Quick Sort Algorithm in DSA C# - Build from Scratch

Quick Sort Algorithm

📖 Scenario: You are helping a librarian organize a list of book IDs in ascending order so that books can be found quickly.

🎯 Goal: Build a program that sorts a list of integers using the Quick Sort algorithm step-by-step.

📋 What You'll Learn

Create an integer array called bookIds with exact values

Create a helper variable n to store the length of bookIds

Write a QuickSort method that sorts the array using the Quick Sort algorithm

Print the sorted array in the format: 1 -> 2 -> 3 -> null

💡 Why This Matters

🌍 Real World

Quick Sort is used in many software systems to efficiently sort data like book IDs, user records, or transaction logs.

💼 Career

Understanding Quick Sort helps in technical interviews and improves problem-solving skills for software development roles.

1

Create the initial array of book IDs

Create an integer array called bookIds with these exact values: 33, 10, 55, 71, 29, 3, 18

DSA C#

// Create the array bookIds with the given values
// Your code here

Hint

Use int[] bookIds = {33, 10, 55, 71, 29, 3, 18}; to create the array.

2

Add a variable for the array length

Create an integer variable called n and set it to the length of the bookIds array using bookIds.Length

DSA C#

int[] bookIds = {33, 10, 55, 71, 29, 3, 18};
// Create variable n to store length of bookIds
// Your code here

Hint

Use int n = bookIds.Length; to get the array length.

3

Write the QuickSort method

Write a method called QuickSort that takes an integer array arr, a start index low, and an end index high. Implement the Quick Sort algorithm using recursion and a helper method Partition.

DSA C#

int[] bookIds = {33, 10, 55, 71, 29, 3, 18};
int n = bookIds.Length;

// Write QuickSort and Partition methods below
// Your code here

Hint

Use recursion in QuickSort and swap elements in Partition to sort the array.

4

Print the sorted array

Print the sorted bookIds array in the format: each number followed by -> and ending with null. For example: 3 -> 10 -> 18 -> 29 -> 33 -> 55 -> 71 -> null

DSA C#

int[] bookIds = {33, 10, 55, 71, 29, 3, 18};
int n = bookIds.Length;

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);
    }
}

int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp1 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp1;
    return i + 1;
}

QuickSort(bookIds, 0, n - 1);

// Print the sorted array in the required format
// Your code here

Hint

Use a for loop to print each element followed by ->, then print null at the end.

Practice

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

easy

A. Insert elements one by one into a sorted list

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

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

D. Merge two sorted arrays into one sorted array

Solution

1. Step 1: Understand Quick Sort's partitioning

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

2. Step 2: Apply recursive sorting

   It then sorts these parts recursively to get the full sorted array.

3. Final Answer:

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

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
• Ignoring the pivot concept

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

easy

A. public int Partition(int[] arr, int low, int high)

B. public void Partition(int[] arr, int low, int high)

C. public int Partition(int arr[], int low, int high)

D. void Partition(int[] arr, int low, int high)

Solution

1. Step 1: Understand partition function return type

   The partition function returns the pivot index as an integer after rearranging elements.

2. Step 2: Check C# syntax for arrays and access modifiers

   In C#, arrays are declared as int[] arr and public methods specify return type before method name.

3. Final Answer:

   public int Partition(int[] arr, int low, int high) -> Option A

4. Quick Check:

   Partition returns int index [OK]

Hint: Partition returns pivot index, so return type must be int [OK]

Common Mistakes:

• Using void instead of int as return type
• Incorrect array syntax like int arr[] in C#
• Missing access modifier or wrong order

3. What will be the output array after one partition call on arr = [8, 3, 7, 6, 2] with pivot as last element (2)?

medium

A. [8, 3, 7, 6, 2]

B. [2, 3, 7, 6, 8]

C. [3, 2, 7, 6, 8]

D. [2, 3, 6, 7, 8]

Solution

1. Step 1: Choose pivot and start partitioning

   Pivot is 2 (last element). Elements less than 2 go left, others right.

2. Step 2: Rearrange elements around pivot

   Only 2 is less or equal to pivot, so it swaps with first element 8. Result: [2, 3, 7, 6, 8]

3. Final Answer:

   [2, 3, 7, 6, 8] -> Option B

4. Quick Check:

   Pivot 2 placed at start [OK]

Hint: Pivot last element; smaller elements move left [OK]

Common Mistakes:

• Not swapping pivot correctly
• Assuming full sort after one partition
• Mixing pivot with first element

4. Identify the error in this Quick Sort partition code 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) {
      Swap(arr, i, j);
      i++;
    }
  }
  Swap(arr, i, high);
  return i;
}

medium

A. The loop should use <= high instead of < high

B. The comparison should be <= pivot instead of < pivot

C. Swap should be called outside the loop only once

D. The initial value of i should be low - 1

Solution

1. Step 1: Understand partition index initialization

   Variable i tracks the position for swapping smaller elements. It should start at low - 1 to correctly place elements.

2. Step 2: Check loop and swap logic

   Loop runs from low to high-1, swapping when arr[j] < pivot. Starting i at low causes incorrect swaps.

3. Final Answer:

   The initial value of i should be low - 1 -> Option D

4. Quick Check:

   i starts at low-1 for correct partition [OK]

Hint: i starts before low to track smaller elements [OK]

Common Mistakes:

• Starting i at low causes wrong swaps
• Changing loop bounds incorrectly
• Using wrong comparison operator

5. Given the array [10, 7, 8, 9, 1, 5], what is the array state after the first full Quick Sort partition step choosing the last element as pivot?

hard

A. [1, 5, 8, 9, 7, 10]

B. [1, 5, 7, 8, 9, 10]

C. [1, 7, 8, 9, 10, 5]

D. [1, 5, 8, 9, 10, 7]

Solution

1. Step 1: Identify pivot and partition process

   Pivot is 5 (last element). Elements less than 5 move left, others right.

2. Step 2: Rearrange elements around pivot

   Elements less than 5 are 1 only (index 4). Swap it with index 0: [1, 7, 8, 9, 10, 5]. Then swap index 1 (7) with high (5): [1, 5, 8, 9, 7, 10].

3. Final Answer:

   [1, 5, 8, 9, 7, 10] -> Option A

4. Quick Check:

   Pivot 5 placed correctly after smaller elements [OK]

Hint: Pivot last; smaller left, pivot placed next [OK]

Common Mistakes:

• Assuming full sort after one partition
• Swapping elements incorrectly
• Misplacing pivot index