Sorting - Quick sort

Updated to 1 day ago

general situation

Quick sort is an alternative to thebubbling sortAn improvement of the Quick sort was proposed by C. A. R. Hoare in 1960.

Algorithmic thinking

The data to be sorted by a trip sort is divided into two independent parts, one of which all the data are smaller than the other part of all the data, and then the two parts of the data according to the method of fast sorting, the whole sorting process can be carried out recursively, so as to achieve the whole data into an ordered sequence.

The quick sort algorithm achieves sorting by multiple comparisons and exchanges, and its sorting process is as follows:

1, first set a cut-off value, through the cut-off value will be divided into two parts of the array.

2, will be greater than or equal to the cut-off value of the data concentrated to the right side of the array, less than the cut-off value of the data concentrated to the left side of the array. At this point, the left part of the elements are less than or equal to the cut-off value, while the right part of the elements are greater than or equal to the cut-off value.

3, then, the left and right data can be sorted independently. For the left side of the array data, and can take a cut-off value, the part of the data will be divided into the left and right parts, the same on the left side of the smaller values placed, the right side of the larger values placed. The right side of the array data can also be done similarly.

4, repeat the above process, you can see that this is a recursive definition. By recursively sorting the left part of the order, and then recursively sort the right part of the order. When the left and right parts of the data sorting is completed, the entire array sorting is also completed.

In a nutshell, it's Dig and Fill + Partitioning.

graphical algorithm

Quick sort has three main parameters, left is the start address of the interval, right is the end address of the interval, and Key is the current start value.

We select a record (usually the first) from the sequence of records to be sorted as the base element (called key) key=arr[left], and then set two variables, left pointing to the leftmost part of the array and right pointing to the rightmost part of the data.

initial step

key first compare with arr[right], if arr[right]<key then arr[left]=arr[right] put this number which is smaller than key to the left, if arr[right]>key then we just need to put right--, after right--, then we take arr[ right] with key until arr[right]<key exchanges elements.

second step

If the case of arr[right]<key exists on the right side, put arr[left]=arr[right], next, it will turn to the left side, take arr[left ] and compare it with key, if arr[left]>key,then put arr[right]=arr[left], if arr[ left]<key, then just +++ the left, and then do the comparison of arr[left] to key.

third step

Then move RIGHT to repeat the above steps.

fourth step

Finally we get {23 58 13 10 57 62} 65 {106 78 95 85}, and then we do the same for the left child series and the right child series. You end up with an ordered series.

{23 58 13 10 57 62} 65 {106 78 95 85}

{10 13} 23 {58 57 62} 65 {85 78 95} 106

10 13 23 57 58 62 65 78 85 95 106

Animation Showcase

We borrowed the Five Minutes to Learn Algorithms animated gif thanks to Five Minutes to Learn Algorithms.

First, manipulate all the numbers in the array
In all the numbers to choose a number as the base of the sort (pivot), pivot is usually randomly selected, here for the convenience of demonstration, we choose the rightmost number as pivot
After selecting the pivot, choose the leftmost number in the operation array to be labeled as the left marker and the rightmost number as the right marker.
Move the left marker to the right
Stop moving when the left marker reaches more than the number of pivots.
Here, 8 > 6 , so stop moving
Then move the right marker to the left
Stop moving when the right marker reaches a number less than pivot.
Here, 4 > 6, so stop moving.
When the left and right markers stop, change the number of markers
Thus, the role of the left marker is to find a number greater than the pivot, and the role of the right marker is to find a number less than the pivot.
By swapping numbers, you can collect the set of numbers smaller than pivot on the left side of the array and the set of numbers larger than pivot on the right side.
After the exchange, keep moving the left marker.
Here, 9 > 6, so stop moving.
Then move the right marker to the left
When the right marker collides with the left marker, it also stops moving.
If the left and right markers are stopped and both are in the same position, exchange this number with the number of the pivot.
This completes the first operation.
Everything less than 6 is to the left of 6, and everything greater than 6 is to the right of 6.
Then recursively perform the same operation on both parts of the split
Done. Quick sort.

Algorithm Performance

time complexity

ideal situation

If it's ideal enough, then weExpect to split the array into two equal parts every time.If we follow this ideal case of partitioning, we end up with a fully binary tree. If we sort n numbers, then the depth of the tree is $log_{2}n+1$ If we set the elapsed time for comparing n numbers to T(n), then we can get the following equation

T(n) ≤ 2T(n/2) + n，T(1) = 0  
T(n) ≤ 2(2T(n/4)+n/2) + n = 4T(n/4) + 2n  
T(n) ≤ 4(2T(n/8)+n/4) + 2n = 8T(n/8) + 3n  
......
T(n) ≤ nT(1) + (log2n)×n = O(nlogn)

worst case scenario

And in the worst case, the tree is a completely skewed tree with only a left or right half. At this point our number of comparisons becomes $\sum_{i=1}^{n-1}(n-i)=(n-1)+(n-2)+\cdots +1=\frac{n*(n-1)}{2}=O(n^{2})$

(math.) space complexity

in-situ ordering

The space usage of the in-place fast row is the use of stack space caused by recursion, which in the best case is recursivetimes, so the space complexity is $O(long_{2}n)$ In the worst case scenario, it's recursiven-1 times, so the space complexity is O(n) 。

Non-in situ sorting

For non-in situ sorting, each recursion declares an additional space totaling n, so the space complexity becomes n times that of in situ sorting, i.e., best case $O(nlog_{2}n)$ Worst case scenario。

stability

precarious。

code implementation

C and C++

void QuickSort(int array[], int low, int high) {
    int i = low;
    int j = high;
    if(i >= j) {
        return;
    }

    int temp = array[low];
    while(i != j) {
        while(array[j] >= temp && i < j) {
            j--;
        }
	while(array[i] <= temp && i < j) {
            i++;
        }
	if(i < j) {
            swap(array[i], array[j]);
        }
    }

    //refer totempPut yourself in your place，（(prefix indicating ordinal number, e.g. first, number two etc)ilocation）
    swap(array[low], array[i]);
    QuickSort(array, low, i - 1);
    QuickSort(array, i + 1, high);
}

Java

public static int[] qsort(int arr[],int start,int end) {        
    int pivot = arr[start];        
    int i = start;        
    int j = end;        
    while (i<j) {            
        while ((i<j)&&(arr[j]>pivot)) {                
            j--;            
        }            
        while ((i<j)&&(arr[i]<pivot)) {                
            i++;            
        }            
        if ((arr[i]==arr[j])&&(i<j)) {                
            i++;            
        } else {                
            int temp = arr[i];                
            arr[i] = arr[j];                
            arr[j] = temp;            
        }        
    }        
    if (i-1>start) arr=qsort(arr,start,i-1);        
    if (j+1<end) arr=qsort(arr,j+1,end);        
    return (arr);    
}

Python

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while i<=right:
        if arr[i]<arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr, pivot, index-1)
    return index-1

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left, (int, float)) else left
    right = len(arr)-1 if not isinstance(right, (int, float)) else right

    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr