Quicksort: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Internal=
=Internal=


* [[Algorithms#Sorting_Algorithms|Algorithms]]
* [[Recursive_Algorithms#Divide_and_Conquer|Divide and Conquer Algorithms]]
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]]
* [[Sorting_Algorithms#Sorting_Algorithms|Sorting Algorithms]]
* [[The Partition Subroutine]]
* [[The Partition Subroutine]]
=Overview=
=Overview=


Line 17: Line 18:


=Algorithm=
=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.
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#Overview|The Partition Subroutine]].


=Correctness=
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.
=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:
The partitioning is the divide phase of the [[Algorithms#Divide_and_Conquer|divide and conquer]] algorithm.
# '''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'>
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.
/**
* @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) {
The last step, "combine", does not do anything.
 
==Pseudocode==
        int q = partition(a, p, r);
<font size=-1>
 
Quicksort(array A, length n)
        quicksort(a, p, q);
  if n == 1, return
        quicksort(a, q, r);
  p = ChoosePivot(A, n)
    }
  partition A around p
}
  Quicksort(first part of array A)
 
  Quicksort(second part of array A)
/**
</font>
* @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=
 
{{External|[https://github.com/ovidiuf/playground/blob/master/data-structures-and-algorithms/quicksort/src/main/java/playground/dsa/quicksort/Quicksort.java Playground Quicksort]}}


=Time Complexity Analysis=
=Time Complexity Analysis=
QuickSort does not subdivide the problem in equal subproblems at one level, so the [[Master_Method#Overview|master theorem]] does not apply in its current form.
QuickSort does not subdivide the problem in equal subproblems at one level, so the [[Master_Method#Overview|master theorem]] does not apply in its current form.


<font color=darkgray>[[CLRS]] pages 174, 180.</font>
A discussion of the time complexity is available here:
 
<font color=darkkhaki>
TODO Stanford algorithm class:  
* https://www.coursera.org/learn/algorithms-divide-conquer/lecture/5Tuvu/analysis-i-a-decomposition-principle
* https://www.coursera.org/learn/algorithms-divide-conquer/lecture/5Tuvu/analysis-i-a-decomposition-principle
* https://www.coursera.org/learn/algorithms-divide-conquer/lecture/sIY1s/analysis-ii-the-key-insight
* https://www.coursera.org/learn/algorithms-divide-conquer/lecture/sIY1s/analysis-ii-the-key-insight
* https://www.coursera.org/learn/algorithms-divide-conquer/lecture/aqD1O/analysis-iii-final-calculations
* https://www.coursera.org/learn/algorithms-divide-conquer/lecture/aqD1O/analysis-iii-final-calculations
</font>
 
<font color=darkgray>[[CLRS]] pages 174, 180.</font>


=Quicksort and Selection Problem=
=Quicksort and Selection Problem=


The randomized Quicksort algorithm is somewhat similar to the one used by the generic [[Selection Problem|selection problem]].
The randomized Quicksort algorithm is somewhat similar to the one used by the generic [[Selection Problem|selection problem]].
=Example=
{{External|[https://github.com/ovidiuf/playground/blob/master/data-structures-and-algorithms/quicksort/src/main/java/playground/dsa/quicksort/Quicksort.java Playground Quicksort]}}

Latest revision as of 19:11, 9 November 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.

Pseudocode

Quicksort(array A, length n)
  if n == 1, return
  p = ChoosePivot(A, n)
  partition A around p
  Quicksort(first part of array A)
  Quicksort(second part of array A)

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.

A discussion of the time complexity is available here:

CLRS pages 174, 180.

Quicksort and Selection Problem

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

Example

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