Understand Quick Sort Algorithm Problem

Problem Name: Quick Sort Algorithm
Problem Description:

šŸš€ Quick Sort Algorithm Explained

Quick Sort is a divide-and-conquer algorithm that efficiently sorts an array by selecting a pivot element and partitioning the other elements into two groups:

  • Smaller than the pivot
  • Greater than the pivot

This process is recursively applied to both groups until the entire array is sorted.

šŸ“Œ Steps of Quick Sort

  1. Choose a Pivot: Pick an element from the array (commonly the last, first, or a random element).
  2. Partitioning: Rearrange the array so that elements smaller than the pivot come before it, and elements greater come after.
  3. Recursion: Apply Quick Sort on the left and right sub-arrays.
  4. Base Case: When the sub-array has 0 or 1 element, it's already sorted.

Quick Sort: Time Complexity & Key Takeaways

Time Complexity Table

ScenarioTime ComplexityDescription
Best CaseO(n log n)Occurs when the pivot divides the array into two nearly equal parts.
Average CaseO(n log n) Typically achieved with balanced partitions during recursion.
Worst CaseO(nĀ²)Happens when the pivot is the smallest or largest element each time, leading to highly unbalanced partitions (e.g., already sorted array).

Key Takeaways

  • Divide and Conquer: Quick Sort works by breaking the problem into smaller sub-problems using a pivot to partition the array.
  • Efficiency: It generally performs very well with an average-case time complexity of O(n log n), making it suitable for large datasets.
  • Worst Case Pitfall: Poor pivot selection (e.g., always picking the smallest or largest element) can degrade its performance to O(nĀ²).
  • In-Place Sorting: Quick Sort can be implemented in-place, requiring little additional memory.
  • Not Stable: The algorithm does not maintain the relative order of equal elements.

Quick Sort remains a popular choice due to its average-case efficiency, despite potential pitfalls with worst-case performance.

Category:
  • Searching & Sorting
  • Backtracking
Programming Language:
  • Java
Reference Link:

https://drawtocode.vercel.app/problems/quick-sort-algorithm

Online IDE

Scroll down for output
Java
Output:
Loading component...
Loading component...
Tracking code (View only. In case you want to track the code, click this button):
Main Function:
INPUT: [8, 3, 5, 4, 2, 7, 6, 1]
OUTPUT: [1, 2, 3, 4, 5, 6, 7, 8]
public static void main(String args[]){
 int arr[] = { 12, 11, 13, 5, 6, 7 };
 System.out.println("Given array is");
printArray(arr);
quickSort( arr, 0, 5);
System.out.println("\nSorted array is");
printArray(arr);
}//function end
Helper Function:
 public static 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);
}//If End
}//function end
Utility Functions and Global variables:
private static 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;
}//If End
 }//Loop End
 int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}//function end
    static void printArray(int[] arr){
        for (int val : arr) {
            System.out.print(val + " ");
}//Loop End
System.out.println();
} // Function End
Privacy Policy | About