Quick sort

This chapter introduces quick sort in sorting algorithm .

Catalog
1.  Quick sort Introduction
2.  Quick sort text description
3.  Time complexity and stability of quick sort
4.  Fast sort implementation
4.1  Quick sort C Realization
4.2  Quick sort C++ Realization
4.3  Quick sort Java Realization

Reprint please indicate the source ： Quick sort - If the sky doesn't die - Blog Garden

---

More ： Data structure and algorithm series Catalog

Quick sort Introduction

Quick sort (Quick Sort) Use divide and conquer strategy .
The basic idea is this ： Choose a base number , Divide the data to be sorted into two independent parts by one sorting ; All the data in one part is smaller than all the data in the other part . then , Then according to this method, the two parts of data are sorted quickly , The whole sort process can be done recursively , So that the whole data becomes an ordered sequence .

Quick sort process ：
(1) Pick a base value from the sequence .
(2) Place everything smaller than the benchmark in front of the benchmark , All those larger than the benchmark are placed behind the benchmark ( The same number can go to either side ); After the partition exits , The benchmark is in the middle of the sequence .
(3) Recursively " The subsequence before the reference value " and " The subsequence after the reference value " Sort .

Quick sort text description

Quick sort code

/*
 *  Quick sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     l --  The left boundary of the array ( for example , Sort from the start , be l=0)
 *     r --  The right boundary of the array ( for example , Sort to the end of the array , be r=a.length-1)
 */
void quick_sort(int a[], int l, int r)
{
    if (l < r)
    {
        int i,j,x;

        i = l;
        j = r;
        x = a[i];
        while (i < j)
        {
            while(i < j && a[j] > x)
                j--; //  Find the first less than... From right to left x Number of numbers 
            if(i < j)
                a[i++] = a[j];
            while(i < j && a[i] < x)
                i++; //  Find the first one greater than... From left to right x Number of numbers 
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = x;
        quick_sort(a, l, i-1); /*  Recursively call  */
        quick_sort(a, i+1, r); /*  Recursively call  */
    }
}

The following is a sequence of numbers a={30,40,60,10,20,50} For example , Demonstrate its quick sort process ( Here's the picture ).

The picture above just shows the second 1 A quick sort of process . In the 1 During the trip , Set up x=a[i], namely x=30.
(01) from " Right --> Left " Find less than x Number of numbers ： Find the number that satisfies the condition a[j]=20, here j=4; And then a[j] assignment a[i], here i=0; And then traverse from left to right .
(02) from " Left --> Right " Find greater than x Number of numbers ： Find the number that satisfies the condition a[i]=40, here i=1; And then a[i] assignment a[j], here j=4; And then traverse from right to left .
(03) from " Right --> Left " Find less than x Number of numbers ： Find the number that satisfies the condition a[j]=10, here j=3; And then a[j] assignment a[i], here i=1; And then traverse from left to right .
(04) from " Left --> Right " Find greater than x Number of numbers ： Find the number that satisfies the condition a[i]=60, here i=2; And then a[i] assignment a[j], here j=3; And then traverse from right to left .
(05) from " Right --> Left " Find less than x Number of numbers ： There is no number that satisfies the condition . When i>=j when , Stop searching ; And then x Assign a value to a[i]. The tour ends ！

Follow the same method , Recursive traversal of subsequences . Finally, we get an ordered array ！

Time complexity and stability of quick sort

Quicksort stability
Quicksort is an unstable algorithm , It doesn't meet the definition of stable algorithm .
Algorithm stability -- Let's assume that there exists in a sequence a[i]=a[j], If before sorting ,a[i] stay a[j] front ; And after sorting ,a[i] Still in a[j] front . Then the sorting algorithm is stable ！

Time complexity of quick sorting
The time complexity of quicksort in the worst case is O(N2), The average time complexity is O(N*lgN).
This sentence is very understandable ： Let's assume that the sequence being sorted has N Number . The time complexity of traversing once is O(N), How many times does it take to traverse ？ At least lg(N+1) Time , most N Time .
(01) Why at least lg(N+1) Time ？ Quick sort is traversed by divide and conquer method , We think of it as a binary tree , The number of times it needs to traverse is the depth of the binary tree , And according to the definition of complete binary tree , Its depth is at least lg(N+1). therefore , The minimum traversal times of quicksort is lg(N+1) Time .
(02) Why at most N Time ？ This should be very simple , Or think of quicksort as a binary tree , It's the deepest N. therefore , The most traversal times of quick read sort is N Time .

Fast sort implementation

Quick sort C Realization
Implementation code (quick_sort.c)

/**
 *  Quick sort ：C  Language 
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <stdio.h>

//  The length of the array 
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )

/*
 *  Quick sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     l --  The left boundary of the array ( for example , Sort from the start , be l=0)
 *     r --  The right boundary of the array ( for example , Sort to the end of the array , be r=a.length-1)
 */
void quick_sort(int a[], int l, int r)
{
    if (l < r)
    {
        int i,j,x;

        i = l;
        j = r;
        x = a[i];
        while (i < j)
        {
            while(i < j && a[j] > x)
                j--; //  Find the first less than... From right to left x Number of numbers 
            if(i < j)
                a[i++] = a[j];
            while(i < j && a[i] < x)
                i++; //  Find the first one greater than... From left to right x Number of numbers 
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = x;
        quick_sort(a, l, i-1); /*  Recursively call  */
        quick_sort(a, i+1, r); /*  Recursively call  */
    }
}

void main()
{
    int i;
    int a[] = {30,40,60,10,20,50};
    int ilen = LENGTH(a);

    printf("before sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");

    quick_sort(a, 0, ilen-1);

    printf("after  sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");
}

Quick sort C++ Realization
Implementation code (QuickSort.cpp)

/**
 *  Quick sort ：C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 *  Quick sort 
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     l --  The left boundary of the array ( for example , Sort from the start , be l=0)
 *     r --  The right boundary of the array ( for example , Sort to the end of the array , be r=a.length-1)
 */
void quickSort(int* a, int l, int r)
{
    if (l < r)
    {
        int i,j,x;

        i = l;
        j = r;
        x = a[i];
        while (i < j)
        {
            while(i < j && a[j] > x)
                j--; //  Find the first less than... From right to left x Number of numbers 
            if(i < j)
                a[i++] = a[j];
            while(i < j && a[i] < x)
                i++; //  Find the first one greater than... From left to right x Number of numbers 
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = x;
        quickSort(a, l, i-1); /*  Recursively call  */
        quickSort(a, i+1, r); /*  Recursively call  */
    }
}

int main()
{
    int i;
    int a[] = {30,40,60,10,20,50};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    quickSort(a, 0, ilen-1);

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

Quick sort Java Realization
Implementation code (QuickSort.java)

/**
 *  Quick sort ：Java
 *
 * @author skywang
 * @date 2014/03/11
 */

public class QuickSort {

    /*
     *  Quick sort 
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     l --  The left boundary of the array ( for example , Sort from the start , be l=0)
     *     r --  The right boundary of the array ( for example , Sort to the end of the array , be r=a.length-1)
     */
    public static void quickSort(int[] a, int l, int r) {

        if (l < r) {
            int i,j,x;

            i = l;
            j = r;
            x = a[i];
            while (i < j) {
                while(i < j && a[j] > x)
                    j--; //  Find the first less than... From right to left x Number of numbers 
                if(i < j)
                    a[i++] = a[j];
                while(i < j && a[i] < x)
                    i++; //  Find the first one greater than... From left to right x Number of numbers 
                if(i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quickSort(a, l, i-1); /*  Recursively call  */
            quickSort(a, i+1, r); /*  Recursively call  */
        }
    }

    public static void main(String[] args) {
        int i;
        int a[] = {30,40,60,10,20,50};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        quickSort(a, 0, a.length-1);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}

above 3 The implementation principle and output results of the two languages are the same . Here is their output ：

before sort:30 40 60 10 20 50
after  sort:10 20 30 40 50 60