Quick Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Quick Sort Algorithm

Choose pivot element

↓

Partition array around pivot

↓

Elements < pivot to left

↓

Elements > pivot to right

↓

Recursively quicksort left part

→Recursively quicksort right part

↓

Combine sorted parts

Quick Sort picks a pivot, partitions the array around it, then sorts left and right parts recursively.

Execution Sample

DSA Go

func quickSort(arr []int, low, high int) {
  if low < high {
    p := partition(arr, low, high)
    quickSort(arr, low, p-1)
    quickSort(arr, p+1, high)
  }
}

This code sorts an array by partitioning around a pivot and recursively sorting subarrays.

Execution Table

Step	Operation	Pivot	Array State	Partition Indices	Action
1	Choose pivot	7	[7, 2, 1, 6, 8, 5, 3, 4]	low=0, high=7	Pivot is last element 7
2	Partition start	7	[7, 2, 1, 6, 8, 5, 3, 4]	i= -1, j=0	Compare arr[j]=7 with pivot=7
3	Compare	7	[7, 2, 1, 6, 8, 5, 3, 4]	i= -1, j=0	7 <= 7, increment i to 0, swap arr[i] and arr[j]
4	Swap	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=0, j=0	Swap arr[0] and arr[0] (no change)
5	Compare	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=0, j=1	2 <= 7, increment i to 1, swap arr[i] and arr[j]
6	Swap	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=1, j=1	Swap arr[1] and arr[1] (no change)
7	Compare	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=1, j=2	1 <= 7, increment i to 2, swap arr[i] and arr[j]
8	Swap	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=2, j=2	Swap arr[2] and arr[2] (no change)
9	Compare	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=2, j=3	6 <= 7, increment i to 3, swap arr[i] and arr[j]
10	Swap	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=3, j=3	Swap arr[3] and arr[3] (no change)
11	Compare	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=3, j=4	8 > 7, no increment, no swap
12	Compare	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=3, j=5	5 <= 7, increment i to 4, swap arr[i] and arr[j]
13	Swap	7	[7, 2, 1, 6, 8, 5, 3, 4]	i=4, j=5	Swap arr[4] and arr[5] → [7, 2, 1, 6, 5, 8, 3, 4]
14	Compare	7	[7, 2, 1, 6, 5, 8, 3, 4]	i=4, j=6	3 <= 7, increment i to 5, swap arr[i] and arr[j]
15	Swap	7	[7, 2, 1, 6, 5, 8, 3, 4]	i=5, j=6	Swap arr[5] and arr[6] → [7, 2, 1, 6, 5, 3, 8, 4]
16	Compare	7	[7, 2, 1, 6, 5, 3, 8, 4]	i=5, j=7	4 <= 7, increment i to 6, swap arr[i] and arr[j]
17	Swap	7	[7, 2, 1, 6, 5, 3, 8, 4]	i=6, j=7	Swap arr[6] and arr[7] → [7, 2, 1, 6, 5, 3, 4, 8]
18	Partition end	7	[7, 2, 1, 6, 5, 3, 4, 8]	i=6	Swap pivot arr[7] and arr[i+1] arr[7] → [7, 2, 1, 6, 5, 3, 4, 8] becomes [7, 2, 1, 6, 5, 3, 4, 8]
19	Pivot placed	7	[7, 2, 1, 6, 5, 3, 4, 8]	pivot index=7	Pivot 7 is now at index 7
20	Recurse left	-	[7, 2, 1, 6, 5, 3, 4, 8]	low=0, high=6	QuickSort left subarray
21	Choose pivot	4	[7, 2, 1, 6, 5, 3, 4, 8]	low=0, high=6	Pivot is last element 4
22	Partition start	4	[7, 2, 1, 6, 5, 3, 4, 8]	i=-1, j=0	Compare arr[j]=7 with pivot=4
23	Compare	4	[7, 2, 1, 6, 5, 3, 4, 8]	i=-1, j=0	7 > 4, no increment, no swap
24	Compare	4	[7, 2, 1, 6, 5, 3, 4, 8]	i=-1, j=1	2 <= 4, increment i to 0, swap arr[i] and arr[j]
25	Swap	4	[7, 2, 1, 6, 5, 3, 4, 8]	i=0, j=1	Swap arr[0] and arr[1] → [2, 7, 1, 6, 5, 3, 4, 8]
26	Compare	4	[2, 7, 1, 6, 5, 3, 4, 8]	i=0, j=2	1 <= 4, increment i to 1, swap arr[i] and arr[j]
27	Swap	4	[2, 7, 1, 6, 5, 3, 4, 8]	i=1, j=2	Swap arr[1] and arr[2] → [2, 1, 7, 6, 5, 3, 4, 8]
28	Compare	4	[2, 1, 7, 6, 5, 3, 4, 8]	i=1, j=3	6 > 4, no increment, no swap
29	Compare	4	[2, 1, 7, 6, 5, 3, 4, 8]	i=1, j=4	5 > 4, no increment, no swap
30	Compare	4	[2, 1, 7, 6, 5, 3, 4, 8]	i=1, j=5	3 <= 4, increment i to 2, swap arr[i] and arr[j]
31	Swap	4	[2, 1, 7, 6, 5, 3, 4, 8]	i=2, j=5	Swap arr[2] and arr[5] → [2, 1, 3, 6, 5, 7, 4, 8]
32	Partition end	4	[2, 1, 3, 6, 5, 7, 4, 8]	i=2	Swap pivot arr[6] and arr[i+1] arr[3] → [2, 1, 3, 4, 5, 7, 6, 8]
33	Pivot placed	4	[2, 1, 3, 4, 5, 7, 6, 8]	pivot index=3	Pivot 4 is now at index 3
34	Recurse left	-	[2, 1, 3, 4, 5, 7, 6, 8]	low=0, high=2	QuickSort left subarray
35	Choose pivot	3	[2, 1, 3, 4, 5, 7, 6, 8]	low=0, high=2	Pivot is last element 3
36	Partition start	3	[2, 1, 3, 4, 5, 7, 6, 8]	i=-1, j=0	Compare arr[j]=2 with pivot=3
37	Compare	3	[2, 1, 3, 4, 5, 7, 6, 8]	i=-1, j=0	2 <= 3, increment i to 0, swap arr[i] and arr[j]
38	Swap	3	[2, 1, 3, 4, 5, 7, 6, 8]	i=0, j=0	Swap arr[0] and arr[0] (no change)
39	Compare	3	[2, 1, 3, 4, 5, 7, 6, 8]	i=0, j=1	1 <= 3, increment i to 1, swap arr[i] and arr[j]
40	Swap	3	[2, 1, 3, 4, 5, 7, 6, 8]	i=1, j=1	Swap arr[1] and arr[1] (no change)
41	Compare	3	[2, 1, 3, 4, 5, 7, 6, 8]	i=1, j=2	3 <= 3, increment i to 2, swap arr[i] and arr[j]
42	Swap	3	[2, 1, 3, 4, 5, 7, 6, 8]	i=2, j=2	Swap arr[2] and arr[2] (no change)
43	Partition end	3	[2, 1, 3, 4, 5, 7, 6, 8]	i=2	Swap pivot arr[2] and arr[i+1] arr[3] (no change)
44	Pivot placed	3	[2, 1, 3, 4, 5, 7, 6, 8]	pivot index=2	Pivot 3 is now at index 2
45	Recurse left	-	[2, 1, 3, 4, 5, 7, 6, 8]	low=0, high=1	QuickSort left subarray
46	Choose pivot	1	[2, 1, 3, 4, 5, 7, 6, 8]	low=0, high=1	Pivot is last element 1
47	Partition start	1	[2, 1, 3, 4, 5, 7, 6, 8]	i=-1, j=0	Compare arr[j]=2 with pivot=1
48	Compare	1	[2, 1, 3, 4, 5, 7, 6, 8]	i=-1, j=0	2 > 1, no increment, no swap
49	Compare	1	[2, 1, 3, 4, 5, 7, 6, 8]	i=-1, j=1	1 <= 1, increment i to 0, swap arr[i] and arr[j]
50	Swap	1	[2, 1, 3, 4, 5, 7, 6, 8]	i=0, j=1	Swap arr[0] and arr[1] → [1, 2, 3, 4, 5, 7, 6, 8]
51	Partition end	1	[1, 2, 3, 4, 5, 7, 6, 8]	i=0	Swap pivot arr[1] and arr[i+1] arr[1] (no change)
52	Pivot placed	1	[1, 2, 3, 4, 5, 7, 6, 8]	pivot index=1	Pivot 1 is now at index 1
53	Recurse left	-	[1, 2, 3, 4, 5, 7, 6, 8]	low=0, high=0	Base case reached, no action
54	Recurse right	-	[1, 2, 3, 4, 5, 7, 6, 8]	low=2, high=1	Base case reached, no action
55	Recurse right	-	[1, 2, 3, 4, 5, 7, 6, 8]	low=4, high=6	QuickSort right subarray
56	Choose pivot	6	[1, 2, 3, 4, 5, 7, 6, 8]	low=4, high=6	Pivot is last element 6
57	Partition start	6	[1, 2, 3, 4, 5, 7, 6, 8]	i=3, j=4	Compare arr[j]=5 with pivot=6
58	Compare	6	[1, 2, 3, 4, 5, 7, 6, 8]	i=3, j=4	5 <= 6, increment i to 4, swap arr[i] and arr[j]
59	Swap	6	[1, 2, 3, 4, 5, 7, 6, 8]	i=4, j=4	Swap arr[4] and arr[4] (no change)
60	Compare	6	[1, 2, 3, 4, 5, 7, 6, 8]	i=4, j=5	7 > 6, no increment, no swap
61	Compare	6	[1, 2, 3, 4, 5, 7, 6, 8]	i=4, j=6	6 <= 6, increment i to 5, swap arr[i] and arr[j]
62	Swap	6	[1, 2, 3, 4, 5, 7, 6, 8]	i=5, j=6	Swap arr[5] and arr[6] → [1, 2, 3, 4, 5, 6, 7, 8]
63	Partition end	6	[1, 2, 3, 4, 5, 6, 7, 8]	i=5	Swap pivot arr[6] and arr[i+1] arr[6] (no change)
64	Pivot placed	6	[1, 2, 3, 4, 5, 6, 7, 8]	pivot index=6	Pivot 6 is now at index 6
65	Recurse left	-	[1, 2, 3, 4, 5, 6, 7, 8]	low=4, high=5	QuickSort left subarray
66	Choose pivot	5	[1, 2, 3, 4, 5, 6, 7, 8]	low=4, high=5	Pivot is last element 5
67	Partition start	5	[1, 2, 3, 4, 5, 6, 7, 8]	i=3, j=4	Compare arr[j]=5 with pivot=5
68	Compare	5	[1, 2, 3, 4, 5, 6, 7, 8]	i=3, j=4	5 <= 5, increment i to 4, swap arr[i] and arr[j]
69	Swap	5	[1, 2, 3, 4, 5, 6, 7, 8]	i=4, j=4	Swap arr[4] and arr[4] (no change)
70	Partition end	5	[1, 2, 3, 4, 5, 6, 7, 8]	i=4	Swap pivot arr[5] and arr[i+1] arr[5] (no change)
71	Pivot placed	5	[1, 2, 3, 4, 5, 6, 7, 8]	pivot index=5	Pivot 5 is now at index 5
72	Recurse left	-	[1, 2, 3, 4, 5, 6, 7, 8]	low=4, high=4	Base case reached, no action
73	Recurse right	-	[1, 2, 3, 4, 5, 6, 7, 8]	low=6, high=5	Base case reached, no action
74	Recurse right	-	[1, 2, 3, 4, 5, 6, 7, 8]	low=7, high=6	Base case reached, no action
75	Recurse right	-	[1, 2, 3, 4, 5, 6, 7, 8]	low=8, high=7	Base case reached, no action

💡 All subarrays sorted, recursion ends when low >= high

Variable Tracker

Variable	Start	After Step 18	After Step 33	After Step 44	After Step 50	After Step 62	Final
arr	[7, 2, 1, 6, 8, 5, 3, 4]	[7, 2, 1, 6, 5, 3, 4, 8]	[2, 1, 3, 4, 5, 7, 6, 8]	[2, 1, 3, 4, 5, 7, 6, 8]	[1, 2, 3, 4, 5, 7, 6, 8]	[1, 2, 3, 4, 5, 6, 7, 8]	[1, 2, 3, 4, 5, 6, 7, 8]
pivot	7	7	4	3	1	6	-
i	-1	6	2	2	0	5	-
pivot index	-	7	3	2	1	6	-

Key Moments - 3 Insights

Why do we swap elements when arr[j] <= pivot during partition?

Swapping moves smaller elements to the left side of the pivot, ensuring correct partitioning as shown in steps 3-17.

Why is the pivot chosen as the last element in this example?

Choosing the last element as pivot is a common simple strategy; it simplifies partition logic as seen in step 1 and repeated in recursive calls.

When does the recursion stop?

Recursion stops when the subarray has zero or one element (low >= high), as shown in steps 53, 54, 72, 73, 74, 75.

Visual Quiz - 3 Questions

Look at the execution_table at step 13, what is the array state after the swap?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 13 in execution_table.

At which step is the pivot 4 placed in its final position?

A Step 33

B Step 44

C Step 18

D Step 50

💡 Hint

Look for 'Pivot placed' operation with pivot 4 in execution_table.

If the pivot was chosen as the first element instead of the last, how would the partition steps change?

A No change in partition steps

B Pivot would be swapped with last element before partition

C Partition would start from the first element and compare differently

D Recursion would stop earlier

💡 Hint

Consider how pivot choice affects partition start and comparisons in execution_table.

Concept Snapshot

Quick Sort Algorithm:
- Choose a pivot (commonly last element)
- Partition array: elements <= pivot left, > pivot right
- Recursively sort left and right subarrays
- Stops when subarray size <= 1
- Efficient average O(n log n) sorting

Full Transcript

Quick Sort works by picking a pivot element, usually the last in the current array segment. It then rearranges the array so that all elements less than or equal to the pivot come before it, and all greater elements come after. This is called partitioning. After partitioning, the pivot is in its correct sorted position. The algorithm then recursively applies the same process to the left and right parts of the array around the pivot. The recursion stops when the subarray has zero or one element, which means it is already sorted. The execution table shows each comparison and swap during partitioning, how the pivot moves to its final place, and how recursive calls sort smaller parts. The variable tracker shows how the array and pointers change after key steps. This visual step-by-step helps understand how Quick Sort efficiently sorts the array.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Merge two sorted lists into one sorted list

B. Compare every element with every other element and swap if needed

C. Insert elements one by one into a sorted part of the list

D. Divide the list into smaller parts using a pivot and sort them recursively

Solution

1. Step 1: Understand Quick Sort's approach

   Quick Sort picks a pivot element and divides the list into parts smaller and larger than the pivot.

2. Step 2: Recursive sorting of parts

   It then sorts these parts by calling itself on each part, making the whole list sorted.

3. Final Answer:

   Divide the list into smaller parts using a pivot and sort them recursively -> Option D

4. Quick Check:

   Quick Sort = Divide and conquer with pivot [OK]

Hint: Remember: Quick Sort uses a pivot to split and sort recursively [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort or Merge Sort
• Thinking Quick Sort compares all pairs directly
• Believing Quick Sort merges sorted lists

2. Which of the following is the correct way to declare a function for Quick Sort in Go?

easy

A. func quickSort(arr []int) []int

B. func quickSort(arr int[]) int[]

C. func quickSort(arr array of int) array of int

D. function quickSort(arr: []int) -> []int

Solution

1. Step 1: Check Go function syntax

   In Go, functions are declared with func, parameter types after names, and return types after parameters.

2. Step 2: Match correct parameter and return types

   arr []int means a slice of integers, and []int as return type means returning a slice of integers.

3. Final Answer:

   func quickSort(arr []int) []int -> Option A

4. Quick Check:

   Go func syntax = func name(params) returns [OK]

Hint: Go functions: func name(params type) returnType [OK]

Common Mistakes:

• Using array syntax like int[] which is not Go style
• Writing 'function' instead of 'func'
• Placing types before parameter names

3. What will be the output of the following Go code snippet using Quick Sort on the array [3, 6, 2, 7, 5]?

func main() {
    arr := []int{3, 6, 2, 7, 5}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

func quickSort(arr []int, low, high int) {
    if low < high {
        p := partition(arr, low, high)
        quickSort(arr, low, p-1)
        quickSort(arr, p+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

medium

A. [7 6 5 3 2]

B. [3 2 5 6 7]

C. [2 3 5 6 7]

D. [2 3 6 5 7]

Solution

1. Step 1: Understand partition and recursive calls

   The partition function picks the last element as pivot and rearranges elements smaller than pivot to the left. Recursive calls sort left and right parts.

2. Step 2: Trace sorting of [3,6,2,7,5]

   Pivot 5 moves elements less than 5 left: [3,2,5,7,6]. Then recursively sort [3,2] and [7,6]. Final sorted array is [2 3 5 6 7].

3. Final Answer:

   [2 3 5 6 7] -> Option C

4. Quick Check:

   Quick Sort output = sorted array ascending [OK]

Hint: Quick Sort output is sorted ascending array [OK]

Common Mistakes:

• Confusing pivot placement causing wrong order
• Not sorting both left and right parts recursively
• Mixing up indices in partition function

4. Identify the bug in this Quick Sort partition function in Go:

func partition(arr []int, low, high int) int {
    pivot := arr[low]
    i := low
    for j := low + 1; j <= high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i], arr[low] = arr[low], arr[i]
    return i
}

medium

A. Pivot should be arr[high], not arr[low]

B. Swap indices in last line should be arr[i+1], arr[low]

C. Loop should start from j = low, not low + 1

D. Return value should be low, not i

Solution

1. Step 1: Check pivot choice in partition

   Standard Quick Sort uses last element as pivot for partitioning, but here pivot is first element which changes logic.

2. Step 2: Understand impact of pivot choice

   Using arr[low] as pivot requires different partition logic; current swaps and indices assume pivot at end, causing incorrect partition.

3. Final Answer:

   Pivot should be arr[high], not arr[low] -> Option A

4. Quick Check:

   Pivot position must match partition logic [OK]

Hint: Pivot usually last element in standard Quick Sort partition [OK]

Common Mistakes:

• Changing pivot without adjusting partition logic
• Incorrect swap indices causing wrong array order
• Returning wrong partition index

5. You want to sort a large list of integers using Quick Sort but want to optimize for the worst-case scenario. Which modification helps reduce the chance of worst-case performance?

hard

A. Always pick the first element as pivot

B. Pick a random element as pivot each time

C. Sort the list first before applying Quick Sort

D. Use Bubble Sort instead for large lists

Solution

1. Step 1: Understand worst-case in Quick Sort

   Worst-case happens when pivot divides list unevenly, e.g., always smallest or largest element.

2. Step 2: Use random pivot to avoid worst-case

   Choosing a random pivot reduces chance of always bad splits, improving average performance.

3. Final Answer:

   Pick a random element as pivot each time -> Option B

4. Quick Check:

   Random pivot reduces worst-case risk [OK]

Hint: Random pivot choice avoids worst-case splits [OK]

Common Mistakes:

• Always picking first element causes worst-case on sorted input
• Sorting before Quick Sort wastes effort
• Using Bubble Sort is inefficient for large lists