Quicksort

Quicksort

The quicksort is the fastest known comparison-based sorting algorithm, with a growth rate of O (n log n) on average. However, in the worst case, this degrades to O (n[sup]2[/sup]), but this can be mostly avoided if implemented carefully.

Yin-So Chen

September 13, 1999 16k views

Now that we visit a recursive sorting algorithm. This algorithm involves moving a data, called pivot. The algorithm then partitions the array into two parts by moving the pivot into its correct position, so that items to the pivot's left are smaller then the pivot, and the items to the right are bigger.The algorithm then is called recursively so that it will partition the two subordinate arrays on either side of the pivot until the entire array is sorted.

Below is the pseudo-code of Quick Sort.

Quick Sort (Sorting array A[size])
 
 While Low is less than High
 {
 Choose Pivot as the element at position A[Low]
 While A[High] is greater than Pivot, decrement High; else move A[High] to A[Low]
 While A[Low] is less than Pivot, increment Low; else move A[Low] to A[High]
 }
 Move Pivot into A[High], see Pivot position as High.
 If Low is less than Pivot point, recursively call Quick Sort with Low =
 Low, High = Pivot point - 1
 If High is greater than Pivot point, recursively call Quick Sort with Low =
 Pivot point + 1, High = High.

Related Tutorials

Balancing Game Development and Creative Direction in Indie Production

My Unreal Engine Development Process: From Core Idea to Playable Build

Introducing LaneGraph: The Ultimate Road Network Solution for Unity

Retargeting Mixamo Characters with Root Motion In Unreal Engine 5.4.

How To Make A SIMPLE Main Menu In Unity

Guide to Gameplay Balance

Discussion

Discussion

More from Yin-So Chen

Comparing Shadow Mapping Techniques with Shadow Explorer

New Incentives and a Whole New Platform From The Intel AppUp developer program

The Game Maker