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.