Introduction to Quick Sorting

Quicksort (English: Quicksort), also known as partition-exchange sort, divides the sorted data into two separate parts by one-time sorting. All the data in one part are smaller than all the data in the other part. Then, according to this method, the two parts of the data are sorted quickly, and the whole sorting process can be recursive. In this way, the whole data can be transformed into an ordered sequence.

2. The Principle of Quick Sorting

1. Picking out an element from a sequence is called a pivot.
2. Reordering sequence, all elements smaller than the benchmark are placed in front of the benchmark, and all elements larger than the benchmark are placed behind the benchmark (the same number can reach either side). After the partition ends, the benchmark is in the middle of the sequence. This is called partition operation.
3. recursive sorting ranks the subordinate sequences of elements smaller than the base value and those larger than the base value.

4. The bottom case of recursion is that the size of the sequence is zero or one, that is, it's always sorted. Although recursive, the algorithm always ends, because in each iteration, it places at least one element at its last position.

3. Steps for Quick Sorting

1. Set two variables i, j, sort At the beginning: i=0, j=N-1;
2. With the first array element as the key data, the key is assigned, that is, key=A[0].
3. Search forward from j, that is, search forward from back (j--), find the first value A[j], which is less than key, and exchange the values of A[j] and A[i];
4. Search backward from i, i. e. search backward from front (i++), find the first A[i] larger than the key, and exchange the values of A[i] and A[j].
5. Repeat steps 3 and 4 until i=j; (In steps 3 and 4, no qualified value is found, that is, A[j] in step 3 is not less than key, and A[i] in step 4 is not more than key, change the value of J and I so that j=j-1, i=i+1, until it is found. Find the value that meets the requirement, and the position of I and j pointers will remain unchanged when swapping. In addition, the process of i==j must be just when I + or J - is completed, which will end the cycle.

Graphics of Quick Sorting

5. Implementation of python code for quick sorting

def quick_sort(alist,start,end):
    # The condition of recursion is that there must be an exit for recursion.
    if start>=end:
        return
    
    # Set the starting element to be the reference element to look for
    k = alist[start]
    # set variable i Record search from left to right
    i = start
    # set variable j Record search from right to left
    j = end
    
    # i<j The explanation is not yet available. i and j We haven't met yet. We need to continue comparing.
    while i<j:
        
        # i<j,And if the data at this time are all better than k Words (right-to-left comparison)
        while i<j and alist[j]>=k:
            # j Let's go down and look straight ahead.
            j -= 1
        # Out of while Loops indicate that the data to be exchanged has been found.
        temp = alist[j]
        alist[j] = alist[i]
        alist[i] = temp
        
        # i<j And if the data at this time are all better than k Small words (from left to right to comparison)
        while i<j and alist[i]<=k:
            # i Incrementally, always look back
            i += 1
        # Out of while Loops indicate that the data to be exchanged has been found.
        temp = alist[j]
        alist[j] = alist[i]
        alist[i] = temp
    # Then continue sorting the data on the left using recursion
    quick_sort(alist,start,i-1)
    # Then continue sorting the data on the right using recursion
    quick_sort(alist,i+1,end)

#Create an array
numlist = [6,1,2,7,9,5,4,3,10,8]
print("Before sorting:%s"%numlist)
quick_sort(numlist,0,len(numlist)-1)
print("After sorting:%s"%numlist)

The results are as follows:

Before sorting: [6, 1, 2, 7, 9, 5, 4, 3, 10, 8]
After sorting: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

6. Implementation of C Language Code for Quick Sorting

#include <stdio.h>

// Creating Quick Sort Functions
void quick_sort(int arr[],int start,int end)
{
    // The condition of recursion is that there must be an exit for recursion.
    if (start>=end)
    {
        return;
    }
    // Set the starting element to be the reference element to look for
    int k = arr[start];
    // set variable i Record search from left to right
    int i = start;
    // set variable j Record search from right to left
    int j = end;
    
    // i<j The explanation is not yet available. i and j We haven't met yet. We need to continue comparing.
    while (i<j)
    {
        // i<j,And if the data at this time are all better than k Words (right-to-left comparison)
        while (i<j&&arr[j]>=k)
        {
            // # j decreases and goes straight ahead.
            j--;
        }
        // Out of while Loops indicate that the data to be exchanged has been found.
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        // i<j And if the data at this time are all better than k Small words (from left to right to comparison)
        while (i<j&&arr[i]<=k)
        {
            // i Incrementally, always look back
            i++;
        }
        // Out of while Loops indicate that the data to be exchanged has been found.
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // Then continue sorting the data on the left using recursion
    quick_sort(arr, start, i-1);
    // Then continue sorting the data on the right using recursion
    quick_sort(arr, i+1, end);
}

int main(int argc, const char * argv[])
{
    // Quick sort function declaration
    void quick_sort(int arr[],int start,int end);
    // Create arrays that need to be sorted
    int array[] = {6,1,2,7,9,5,4,3,10,8};
    // Call Quick Sort
    quick_sort(array, 0, 9);
    // Print Verification
    for (int i=0; i<10; i++)
    {
        printf("%d ",array[i]);
    }
    return 0;
}

The results are as follows:

1 2 3 4 5 6 7 8 9 10

7. Time Complexity of Quick Sorting

• Optimal time complexity: O(nlogn)
• Worst-case time complexity: O(n2)

8. Stability of Quick Sorting

Quick sorting is not a stable sorting algorithm, that is, the relative positions of multiple identical values may change at the end of the algorithm.