An overview,
Recently, WHEN I read some interview questions, I found that many interviews require quick sorting by handwriting. After checking some blogs, I found that others’ writings were not very clear and hard to remember. Therefore, in order to better master this algorithm, I wrote down my learning process in this article. You will learn about quicksort algorithms and how to implement quicksort using Java.
Quicksort is a divide-and-conquer sorting algorithm, in which: 1, the array is divided into two subarrays by selecting a center element from the array. When dividing the array, the elements smaller than the center element are placed in the left subarray, and the elements larger than the center element are placed in the right subarray. 2. The left and right subarrays are divided in the same way, until each subarray contains an element. 3. Finally, group the elements together to form a sorted array.
Pivot element: Sometimes translated as pivot element, primitive, base element, I call it pivot element here
Second, the working principle of quicksort algorithm
1. Select the central element
Quicksort has different variations when selecting the center element at different positions. For example, we can select the first element, the last element, and the median of the three elements at left, right, and center as the center element. In this case, we will select the last element in the array as the center element.
2. Rearrange arrays
Now rearrange the array so that those smaller than the central element are placed on the left and those larger than the central element are placed on the right.
The array is rearranged as follows: 1. The pointer is fixed to the central element, and the central element is compared to the element starting from the first index.
3. Delimit the numerator array
Again, the center element is selected for the left and right subparts respectively, and step 2 is repeated to split the subarray until each subarray has only one element, at which point the array is sorted upward by the quicksort algorithm.
4, quick sort visual illustration description
You can use the following illustration to understand how the quicksort algorithm works.
Pseudo code of quicksort algorithm
1. Pseudo-code description
quickSort(array, leftmostIndex, rightmostIndex)
if (leftmostIndex < rightmostIndex)
pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
quickSort(array, leftmostIndex, pivotIndex - 1)
quickSort(array, pivotIndex, rightmostIndex)
partition(array, leftmostIndex, rightmostIndex)
set rightmostIndex as pivotIndex
storeIndex <- leftmostIndex - 1
for i <- leftmostIndex + 1 to rightmostIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1
Copy the codeFour, Java implementation of quicksort
Java code for quicksort is as follows:
public class QuickSort {
public static int partition(int[] array, int low, int high) {
// take the last element as the center element
int pivot = array[high];
// Define a pointer larger than the center element, pointing first to the first element
int pointer = low;
// Iterate over all the elements in the array, placing those larger than the central element on the right and those smaller than the central element on the left
for (int i = low; i < high; i++) {
if (array[i] <= pivot) {
// Swap an element smaller than the center element with the element to which the pointer points
// If the first element is smaller than the central element, the position is swapped between itself and the pointer, and the index moves down one bit
// If the element is larger than the central element, the index is moved down and the pointer points to the larger element until it finds an element smaller than the central element and switches positions, the pointer is moved down
int temp = array[i];
array[i] = array[pointer];
array[pointer] = temp;
pointer++;
}
System.out.println(Arrays.toString(array));
}
// Swap the center element with the element to which the pointer points
int temp = array[pointer ];
array[pointer] = array[high];
array[high] = temp;
return pointer;
}
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// Get the position of the delimiter array
int position = partition(array, low, high);
// Left subarray recursive call
quickSort(array, low, position -1);
// Recursive call to the right subarray
quickSort(array, position + 1, high); }}public static void main(String[] args) {
int[] array = {6.72.113.11.23};
quickSort(array, 0, array.length -1);
System.out.println("Sorted results."); System.out.println(Arrays.toString(array)); }}Copy the codeThe sorting process results in the following:
[6, 72, 113, 11, 23] [6, 72, 113, 11, 23] [6, 11, 113, 72, 23] 72, 113] results of sorting [6, 11, 23, 72, 113]Copy the codeFrom this sort result we can see the whole sorting process.
5. Complexity of quicksort
| Time complexity | O said |
|---|---|
| The best | Order n log n. |
| The worst | Order n times n. |
| On average, | Order n log n. |
| Spatial complexity | Order log n. |
| The stability of | unstable |
1. Time complexity
- Worst-case complexity [big-o] :
Occurs when the selected center element is the largest or smallest element, which results in the center element being at the very end of the sorted array. One subarray is always empty while the other subarray contains elements. Therefore, quicksort is called only on this subarray, and the quicksort algorithm has better performance for scattered data.
- Best-case complexity [big-o] :
This happens when the central element is always the middle element or near the middle element.
- Average complexity [big-O] :
Occurs in the absence of the above conditions.
2. Spatial complexity
The space of quicksort is order log n.
Six, quicksort applications
The Quicksort algorithm is used in the following cases
- Programming languages lend themselves well to recursion
- Time complexity is important
- Spatial complexity is important