❮ Zookeeper Leader Android Tutorial Alertdialog ❯

Quick Sort

Category Programming Techniques

Quick sort is often used due to its efficiency among sorting methods with the same O(N*logN) complexity, making it one of the faster options. Its popularity is also due to the practicality of its divide-and-conquer approach, which is why it is frequently encountered in software company interviews, including those of renowned IT firms like Tencent and Microsoft, as well as in various programming exams such as software certification and graduate entrance exams.

Overall,默写 quick sort directly from memory can be quite challenging. Based on my understanding, I have provided a colloquial explanation of quick sort to aid comprehension and facilitate quick mastery.

Quick sort was proposed by C.R.A. Hoare in 1962 and is a type of partition-exchange sort. It employs a divide-and-conquer strategy, commonly referred to as the Divide-and-Conquer Method.

The basic idea of this method is:

1. Start by selecting a number from the array as the pivot.
1. During the partitioning process, place all numbers greater than this pivot to its right, and all numbers less than or equal to it to its left.
1. Repeat the second step for the left and right sub-arrays until each sub-array contains only one number.

Although quick sort is referred to as a divide-and-conquer method, the term "divide-and-conquer" does not fully capture all the steps of quick sort. Therefore, I further explain quick sort as a combination of "dig-hole-fill-number" and divide-and-conquer:

Let's look at an example first, and the definition will be provided later (it's best to summarize the definition in your own words, as this will help with coding implementation).

Consider an array with the first number as the pivot.

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | 72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |

Initially, i = 0; j = 9; X = a[i] = 72

Since a[0] has been saved to X, it can be thought of as a hole in the array a[0], which can be filled with other data.

Start from j and find a number less than or equal to X. When j = 8, it meets the condition, so dig out a[8] and fill it into the previous hole a[0]. a[0] = a[8]; i++; Now, a[0] is filled, but a new hole a[8] is formed. To fill this new hole, find a number greater than X from i onwards. When i = 3, it meets the condition, so dig out a[3] and fill it into the previous hole a[8] = a[3]; j--;

The array becomes:

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | 48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 88 | 85 |

i = 3; j = 7; X = 72

Repeat the above steps, first finding from the back to the front, then from the front to the back.

Find from j to the front, when j = 5, it meets the condition, dig out a[5] and fill it into the previous hole, a[3] = a[5]; i++;

Find from i to the back, when i = 5, i == j, exit.

At this point, i = j = 5, and a[5] is the hole dug last time, so fill X into a[5].

The array becomes:

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | 48 | 6 | 57 | 42 | 60 | 72 | 83 | 73 | 88 | 85 |

It can be seen that the numbers before a[5] are all smaller, and the numbers after a[5] are all larger. Therefore, repeat the above steps for the two sub-intervals a[0…4] and a[6…9].

Summarize the "dig-hole-fill-number" method:

1. i = L; j = R; Dig out the pivot number to form the first hole a[i].
1. j--, find a number smaller than it from back to front, and dig out this number to fill the previous hole a[i].
1. i++, find a number larger than it from front to back, and dig out this number to fill the previous hole a[j].
1. Repeat steps 2 and 3 until i == j, then fill the pivot number into a[i].

It is easy to implement the "dig-hole-fill-number" code following this summary:

int AdjustArray(int s[], int l, int r) // Return the position of the adjusted pivot
{
    int i = l, j = r;
    int x = s[l]; // s[l] is the first hole
    while (i < j)
    {
        // Find a number less than x from right to left to fill s[i]
        while(i < j && s[j] >= x) 
            j--;  
        if(i < j) 
        {
            s[i] = s[j]; // Fill s[j] into s[i], and s[j] becomes a new hole
            i++;
        }

        // Find a number greater than or equal to x from left to right to fill s[j]
        while(i < j && s[i] < x)
            i++;  
        if(i < j) 
        {
            s[j] = s[i]; // Fill s[i] into s[j], and s[i] becomes a new hole
            j--;
        }
    }
    // Exit when i equals j. Fill x into this hole.
    s[i] = x;

    return i;
}

Next, write the divide-and-conquer code:

void quick_sort1(int s[], int l, int r)
{
    if (l < r)
    {
        int i = AdjustArray(s, l, r); // Adjust s[] using the dig-hole-fill-number method
        quick_sort1(s, l, i - 1); // Recursive call
        quick_sort1(s, i + 1, r);
    }
}

This code is not very concise, so let's combine and tidy it up:

// Quick sort
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        // Swap(s[l], s[(l + r) / 2]); // Swap the middle number with the first number, see note 1
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // Find the first number less than x from right to left
                j--;  
            if(i < j) 
                s[i++] = s[j];

            while(i < j && s[i] < x) // Find the first number greater than or equal to x from left to right
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // Recursive call
        quick_sort(s, i + 1, r);
    }
}

There are many improved versions of quick sort, such as randomly selecting the pivot, or directly using another sorting method when the data within the interval is small to reduce recursive depth. Interested readers can delve deeper into this topic.

Note 1: Some books use the middle number as the pivot. To implement this, simply swap the middle number with the first number.

Author: MoreWindows

Original: https://blog.csdn.net/morewindows/article/details/6684558

#

** 阿拉蕾

* 271**[email protected]

C# version, I'll provide it.

namespace{
    class Program{
        static void QuickSort(int[] dataArray, int left, int right){
            if(left < right){
                int x = dataArray[left];
                int i = left;
                int j = right;
                while(true && i < j){
                    while(true && i < j){
                        if(dataArray[j] <= x){
                            dataArray[i] = dataArray[j];
                            break;
                        }else{
                            j--;
                        }
                    }
                    while(true && i < j){
                        if(dataArray[i] > x){
                            dataArray[j] = dataArray[i];
                            break;          
                        }else{
                            i++;
                        }
                    }
                }
                dataArray[i] = x;
                QuickSort(dataArray, left, i - 1);
                QuickSort(dataArray, i + 1, right);
            }
        }
        static void Main(string[] args){
            int[] data = new int[]{72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
            Console.WriteLine("Quick sort order:");
            QuickSort(data, 0, data.Length - 1);
            foreach(var item in data){
                Console.Write(item + " ");
            }
            Console.ReadLine();
        }
    }
}

** 阿拉蕾

* 271**[email protected]

** 一只可爱的野指针

* 252**[email protected]

Java colloquial explanation version, I'll provide it.

//公众号：一只快活的野指针
public class Quick {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6}; // Directly copy the array
        quick_sort(arr, 0, arr.length - 1);    
        print(arr);
    }
    private static int get_mid(int arr[], int left, int right){
        int pivot = arr[left]; // Custom sorting pivot, store arr[left] in pivot, now arr[left] is empty. pivot acts as an intermediary.
        while(left < right){ // Exit the loop when the left and right pointers meet, indicating the end of the double-pointer traversal.
            while(true && left < right){
                if(arr[right] <= pivot){
                    arr[left] = arr[right];
                    break;
                }else{
                    right--;
                }
            }
            while(true && left < right){
                if(arr[left] > pivot){
                    arr[right] = arr[left];
                    break;          
                }else{
                    left++;
                }
            }
        }
        arr[left] = pivot;
        return left;
    }
    private static void quick_sort(int[] arr, int left, int right){
        if(left < right){
            int mid = get_mid(arr, left, right);
            quick_sort(arr, left, mid - 1);
            quick_sort(arr, mid + 1, right);
        }
    }
    private static void print(int[] arr){
        for(int i : arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

while(arr[right]>=pivot && left<right) right--; // The right pointer traverses from right to left. When arr[right] >= pivot, it continues to traverse right as it satisfies the condition of placing smaller elements to the left and larger elements to the right of the pivot. When arr[right] < pivot, the current value arr[right] is assigned to the empty position arr[left], making arr[right] empty. arr[left] = arr[right]; while(arr[left]<=pivot && left<right) left++; // The left pointer traverses from left to right. When arr[left] <= pivot, it continues to traverse left as it satisfies the condition of placing smaller elements to the left and larger elements to the right of the pivot. When arr[left] > pivot, the current value arr[left] is assigned to the empty position arr[right], making arr[left] empty. arr[right] = arr[left]; } // The above loop achieves the pattern of placing smaller elements to the left and larger elements to the right of the pivot. arr[left] = pivot; // Finally, the pivot value is placed back into the empty position arr[left]. return left; // Returns the index position of the pivot. }

private static void quick_sort(int[] arr, int left, int right) { if(left < right) { /* Divides arr[left..right] into two parts arr[left..mid] and arr[mid+1..right],

placing smaller elements to the left and larger elements to the right of the pivot. This is the first step. */ int mid = get_mid(arr, left, right); // Receives the index position of the pivot. quick_sort(arr, left, mid-1); // Recursively sorts arr[left..mid] to make the left subsequence ordered. quick_sort(arr, mid+1, right); // Recursively sorts arr[mid+1..right] to make the right subsequence ordered. } }

public static void print(int arr[]) // Encapsulated function to print the array { for(int k = 0; k < arr.length; k++) { System.out.print(arr[k] + " "); } } }

❮ Zookeeper Leader Android Tutorial Alertdialog ❯