Hello! In this session, we will take a closer look at the Quick Sort algorithm using C++. Quick Sort is a sorting algorithm that frequently appears in various programming interviews and algorithm exams. In this article, we will master Quick Sort through its concept, implementation, time complexity, and example problems.<\/p>\n
Quick Sort is a type of divide-and-conquer algorithm that efficiently sorts data. The algorithm works as follows:<\/p>\n
There are several methods for selecting a pivot. Common methods include:<\/p>\n
It is important to choose an appropriate method as the pivot selection significantly impacts sorting performance.<\/p>\n
The average time complexity of Quick Sort is O(n log n). However, in the worst-case scenario (e.g., when the array is already sorted), performance can degrade to O(n\u00b2). Good pivot selection methods are important to prevent this.<\/p>\n
Now, let\u2019s solve a problem using Quick Sort. Solve the following problem:<\/p>\n
\nProblem:<\/strong> Given an array of integers, sort the array in ascending order using the Quick Sort algorithm.
\nInput:<\/strong>[10, 7, 8, 9, 1, 5]<\/code>
\nOutput:<\/strong>[1, 5, 7, 8, 9, 10]<\/code>\n<\/p><\/blockquote>\n3. Problem Solving Process<\/h2>\n
The steps to solve the problem are as follows:<\/p>\n
3.1 Algorithm Implementation<\/h3>\n
First, let’s implement the Quick Sort algorithm in C++.<\/p>\n
\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\n\/\/ Partition function\nint partition(vector<int> &arr, int low, int high) {\n int pivot = arr[high]; \/\/ Select the last element as pivot\n int i = (low - 1); \/\/ Index for smaller elements\n\n for (int j = low; j < high; j++) {\n \/\/ If current element is smaller than the pivot\n if (arr[j] < pivot) {\n i++; \/\/ Increment index of smaller elements\n swap(arr[i], arr[j]); \/\/ Swap elements\n }\n }\n swap(arr[i + 1], arr[high]); \/\/ Swap the pivot to the correct location\n return (i + 1); \/\/ Return the new index of the pivot\n}\n\n\/\/ Quick Sort function\nvoid quickSort(vector<int> &arr, int low, int high) {\n if (low < high) {\n \/\/ Perform partition and get the pivot index\n int pi = partition(arr, low, high);\n\n quickSort(arr, low, pi - 1); \/\/ Sort the left sub-array\n quickSort(arr, pi + 1, high); \/\/ Sort the right sub-array\n }\n}\n\n\/\/ Main function\nint main() {\n vector<int> arr = {10, 7, 8, 9, 1, 5};\n int n = arr.size();\n\n quickSort(arr, 0, n - 1);\n\n cout << \"Sorted array: \";\n for (int i = 0; i < n; i++) {\n cout << arr[i] << \" \";\n }\n return 0;\n}\n <\/code><\/pre>\nThe code above implements the Quick Sort algorithm. The
partition<\/code> function divides the given array based on the pivot, and thequickSort<\/code> function performs sorting recursively.<\/p>\n3.2 Code Explanation<\/h3>\n
Let\u2019s take a step-by-step look at the code:<\/p>\n
\n
partition<\/code> function:\n\n
- Selects the last element as the pivot.<\/li>\n
- Divides the given array based on the pivot.<\/li>\n
- Moves the pivot to its sorted position.<\/li>\n
- Returns the new pivot index.<\/li>\n<\/ul>\n<\/li>\n
quickSort<\/code> function:\n\n
- Checks the base condition and makes recursive calls for sub-arrays.<\/li>\n
- Performs the process of “finding the pivot and sorting” for each sub-array.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n
3.3 Code Execution Result<\/h3>\n
When the code is executed, it produces the following output:<\/p>\n
Sorted array: 1 5 7 8 9 10<\/code><\/p>\nWe can confirm that the sorted array is printed correctly. This indicates that Quick Sort has been performed successfully.<\/p>\n
4. Additional Considerations<\/h2>\n
There are several additional considerations when using Quick Sort:<\/p>\n
4.1 Stability<\/h3>\n
Quick Sort is an unstable sorting algorithm. That is, the relative order of elements with the same value is not guaranteed after sorting. If stability is required, other sorting algorithms (e.g., Merge Sort) should be considered.<\/p>\n
4.2 Memory Usage<\/h3>\n
Quick Sort operates recursively, using memory on the call stack. In the worst case, it can have O(n) space complexity, but on average, it is O(log n).<\/p>\n
5. Quick Sort vs Other Sorting Algorithms<\/h2>\n
Compared to other sorting algorithms, Quick Sort has the following advantages and disadvantages:<\/p>\n
5.1 Advantages<\/h3>\n
\n
- Typically offers fast performance with an average of O(n log n).<\/li>\n
- Requires less additional memory space.<\/li>\n
- Supports recursive and intuitive implementations.<\/li>\n<\/ul>\n
5.2 Disadvantages<\/h3>\n
\n
- Can have O(n\u00b2) performance in the worst case.<\/li>\n
- Is an unstable sort and the relative order of identical elements may change.<\/li>\n<\/ul>\n
6. Conclusion<\/h2>\n
In this article, we implemented the Quick Sort algorithm using C++ and explored various aspects. Quick Sort is an efficient and widely used sorting algorithm, making it a common topic in algorithm exams or coding interviews. Understanding and implementing Quick Sort will greatly aid in coding tests.<\/p>\n
Finally, try solving more problems using Quick Sort. Considering various cases will help deepen your understanding of this algorithm.<\/p>\n