terminal
MASTER INDEXLIBRARIAN GUIDE
INDEX/ALGORITHMS/Quick Sort
Sorting // UNSTABLE

Quick Sort_

Efficient, in-place divide-and-conquer sorting algorithm

Abstract // Theoretical Basis

Quicksort is an efficient, in-place sorting algorithm that uses the divide-and-conquer paradigm. It partitions an array into two subarrays around a pivot element and recursively sorts them.

Interactive Simulation

Simulation_Env:Active
Step 1 / 42
7
i:0
2
i:1
9
i:2
4
i:3
1
i:4
8
i:5
3
i:6
6
i:7
5
i:8
DataSet_N:9 // Visual_Index_Matrix
Hold Ctrl to Zoom
100%
EXECUTION_TRACE
1

Step 1

Initial array.

[7, 2, 9, 4, 1, 8, 3, 6, 5]
2

Step 2

Pivot selected: 5 at index 8. Partition range [0, 8].

[7, 2, 9, 4, 1, 8, 3, 6, 5]
3

Step 3

Compare arr[0]=7 < pivot 5?

[7, 2, 9, 4, 1, 8, 3, 6, 5]
4

Step 4

Compare arr[1]=2 < pivot 5?

[7, 2, 9, 4, 1, 8, 3, 6, 5]
5

Step 5

Swap arr[0]=2 ↔ arr[1]=7.

[2, 7, 9, 4, 1, 8, 3, 6, 5]
6

Step 6

Compare arr[2]=9 < pivot 5?

[2, 7, 9, 4, 1, 8, 3, 6, 5]
7

Step 7

Compare arr[3]=4 < pivot 5?

[2, 7, 9, 4, 1, 8, 3, 6, 5]
8

Step 8

Swap arr[1]=4 ↔ arr[3]=7.

[2, 4, 9, 7, 1, 8, 3, 6, 5]
9

Step 9

Compare arr[4]=1 < pivot 5?

[2, 4, 9, 7, 1, 8, 3, 6, 5]
10

Step 10

Swap arr[2]=1 ↔ arr[4]=9.

[2, 4, 1, 7, 9, 8, 3, 6, 5]
11

Step 11

Compare arr[5]=8 < pivot 5?

[2, 4, 1, 7, 9, 8, 3, 6, 5]
12

Step 12

Compare arr[6]=3 < pivot 5?

[2, 4, 1, 7, 9, 8, 3, 6, 5]
13

Step 13

Swap arr[3]=3 ↔ arr[6]=7.

[2, 4, 1, 3, 9, 8, 7, 6, 5]
14

Step 14

Compare arr[7]=6 < pivot 5?

[2, 4, 1, 3, 9, 8, 7, 6, 5]
15

Step 15

Place pivot 5 at position 4.

[2, 4, 1, 3, 5, 8, 7, 6, 9]
16

Step 16

Pivot selected: 3 at index 3. Partition range [0, 3].

[2, 4, 1, 3, 5, 8, 7, 6, 9]
17

Step 17

Compare arr[0]=2 < pivot 3?

[2, 4, 1, 3, 5, 8, 7, 6, 9]
18

Step 18

Swap arr[0]=2 ↔ arr[0]=2.

[2, 4, 1, 3, 5, 8, 7, 6, 9]
19

Step 19

Compare arr[1]=4 < pivot 3?

[2, 4, 1, 3, 5, 8, 7, 6, 9]
20

Step 20

Compare arr[2]=1 < pivot 3?

[2, 4, 1, 3, 5, 8, 7, 6, 9]
21

Step 21

Swap arr[1]=1 ↔ arr[2]=4.

[2, 1, 4, 3, 5, 8, 7, 6, 9]
22

Step 22

Place pivot 3 at position 2.

[2, 1, 3, 4, 5, 8, 7, 6, 9]
23

Step 23

Pivot selected: 1 at index 1. Partition range [0, 1].

[2, 1, 3, 4, 5, 8, 7, 6, 9]
24

Step 24

Compare arr[0]=2 < pivot 1?

[2, 1, 3, 4, 5, 8, 7, 6, 9]
25

Step 25

Place pivot 1 at position 0.

[1, 2, 3, 4, 5, 8, 7, 6, 9]
26

Step 26

Pivot selected: 9 at index 8. Partition range [5, 8].

[1, 2, 3, 4, 5, 8, 7, 6, 9]
27

Step 27

Compare arr[5]=8 < pivot 9?

[1, 2, 3, 4, 5, 8, 7, 6, 9]
28

Step 28

Swap arr[5]=8 ↔ arr[5]=8.

[1, 2, 3, 4, 5, 8, 7, 6, 9]
29

Step 29

Compare arr[6]=7 < pivot 9?

[1, 2, 3, 4, 5, 8, 7, 6, 9]
30

Step 30

Swap arr[6]=7 ↔ arr[6]=7.

