{"id":794,"date":"2025-11-21T08:53:41","date_gmt":"2025-11-21T03:23:41","guid":{"rendered":"https:\/\/codexplained.in\/?p=794"},"modified":"2025-11-21T08:53:41","modified_gmt":"2025-11-21T03:23:41","slug":"quick-sort-using-recursion","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=794","title":{"rendered":"Quick Sort using Recursion"},"content":{"rendered":"\n

Quick Sort is an efficient sorting algorithm that uses the “divide and conquer” approach. The algorithm selects a “pivot” element from the array, partitions the array into two sub-arrays such that elements less than the pivot go to the left of it and elements greater than the pivot go to the right, and then recursively applies the same strategy to both sub-arrays.<\/p>\n\n\n\n

Here\u2019s the step-by-step explanation along with a C program that implements Quick Sort.<\/p>\n\n\n\n

Steps of Quick Sort:<\/strong><\/p>\n\n\n\n

    \n
  1. Choose a Pivot<\/strong>: A pivot element is selected. Commonly, the last element in the array is used.<\/li>\n<\/ol>\n\n\n\n

    2. Partitioning<\/strong>: Re-arrange the array such that:<\/p>\n\n\n\n

      \n
    • All elements less than the pivot are moved to the left.<\/li>\n\n\n\n
    • All elements greater than the pivot are moved to the right.<\/li>\n<\/ul>\n\n\n\n

      3. Recursive Sorting<\/strong>: Recursively apply the same steps to the sub-arrays on the left and right of the pivot.<\/p>\n\n\n\n

      4.<\/strong> Base Case<\/strong>: The recursion stops when the sub-array has 0 or 1 element, as it is already sorted.<\/p>\n\n\n

      \n #include <stdio.h>\n\n\/\/ Function to swap two elements\nvoid swap(int *a, int *b) \n{\n    int temp = *a;\n    *a = *b;\n    *b = temp;\n}\n\n\/\/ Function to partition the array\nint partition(int arr[], int low, int high) \n{\n    int pivot = arr[high];  \/\/ Choosing the last element as the pivot\n    int i = (low - 1);  \/\/ Index of the smaller element\n\n    for (int j = low; j <= high - 1; j++) \n{\n        \/\/ If the current element is smaller than or equal to the pivot\n        if (arr[j] <= pivot) \n{\n            i++;    \/\/ Increment index of the smaller element\n            swap(&arr[i], &arr[j]);\n        }\n    }\n    swap(&arr[i + 1], &arr[high]);\n    return (i + 1);\n}\n\n\/\/ Recursive QuickSort function\nvoid quickSort(int arr[], int low, int high) \n{\n    if (low < high) \n{\n        \/\/ Partition the array\n        int pi = partition(arr, low, high);\n\n        \/\/ Recursively sort elements before partition and after partition\n        quickSort(arr, low, pi - 1);\n        quickSort(arr, pi + 1, high);\n    }\n}\n\n\/\/ Function to print the array\nvoid printArray(int arr[], int size) \n{\n    for (int i = 0; i < size; i++)\n        printf("%d ", arr[i]);\n    printf("\\n");\n}\n\nint main() \n{\n    int arr[] = {10, 80, 30, 90, 40, 50, 70};\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n    printf("Original array: \\n");\n    printArray(arr, n);\n    \n    quickSort(arr, 0, n - 1);\n    \n    printf("Sorted array: \\n");\n    printArray(arr, n);\n    return 0;\n}\n<\/pre><\/div>\n\n\n
      Detailed Explanation:<\/strong><\/p>\n\n\n\n
        \n
      1. swap function<\/strong>:<\/li>\n<\/ol>\n\n\n\n
          \n
        • Takes two pointers and swaps their values.<\/li>\n\n\n\n
        • It’s used during partitioning to move elements.<\/li>\n<\/ul>\n\n\n\n
          2. partition function<\/strong>:<\/p>\n\n\n\n
            \n
          • Takes the array and divides it into two parts around a pivot.<\/li>\n\n\n\n
          • The pivot is chosen as the last element (arr[high]<\/code>).<\/li>\n\n\n\n
          • It re-arranges the elements so that those smaller than the pivot are to its left, and those larger are to its right.<\/li>\n\n\n\n
          • Returns the index of the pivot after partitioning.<\/li>\n<\/ul>\n\n\n\n
            3. quickSort function<\/strong>:<\/p>\n\n\n\n
              \n
            • This is the main recursive function that sorts the array.<\/li>\n\n\n\n
            • It checks if the current array or sub-array is non-empty (low < high<\/code>), and if so, calls the partition function.<\/li>\n\n\n\n
            • After partitioning, it recursively sorts the left and right sub-arrays.<\/li>\n<\/ul>\n\n\n\n
              4. printArray function<\/strong>:<\/p>\n\n\n\n
                \n
              • This function simply prints the elements of the array.<\/li>\n<\/ul>\n\n\n\n
                5. main function<\/strong>:<\/p>\n\n\n\n
                  \n
                • Initializes an array with unsorted values.<\/li>\n\n\n\n
                • Calls the quickSort<\/code> function to sort the array.<\/li>\n\n\n\n
                • Prints the original and sorted arrays.<\/li>\n<\/ul>\n\n\n\n
                  Output:<\/strong><\/p>\n\n\n
                  \nOriginal array:\n10 80 30 90 40 50 70 \nSorted array:\n10 30 40 50 70 80 90\n\n<\/pre><\/div>\n\n\n
                  Explanation of Output:<\/h3>\n\n\n\n
                    \n
                  • The original array is [10, 80, 30, 90, 40, 50, 70]<\/code>.<\/li>\n\n\n\n
                  • After applying Quick Sort, the sorted array is [10, 30, 40, 50, 70, 80, 90]<\/code>.<\/li>\n<\/ul>\n\n\n\n
                    Time Complexity:<\/h3>\n\n\n\n
                      \n
                    • Best and Average Case<\/strong>: O(n log n)<\/code> where n<\/code> is the number of elements in the array.<\/li>\n\n\n\n
                    • Worst Case<\/strong>: O(n^2)<\/code> occurs when the pivot divides the array into extremely unbalanced partitions (e.g., when the array is already sorted, and the pivot is always the largest\/smallest element).<\/li>\n<\/ul>\n\n\n\n
                      This implementation of Quick Sort effectively handles the sorting of an array using recursion, providing efficient sorting for average cases.<\/p>\n\n\n\n
                      <\/p>\n