Implementation of QuickSort in C++
QuickSort is a well-known sorting algorithm that implements the divide-and-conquer technique. It operates by selecting one of the array’s pivot elements and separating the other components into two subarrays based on whether they are smaller or bigger than the pivot. After that, the subarrays are sorted recursively until the entire array is sorted.
Time complexity
On average, this approach has a time complexity of , where is the number of array items. In the worst-case situation, when the pivot is repeatedly picked incorrectly, the time complexity can fall below . Because of the recursive calls, the space complexity becomes .
Code
#include <iostream>// Swapping elementsvoid swap_elements(int &number_1, int &number_2){int temp_num = number_1;number_1 = number_2;number_2 = temp_num;}// Portioning the array and then returning index of the pivotint partition_array(int array_value[], int lower_value, int higher_value){int pivot_value = array_value[higher_value]; // Choose the rightmost element for the pivotint i_1 = (lower_value - 1);for (int j_1 = lower_value; j_1 <= higher_value - 1; j_1++){if (array_value[j_1] <= pivot_value){i_1++;swap_elements(array_value[i_1], array_value[j_1]); // Swap array_value[i] and arrar_value[j]}}swap_elements(array_value[i_1 + 1], array_value[higher_value]);return (i_1 + 1); // Return the partition index}// Performing Quick-Sortvoid quick_sort(int array_value[], int lower_value, int higher_value){if (lower_value < higher_value){int pivot_index = partition_array(array_value, lower_value, higher_value); // Partition the array// Recursive calls to sort the sub-arraysquick_sort(array_value, lower_value, pivot_index - 1);quick_sort(array_value, pivot_index + 1, higher_value);}}// Printing arrayvoid print_array(int array_value[], int size_of_array){for (int i = 0; i < size_of_array; i++){std::cout << array_value[i] << " ";}std::cout << std::endl;}int main(){int array_values[] = { 9, 2, 5, 1, 7, 4, 8, 3 };int size_of_array = sizeof(array_values) / sizeof(array_values[0]);std::cout << "Original array: ";print_array(array_values, size_of_array);quick_sort(array_values, 0, size_of_array - 1);std::cout << "Sorted array: ";print_array(array_values, size_of_array);return 0;}
Code explanation
-
Lines 4–9: The
swap_elements()function takes two integers as input and swaps their values. It is used to exchange components during the splitting step of QuickSort. -
Lines 12–28: The function
partition_array()accepts an arrayarray_value, the lowest indexlower_value, and the highest indexhigher_valueas parameters. Thepivot_valueelement is chosen as the rightmost element,array_value[higher_value]. It rearranges the array so that all elements less than or equal to the pivot come before it, and all elements greater than the pivot come after it. It returns the pivot element’s index after partitioning. -
Lines 31–41: The function
quick_sort()performs the QuickSort algorithm. It takes an arrayarray_value, the lowest indexlower_value, and the highest indexhigher_value. If the low index is less than the high index, it calls thepartition_array()function to partition the array and get the pivot index. It recursively callsquick_sort()on the subarray before the pivot (fromlower_valuetopivot_index - 1) and the subarray after the pivot (frompivot_index + 1tohigher_value). -
Lines 44–52: It prints all the elements of the array separated by a space and ends with a new line.
-
Lines 56–66: It initializes an array
array_valuewith some values. It calculates the size of the array by dividing the totalsize_of_arrayof the array by thesize_of_arrayof a single element. It then prints the original array, performs quick sort on the array, and prints the sorted array.