[1, 2, 3, 4, 5, 8, 7, 6, 9]
31

Step 31

Compare arr[7]=6 < pivot 9?

[1, 2, 3, 4, 5, 8, 7, 6, 9]
32

Step 32

Swap arr[7]=6 ↔ arr[7]=6.

[1, 2, 3, 4, 5, 8, 7, 6, 9]
33

Step 33

Place pivot 9 at position 8.

[1, 2, 3, 4, 5, 8, 7, 6, 9]
34

Step 34

Pivot selected: 6 at index 7. Partition range [5, 7].

[1, 2, 3, 4, 5, 8, 7, 6, 9]
35

Step 35

Compare arr[5]=8 < pivot 6?

[1, 2, 3, 4, 5, 8, 7, 6, 9]
36

Step 36

Compare arr[6]=7 < pivot 6?

[1, 2, 3, 4, 5, 8, 7, 6, 9]
37

Step 37

Place pivot 6 at position 5.

[1, 2, 3, 4, 5, 6, 7, 8, 9]
38

Step 38

Pivot selected: 8 at index 7. Partition range [6, 7].

[1, 2, 3, 4, 5, 6, 7, 8, 9]
39

Step 39

Compare arr[6]=7 < pivot 8?

[1, 2, 3, 4, 5, 6, 7, 8, 9]
40

Step 40

Swap arr[6]=7 ↔ arr[6]=7.

[1, 2, 3, 4, 5, 6, 7, 8, 9]
41

Step 41

Place pivot 8 at position 7.

[1, 2, 3, 4, 5, 6, 7, 8, 9]
42

Step 42

Array is fully sorted.

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Computational Analysis

Average Time Complexity

Θ(nlog⁡n)\Theta(n \log n)

Recurrence Relation

T(n)=2T(n/2)+Θ(n)T(n) = 2T(n/2) + \Theta(n)

Note on Space Allocation: Sorts in-place, but requires expected Θ(log⁡n)\Theta(\log n) space for the recursion call stack. In the worst-case (unbalanced partitions), the space complexity can degrade to O(n)O(n) if tail-call optimization is not implemented.

Procedural Methodology

01

Divide: Select a pivot element from the array and partition the elements such that all elements less than or equal to the pivot are placed to its left, and all strictly greater elements are placed to its right.

02

Conquer: Recursively call the quicksort algorithm on the two subarrays (left of the pivot and right of the pivot).

03

Combine: Because the subarrays are sorted in place, no explicit combination step is needed to merge them. The entire array is sorted.

Reference Implementation

Logic_Processor.v1
1
QUICKSORT(A, p, r)
2 if p < r
3 q = PARTITION(A, p, r)
4 QUICKSORT(A, p, q - 1)
5 QUICKSORT(A, q + 1, r)
6
7PARTITION(A, p, r)
8 x = A[r]
9 i = p - 1
10 for j = p to r - 1
11 if A[j] <= x
12 i = i + 1
13 exchange A[i] with A[j]
14 exchange A[i + 1] with A[r]
15 return i + 1
Executing Line 1

This pseudocode implements the Lomuto partition scheme using 0-indexed bounds. p is the starting index and r is the ending index (inclusive).

Theoretical Constraints & Pitfalls

TH-CST.01

The worst-case time complexity of Θ(n2)\Theta(n^2) occurs when the array is already sorted or reverse sorted and a naive pivot strategy (like choosing the last element) is used.

TH-CST.02

To mitigate worst-case scenarios, a randomized pivot selection (Randomized Quicksort) or the Median-of-3 method should be implemented.

Industrial Domain Applications

APP-DMN.01

It is widely used as a general-purpose sorting algorithm in standard libraries (e.g., C++ std::sort utilizes Introsort, which is based on Quicksort) due to its excellent average-case performance and small constant factors.

APP-DMN.02

It works exceptionally well in virtual-memory environments because of its good cache locality and sequential memory access patterns.

Technical Nomenclature

TH-CST

Theoretical Constraint: Denotes a mathematical or architectural limitation inherent to the algorithm's design.

APP-DMN

Application Domain: Identifies specific industrial or computational environments where the algorithm is implemented.

CMP-ANL

Comparative Analysis: Evaluates performance trade-offs between current and alternative algorithmic paradigms.

Comparative Analysis

CMP-ANL.01

compare_arrowsVersus MERGE SORT

Merge sort provides a guaranteed worst-case time complexity of Θ(nlog⁡n)\Theta(n \log n) and is stable, unlike quicksort. However, quicksort operates in-place requiring only Θ(log⁡n)\Theta(\log n) space, and generally outperforms merge sort in practice due to smaller constant factors and superior cache locality.

Academic Index & Citations

Introduction to Algorithms, Third Edition (CLRS)

Research Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Reference Node: Chapter 7: Quicksort, Sections 7.1 - 7.4