Quick Sort Algorithm in DSA C - Execution Trace

Concept Flow - Quick Sort Algorithm

Choose pivot element

↓

Partition array around pivot

↓

Elements < pivot to left, > pivot to right

↓

Recursively quick sort left sub-array

↓

Recursively quick sort right sub-array

↓

Combine sorted sub-arrays

↓

Sorted array ready

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

Execution Sample

DSA C

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

This code sorts an array by partitioning around a pivot and recursively sorting sub-arrays.

Execution Table

Step	Operation	Array State	Pivot	Partition Action	Resulting Array State
1	Choose pivot (last element)	[10, 7, 8, 9, 1, 5]	5	Partition: elements <5 to left, >5 to right	[1, 5, 8, 9, 7, 10]
2	Recursive call on left sub-array [1]	[1, 5, 8, 9, 7, 10]	1	Single element, no partition	[1]
3	Recursive call on right sub-array [8, 9, 7, 10]	[1, 5, 8, 9, 7, 10]	10	Partition: elements <10 to left, >10 to right	[1, 5, 8, 9, 7, 10]
4	Recursive call on left sub-array [8, 9, 7]	[1, 5, 8, 9, 7, 10]	7	Partition: elements <7 to left, >7 to right	[1, 5, 7, 9, 8, 10]
5	Recursive call on left sub-array []	[1, 5, 7, 9, 8, 10]	-	Empty sub-array, no action	[]
6	Recursive call on right sub-array [9, 8]	[1, 5, 7, 9, 8, 10]	8	Partition: elements <8 to left, >8 to right	[1, 5, 7, 8, 9, 10]
7	Recursive call on left sub-array []	[1, 5, 7, 8, 9, 10]	-	Empty sub-array, no action	[]
8	Recursive call on right sub-array [9]	[1, 5, 7, 8, 9, 10]	9	Single element, no partition	[9]
9	All sub-arrays sorted	[1, 5, 7, 8, 9, 10]	-	Sorting complete	[1, 5, 7, 8, 9, 10]

💡 All sub-arrays are sorted or empty, recursion ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 6	Final
arr	[10, 7, 8, 9, 1, 5]	[1, 5, 8, 9, 7, 10]	[1, 5, 8, 9, 7, 10]	[1, 5, 8, 9, 7, 10]	[1, 5, 7, 9, 8, 10]	[1, 5, 7, 8, 9, 10]	[1, 5, 7, 8, 9, 10]
pivot	-	5	1	10	7	8	-
low	0	0	0	3	3	4	-
high	5	5	0	5	5	5	-

Key Moments - 3 Insights

Why do we choose the last element as the pivot?

Choosing the last element as pivot simplifies partitioning logic, as seen in Step 1 of execution_table where 5 is pivot.

What happens when the sub-array has one or zero elements?

No partitioning is needed; recursion stops immediately, as shown in Steps 2, 5, 7, and 8 where sub-arrays are empty or single-element.

How does partitioning rearrange the array?

Partition moves elements smaller than pivot to left and larger to right, updating array state as in Step 1 and Step 4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 1, what is the pivot chosen?

A 10

B 5

C 1

D 7

💡 Hint

Check the 'Pivot' column in Step 1 of execution_table.

At which step does the array first become partially sorted with 7 in its correct position?

A Step 6

B Step 2

C Step 4

D Step 9

💡 Hint

Look at the 'Resulting Array State' column and find when 7 is placed correctly.

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

A Pivot would be 10 and partitioning would rearrange differently

B Pivot would still be 5 and no change

C Pivot would be 1 and partitioning would be the same

D Pivot would be 7 and partitioning would be unchanged

💡 Hint

Pivot choice affects partitioning; Step 1 pivot is last element 5 now.

Concept Snapshot

Quick Sort Algorithm:
- Choose a pivot (commonly last element)
- Partition array: smaller left, larger right
- Recursively sort left and right sub-arrays
- Base case: sub-array size ≤ 1
- Efficient average O(n log n) sorting
- In-place and divide-and-conquer method

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 smaller than the pivot come before it, and all larger come after. This is called partitioning. After partitioning, the pivot is in its correct sorted position. The algorithm then recursively applies the same steps to the left and right sub-arrays around the pivot. When sub-arrays have one or zero elements, recursion stops. This process continues until the entire array is sorted. The execution table shows each step of choosing pivots, partitioning, and recursive calls, with the array state changing accordingly. The variable tracker follows key variables like the array, pivot, and indices. Key moments clarify why the pivot is chosen as last element, what happens with small sub-arrays, and how partitioning rearranges elements. The visual quiz tests understanding of pivot choice, array state changes, and effects of changing pivot selection. Quick Sort is a fast, in-place sorting algorithm using divide and conquer.

