Quicksort: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 20: | Line 20: | ||
=Algorithm= | =Algorithm= | ||
The procedure receives the reference to the array containing the numbers to be sorted, and the edges p (the first element of the section to be sorted) and | The procedure receives the reference to the array containing the numbers to be sorted, and the edges p (the first element of the section to be sorted) and r (the element immediately following the last element to be sorted, or the outside of the array). As all divide-and-conquer algorithms, Quicksort has three steps: | ||
# '''Divide''': it partitions the area to be sorted in three zones, possibly empty: 1) the left zone a[p ... q-1] contains numbers smaller or equal with a special element, called '''pivot''', 2) one zone with one element a[q] containing the pivot 3) the right zone a[q +1 ... r-1], possibly empty that contains numbers bigger or equal with the pivot. | # '''Divide''': it partitions the area to be sorted in three zones, possibly empty: 1) the left zone a[p ... q-1] contains numbers smaller or equal with a special element, called '''pivot''', 2) one zone with one element a[q] containing the pivot 3) the right zone a[q +1 ... r-1], possibly empty that contains numbers bigger or equal with the pivot. | ||
# '''Conquer''': applies itself recursively on the left zone and on the right zone. | # '''Conquer''': applies itself recursively on the left zone and on the right zone. | ||
Revision as of 02:01, 20 August 2018
Internal
Overview
CLRS page 170.
In-place sorting divide-and-conquer algorithm.
| Worst-case time | Θ(n2) |
| Expected running time | Θ(n lgn) |
| Best-case time |
Algorithm
The procedure receives the reference to the array containing the numbers to be sorted, and the edges p (the first element of the section to be sorted) and r (the element immediately following the last element to be sorted, or the outside of the array). As all divide-and-conquer algorithms, Quicksort has three steps:
- Divide: it partitions the area to be sorted in three zones, possibly empty: 1) the left zone a[p ... q-1] contains numbers smaller or equal with a special element, called pivot, 2) one zone with one element a[q] containing the pivot 3) the right zone a[q +1 ... r-1], possibly empty that contains numbers bigger or equal with the pivot.
- Conquer: applies itself recursively on the left zone and on the right zone.
- Combine: since the zones are already sorted, there is nothing to combine.
Time Complexity Analysis
Quicksort and Selection Problem
The randomized Quicksort algorithm is somewhat similar to the one used by the generic selection problem.