Quick Sort Algorithm in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA C#

void Swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[1];
    arr[j] = temp;
}

Drag options to blanks, or click blank then click option'

A[j]

B[i]

C(j)

D(i)

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses instead of square brackets for array indexing.

Swapping with wrong indices.

To swap elements at positions i and j, we assign arr[i] = arr[j]. The correct syntax uses square brackets for indexing.

2fill in blank

medium

Complete the code to choose the pivot element as the last element of the array segment.

DSA C#

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

Drag options to blanks, or click blank then click option'

A[low]

B(low)

C(high)

D[high]

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses instead of square brackets for array indexing.

Choosing the wrong pivot index.

The pivot is chosen as the last element in the current segment, which is arr[high].

3fill in blank

hard

Fix the error in the recursive QuickSort call to sort the left partition.

DSA C#

void QuickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = Partition(arr, low, high);
        QuickSort(arr, low, [1]);
        QuickSort(arr, pi + 1, high);
    }
}

Drag options to blanks, or click blank then click option'

Api - 1

Bpi

Clow

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Using pi instead of pi - 1 causes infinite recursion.

Using wrong indices for recursive calls.

To sort the left partition, QuickSort should be called with low and pi - 1 as boundaries.

4fill in blank

hard

Fill both blanks to complete the base case and the recursive call for the right partition.

DSA C#

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

Drag options to blanks, or click blank then click option'

Alow

Bhigh

Cpi

Dpi - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using pivot indices in the base case condition.

Incorrect comparison operators.

The base case checks if low is less than high to continue sorting.

5fill in blank

hard

Fill the blanks to create a dictionary that maps each element to its square if the element is greater than 2.

DSA C#

var result = new Dictionary<int, int>();
foreach (var num in arr) {
    if (num [1] 2) {
        result[num] = num [2] num;
    }
}
return result;

Drag options to blanks, or click blank then click option'

A>

B*

C<

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using < instead of > in the condition.

Using + instead of * for squaring.

We check if num > 2, then assign result[num] = num * num.

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