Solution Quick Sort

Problem Statement

Write Recursive Approach for Quick Sort

Given an array of integers, sort it in ascending order using the Quick Sort algorithm.

Examples

Solution

The Quick Sort algorithm follows a divide-and-conquer approach to sort an array. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. The base case of the recursion is an array with zero or one element, which is already considered sorted.

The steps of the Quick Sort algorithm can be summarized as follows:

1. Select a pivot element from the array.
2. Partition the array into two sub-arrays: one with elements less than the pivot and one with elements greater than the pivot.
3. Recursively apply Quick Sort to the sub-arrays.
4. Combine the sorted sub-arrays and the pivot element to obtain the final sorted array.

Code

Here is the code for this algorithm:

import java.util.Arrays;
import java.util.List;

public class Solution {

  public List<Integer> sort(List<Integer> array) {
    quickSort(array, 0, array.size() - 1);
    return array;
  }

  private void quickSort(List<Integer> array, int low, int high) {
    if (low < high) {
      int pivotIndex = partition(array, low, high);
      quickSort(array, low, pivotIndex - 1);
      quickSort(array, pivotIndex + 1, high);
    }
  }

  private int partition(List<Integer> array, int low, int high) {
    int pivot = array.get(high);
    int i = low - 1;

    for (int j = low; j < high; j++) {
      if (array.get(j) < pivot) {
        i++;
        int temp = array.get(i);
        array.set(i, array.get(j));
        array.set(j, temp);
      }
    }

    int temp = array.get(i + 1);
    array.set(i + 1, array.get(high));
    array.set(high, temp);

    return i + 1;
  }

  public static void main(String[] args) {
    Solution quickSort = new Solution();

    List<Integer>[] examples = new List[] {
      Arrays.asList(4, 2, 6, 8, 3),
      Arrays.asList(10, 5, 3, 7, 2, 8, 6),
      Arrays.asList(1, 2, 3, 4, 5),
    };

    for (int i = 0; i < examples.length; i++) {
      List<Integer> list = examples[i];
      List<Integer> sortedList = quickSort.sort(list);
      System.out.println("Sorted List #" + (i + 1) + ": " + sortedList);
    }
  }
}

Time and Space Complexity

The time complexity of the Quick Sort algorithm is on average and in the best case, where n is the number of elements in the array. This is because the algorithm divides the array into smaller sub-arrays and recursively sorts them. The worst-case time complexity is when the array is already sorted or almost sorted, and the pivot is chosen poorly. However, the probability of encountering the worst case is low.

The space complexity of the algorithm is on average and in the best case, corresponding to the recursive call stack. In the worst case, the space complexity can be due to the partitioning process. However, the overall space usage is efficient as the algorithm performs in-place sorting by swapping elements within the array.

I'm working on the problem **Solution Quick Sort** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Solution Quick Sort** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Solution Quick Sort**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Solution Quick Sort**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.