lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

index.md (651B)

      1 +++
      2 title = "Quicksort"
      3 +++
      4 
      5 # Quicksort
      6 
      7 algorithm:
      8 
      9 - divide input array into two parts:
     10     - up to index q, keys ≤ pivot
     11     - starting at index q+1, keys ≥ pivot
     12 - sort recursively both sub-arrays
     13 - combine two sub-arrays into one sorted array
     14 
     15 ![screenshot.png](e1298687147a544ae49d5c84761abf9d.png)
     16 
     17 partitioning (in O(n))
     18 
     19 - while list contains more than 1 element:
     20     - take x from list (pivot)
     21     - index i is last key of small-ones-so-far
     22     - index j is first key to be compared to pivot
     23         - if j finds key smaller than pivot, swap that key with i+1
     24 
     25 Worst-case time: ϴ(n²)
     26 Best-case time: ϴ(nlogn)
     27 Average-case: ϴ(nlogn)