Quicksort: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 19: Line 19:


=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 q (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 contains numbers smaller or equal with a special element, called '''pivot''', 2) one zone with one element containing the pivot 3) the right zone, 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=
=Time Complexity Analysis=

Revision as of 00:51, 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 q (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:

  1. Divide: it partitions the area to be sorted in three zones, possibly empty: 1) the left zone contains numbers smaller or equal with a special element, called pivot, 2) one zone with one element containing the pivot 3) the right zone, possibly empty that contains numbers bigger or equal with the pivot.
  2. Conquer: applies itself recursively on the left zone and on the right zone.
  3. 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.