Quicksort: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 29: Line 29:
=Correctness=
=Correctness=
=Complexity=
=Complexity=
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 subarray containing the left zone and on the subarray containing the pivot and on the right zone.
# '''Combine''': since the zones are already sorted, there is nothing to combine.
<syntaxhighlight lang='java'>
/**
* @param p the index of the first element of the array to be sorted (subarray of int[] a)
* @param r the index of the first element *outside* the area to be sorted.
**/
public void quicksort(int[] a, int p, int r) {
    if (p < r - 1) {
        int q = partition(a, p, r);
        quicksort(a, p, q);
        quicksort(a, q, r);
    }
}
/**
* @param p the index of the first element of the array to be sorted (subarray of int[] a)
* @param r the index of the first element *outside* the area to be sorted.
**/
private int partition(int[] a, int p, int r) {
    int pivot = a[r - 1];
    int i = p - 1;
    for(int j = p; j < r - 1; j ++) {
        if (a[j] <= pivot) {
            i = i + 1;
            //
            // swap i, j
            //
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    //
    // swap i + 1 and the pivot
    //
    int q = i + 1;
    int tmp = a[q];
    a[q] = a[r - 1];
    a[r - 1] = tmp;
    return q;
}
</syntaxhighlight>


=Example=
=Example=

Revision as of 20:54, 27 September 2021

Internal

Overview

Quicksort is an in-place sorting divide-and-conquer algorithm. Being an in-place sorting algorithm is considered preferable to merge sort, which has to allocate extra memory.

Worst-case time Θ(n2)
Expected running time Θ(n lg n)
Best-case time Θ(n lg n)

Algorithm

The key idea of Quicksort is to partition an array around a pivot. The pivot is chosen randomly and it can be formally shown that randomly choosing a pivot at each step of the algorithm produces an O(n lg n) time complexity on average. Partitioning an array is discussed here: The Partition Subroutine.

After partitioning, we'll end up with three distinct sections of the array: the subarray where all elements are smaller or equal than the pivot, the pivot and the subarray where all elements are bigger than the pivot.

The partitioning is the divide phase of the divide and conquer algorithm.

The next step is to "conquer": call quicksort recursively on the first and the last section of the array. The pivot is already in the correct position and we will leave it there.

The last step, "combine", does not do anything.

Correctness

Complexity

Example

Playground Quicksort

Time Complexity Analysis

QuickSort does not subdivide the problem in equal subproblems at one level, so the master theorem does not apply in its current form.

CLRS pages 174, 180.

TODO Stanford algorithm class:

Quicksort and Selection Problem

The randomized Quicksort algorithm is somewhat similar to the one used by the generic selection problem.

Retrieved from "https://kb.novaordis.com/index.php?title=Quicksort&oldid=82154"