SHPORA.net :: PDA | |
Main FAQ гуманитарные науки естественные науки математические науки технические науки Järjestamine: pistemeetod (insertion sort) ja kiirmeetod (quicksort). Pistemeetod: Jada jagatakse "järjestatud osaks" (algselt tühi) ja "järjestamata osaks" (algselt kogu jada). Järjestatud osa pikkust suurendatakse järjekordse elemendi paigutamisega õigele kohale järjestatud osas. /** * Sorteerida pistemeetodil List, mille elemendid realiseerivad * liidest Comparable. * @param a sorteeritav list. */ static public void pisteSort (List a) { if (a.size() < 2) return; for (int i=1; i<a.size(); i++) { Comparable b = (Comparable) a.remove (i); int j; for (j=0; j<i; j++) { if (b.compareTo ((Comparable)a.get (j)) < 0) break; } a.add (j, b); // pistame b kohale j } } // pisteSort() lopp /** * Sorteerime massiivi, mille elemendid realiseerivad * liidest Comparable. * @param a sorteeritav massiiv. */ static public void pisteSort (Comparable[] a) { if (a.length < 2) return; for (int i=1; i<a.length; i++) { Comparable b = a[i]; int j; for (j=i-1; j>=0; j--) { if (a[j].compareTo (b) <= 0) break; a[j+1] = a[j]; // vabastame pistekoha } a[j+1] = b; // pistame b kohale } } // pisteSort() lopp Kiirmeetod: (Osa)jada jagatakse kaheks lühemaks osajadaks nii, et ükski element esimeses osas ei oleks suurem ühestki elemendist teises osas. Siis võib kummagi osa sorteerida eraldi (nad on sõltumatud). "Jaga ja valitse" /** * Sorteerida massiiv kiirmeetodil. * @param massiiv sorteeritav massiiv. * @param l vasakpoolne otspunkt. * @param r parempoolne otspunkt. */ static public void sort (Comparable[] massiiv, int l, int r) { if (massiiv.length < 2) return; int i = l; int j = r; Comparable x = massiiv [(i+j) / 2]; do { while (massiiv [i].compareTo (x) < 0) i++; while (x.compareTo (massiiv [j]) < 0) j--; if (i <= j) { Comparable tmp = massiiv [i]; massiiv [i] = massiiv [j]; massiiv [j] = tmp; // selle koha peal on väljatrükk silumiseks: "veelahe" ja vahetatavad i++; j--; } } while (i < j); if (l < j) sort (massiiv, l, j); // rekursioon if (i < r) sort (massiiv, i, r); // rekursioon } // sort() lopp |