Contents
Definition
Quick sort is a very efficient algorithm that leverages the divide-and-conquer principle to sort a data structure. The calculated performance complexity of Quick Sort as follows;
- Best Case: O(n log n),
- Average Case: O(n log n),
- Worse Case: O(n2), reason: the algorithm will select only one element in each iteration
- Space Complexity: O(log n).
Terminology
Furthermore, for starters, it will be a good practice to apprehend the terms in this algorithm;
- Pivot: A reference element that is used as a line whose left and rights elements are divided. There are a few Quick Sort implementations, whose suggestions vary from picking the Pivot from the beginning, middle, end or randomly,
- Partition: It is a practice that swaps elements on the left and right ends, while using the Pivot as a reference. By the end of Partitioning, a partition point for the next divided subsets(those will be divided also) is returned,
- Left Pointer: A pointer or an index value that traverses on the last/low/left subset of the designated array,
- Right Pointer: A pointer or an index value that traverses on the last/low/right subset of the designated array,
Internal of the Algorithm
In every step, the Quick Sort divides the array to subsets and aims to collect the lower numbers on the left side, the greater numbers on the right side of the pivot in an ascending format. Let’s look at a glance how the code performs the operation;
- Choosing a Pivot,
- Beginning the partitioning by swapping the lower elements on the left, greater elements on the right side of the pivot,
- Apply partitioning on the left side and later on the right side.
Code
you can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms