Searching and Sorting

Searching

Boolean search: does the element belong to the set ("yes-no") vs. place search  if "place" is defined (index).
Linear search.
Binary search (bisection of interval).
Hashtable: hash function (hashcode), collision, collision handling schemes, separate chaining, open addressing, linear probing, double hashing.
Running time of different operations for different methods.

Sorting

Abstract properties - time complexity and space complexity, average and worst case, running time in practice, ease of programming.
Stable and unstable methods.
"Slow" methods - quadratic: insertion sort
"Quick" general methods - nlogn: quicksort (unstable), merge sort (extra memory), binary insertion sort (homework!), heapsort (discussed later). Divide and conquer strategies.
Special methods: counting sort, radix sort, bucket sort.


Otsimine ja järjestamine

Otsimise ülesanne

Tuvastada etteantud elemendi kuuluvus etteantud struktuuri.
Tulemuseks võib sõltuvalt ülesandest olla: tõeväärtus (kuulub-ei kuulu), "asukoht" struktuuris (või signaal mittekuulumise kohta), element ise vms.
Meie näidetes üritame leida elemendi asukohta.

Kahendotsimine (Binary Search)

"Lõigu poolitamine" matemaatikas. On rakendatav kahel eeltingimusel:
  1. vaadeldav struktuur on järjestatud
  2. elemendid on indekseeritavad
O(log n)
   /**
    * Leida etteantud listist etteantud element kahendotsimise abil.
    * @param a list.
    * @param e otsitav element.
    * @returns otsitava elemendi indeks või -1, kui elementi ei leidu.
    */
   
   static public int otsi (List a, Comparable e) {

      int j = -1;
      int l = 0;              // vasakpoolne otspunkt
      int r = a.size() - 1;   // parempoolne otspunkt
      while (l <= r) {
         j = (l + r) / 2;
         if (e.compareTo ((Comparable)a.get (j)) == 0)
            return j;
         if (e.compareTo ((Comparable)a.get (j)) > 0)
            l = j+1; // vasak otspunkt nihkub paremale
         else
            r = j-1; // parem otspunkt nihkub vasakule
      };
      return -1;
   } // otsi lopp

Paisktabel

Lugeda vastav peatükk õpikust!

Võtmed, võtmeruum, paisktabel, paiskfunktsioon, kollisioonid, välisahelad, lahtine adresseerimine, topeltpaiskamine

Lisamine ja otsimine: O(1)

Järjestamismeetodid

Abstraktne keerukus, konkreetne keerukus (keskmine, halvim), mäluvajadus, algoritmi lihtsus, stabiilsus, ...

"Aeglased" meetodid: O(n2)


  "Kiired" meetodid: O(nlogn)


 Erimeetodid (kitsendustega): O(n)

Positsioonimeetodi programm

Vaata ka www.sorting-algorithms.com

Pistemeetod (Insertion Sort):

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



 

Kahendpistemeetod:

"Õige" koht leitakse kahendotsimisega: O(nlogn), kui "pistmine" oleks O(1)


Ühildusmeetod (Merge Sort):

"Jaga ja valitse" : jagatakse kogu aeg pooleks (kuni pikkus < 2), pooled ühendatakse lineaarse keerukusega ühildamise abil, kasutatakse lisamälu mahuga O(n)
   static public <T extends Object & Comparable<? super T>> void
      mergesort (List<T> massiiv, int l, int r) {
         if (massiiv.size() < 2) return;
         if ((r-l)<2) return;
         int k = (l+r)/2;
         mergesort (massiiv, l, k);
         mergesort (massiiv, k, r);
         merge (massiiv, l, k, r);
   } // mergesort() lopp

   static public <T extends Object & Comparable<? super T>> void
      merge (List<T> massiiv, int l, int k, int r) {
         if (massiiv.size() < 2) return;
         if ((r-l) < 2) return;
         if (k<=l) return;
         if (k>=r) return;
         List<T> abi = new ArrayList<T>(r-l);
         int n1 = l;
         int n2 = k;
         T elem = null;
         while (true) {
            if ((n1 < k) && (n2 < r)) {
               if (massiiv.get (n1).compareTo (massiiv.get (n2)) > 0) {
                  elem = massiiv.get (n2);
                  n2++;
               } else {
                  elem = massiiv.get (n1);
                  n1++;
               }
               abi.add (elem);
            } else {
               if (n1 >= k) {
                  for (int i = n2; i < r; i++) {
                     abi.add (massiiv.get (i));
                  }
                  break;
               } else {
                  for (int i = n1; i < k; i++) {
                     abi.add (massiiv.get (i));
                  }
                  break;
               }
            }
         }
         for (int i=l; i < r; i++) {
            massiiv.set (i, abi.get (i-l));
         }
   }


Kiirmeetod (Quicksort):

(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+1); // rekursioon
      if (i < r-1) sort (massiiv, i, r); // rekursioon
   } // sort() lopp



Otsimisel ja järjestamisel on abiks
 
java.util.Arrays, java.util.Collections
 
 
J. Pöial