Practice

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

easy

A. Divide the array into smaller parts using a pivot and sort them recursively

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

C. Insert elements one by one into a sorted list

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's approach

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

2. Step 2: Recursive sorting of parts

   It then sorts these parts recursively, combining them to get the sorted array.

3. Final Answer:

   Divide the array into smaller parts using a pivot and sort them recursively -> Option A

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

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

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort merges arrays like Merge Sort
• Believing Quick Sort inserts elements one by one

2. Which of the following is the correct way to declare the partition function header in C for Quick Sort?

easy

A. int partition(int arr, int low, int high);

B. int partition(int arr[], int low, int high);

C. void partition(int arr[], int low, int high);

D. int partition(int arr[], int start, int end, int pivot);

Solution

1. Step 1: Check parameter types for partition

   The partition function takes an array and two indices low and high to work on a subarray.

2. Step 2: Confirm return type

   It returns an integer index of the pivot after partitioning.

3. Final Answer:

   int partition(int arr[], int low, int high); -> Option B

4. Quick Check:

   Partition returns pivot index [OK]

Hint: Partition returns pivot index; use array and low, high indices [OK]

Common Mistakes:

• Using void return type for partition
• Passing array as int instead of int[]
• Adding extra parameters like pivot

3. What will be the output array after applying Quick Sort on arr = {3, 6, 8, 10, 1, 2, 1}?

medium

A. [3, 6, 8, 10, 1, 2, 1]

B. [10, 8, 6, 3, 2, 1, 1]

C. [1, 1, 2, 3, 6, 8, 10]

D. [1, 2, 1, 3, 6, 8, 10]

Solution

1. Step 1: Apply Quick Sort logic on the array

   Quick Sort rearranges elements around pivots recursively, sorting the array in ascending order.

2. Step 2: Sort the given array

   Sorting {3,6,8,10,1,2,1} results in {1,1,2,3,6,8,10}.

3. Final Answer:

   [1, 1, 2, 3, 6, 8, 10] -> Option C

4. Quick Check:

   Sorted array ascending = [1,1,2,3,6,8,10] [OK]

Hint: Quick Sort outputs sorted array ascending by default [OK]

Common Mistakes:

• Assuming Quick Sort keeps original order
• Confusing ascending with descending order
• Not sorting duplicates correctly

4. Identify the error in this Quick Sort partition function snippet:

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

medium

A. Variable i should start at low - 1, not low

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

C. Loop should run till j <= high, not j < high

D. Swap function is called with wrong arguments

Solution

1. Step 1: Check initialization of i

   In partition, i should start at low - 1 to correctly track smaller elements.

2. Step 2: Analyze loop and swaps

   Starting i at low causes skipping the first element comparison and wrong swaps.

3. Final Answer:

   Variable i should start at low - 1, not low -> Option A

4. Quick Check:

   i = low - 1 fixes partition indexing [OK]

Hint: Initialize i to low - 1 before partition loop [OK]

Common Mistakes:

• Starting i at low causes incorrect partitioning
• Changing pivot position unnecessarily
• Extending loop beyond high index

5. Given an array with many duplicate elements, which modification to Quick Sort helps improve performance?

hard

A. Use Bubble Sort instead for duplicates

B. Always choose the first element as pivot

C. Skip sorting duplicates by checking equality before partition

D. Use 3-way partitioning to separate less than, equal to, and greater than pivot

Solution

1. Step 1: Understand problem with duplicates in Quick Sort

   Standard Quick Sort can degrade with many duplicates due to repeated swaps and partitions.

2. Step 2: Apply 3-way partitioning

   3-way partitioning divides array into three parts: less than, equal to, and greater than pivot, reducing unnecessary work.

3. Final Answer:

   Use 3-way partitioning to separate less than, equal to, and greater than pivot -> Option D

4. Quick Check:

   3-way partitioning optimizes duplicates [OK]

Hint: 3-way partitioning handles duplicates efficiently [OK]

Common Mistakes:

• Choosing fixed pivot without randomization
• Skipping duplicates without partitioning
• Switching to slower sorts unnecessarily