This series is my summary of data structure and algorithm when I was looking for a job many years ago. There are basic parts and classic interview questions of various companies. It was first published on CSDN. Is sorted out for a series of friends in need of reference, if there is a mistake, welcome to correct. The full code address for this series is here.

0 overview

Quicksort is also based on divide-and-conquer, similar to merge sort, except that there is no merge at the end of the quicksort partition. Quicksort an array A[p..r] consists of three steps:

  • Partition: arrayA[p...r]Is divided into two subarraysA[p...q-1] 和 A[q+1...r],A[p...q-1]Is less than or equal to every element inA[q]And theA[q+1...r]Each element is greater thanA[q]. The partitioning process is shown in the following figure.
  • Solution: Sort the subarrays separately by recursively calling quicksort.
  • Merge: Because the two subarrays are already sorted and sized, no action is required.

Quicksort algorithm is not a complex algorithm, but the actual code is the most error-prone code, write the wrong easy to loop or partition error, this code see here.

1 Naive quicksort

One drawback of this naive quicksort is that in extreme cases where all elements are equal (or the elements themselves are ordered, such as a[] = {1,2,3,4,5}, etc.), the naive fast algorithm is O(N^2) and O(N LGN) if the array is balanced.

/ / void quickSort(int a[], int l, int u) {/ / void quickSort(int a[], int l, int u) {if (l >= u) return; int q = partition(a, l, u); quickSort(a, l, q-1); quickSort(a, q+1, u); } /** * int partition(int a[], int l, int u) {int I, q=l;for (i = l+1; i <= u; i++) {
        if (a[i] < a[l])
            swapInt(a, i, ++q);
    }
    swapInt(a, l, q);
    return q;
}
Copy the code

2 improvements – Quicksort for bidirectional partitioning

An improved method is to adopt bidirectional partition, using two variables I and J. I scans from left to right, moves over small elements, and stops when encountering large elements. J scans from right to left, moving large elements and stopping at small elements. Then test if I and j cross, stop if they do, otherwise swap the values of the elements I and j correspond to.

Notice that if we have the same elements in the array, we stop scanning and swap the element values of I and j when we encounter the same elements. This increases the number of swaps, but it turns the worst-case case where all the elements are the same from O(N^2) to something like O(NlgN). For example, if array A={2,2,2,2,2}, the naive quicksort method is used to divide n elements into 1 and n-1 each time, and the time complexity is O(n ^2). After bidirectional partition, the position of the first partition is 2, which can basically balance the two parts. The code is as follows:

/** * quick sort - double partition function */ int int lr (int a[], int l, int u, int pivot) {int I = l; int j = u+1;while (1) {
        do {
            i++;
        } while(a[i] < pivot && i <= u); // I <=u.do {
            j--;
        } while (a[j] > pivot);

        if (i > j) break; swapInt(a, i, j); } // a[I...u] is greater than or equal to the pivot element t, and the pivot element is on the left, so it cannot be swapped with I. You can only swap with j. swapInt(a, l, j);returnj; } /** * quickSortLR(int a[], int l, int u) {if (l >= u) return;

    int pivot = a[l];
    int q = partitionLR(a, l, u, pivot);
    quickSortLR(a, l, q-1);
    quickSortLR(a, q+1, u);
}
Copy the code

Although bidirectional partitioning solves the problem that all elements are the same, it still achieves O(N^2) complexity for an already sorted array. While (a[I]

3 continue to improve – random method and trinary method to get hub elements

In order to solve the above problems, it can be further improved to obtain the hub elements by randomly selecting the hub elements or taking the center of three numbers, and then divide the hub elements bidirectionally. The triplet refers to sorting three values from array A[L… u] and using the middle value as the pivot element. If group A[] = {1, 3, 5, 2, 4}, then we sort A[0], A[2] and A[4], select the median A[4](element 4) as the pivot element, and swap it to A[L]. Finally, the array becomes A[] = {4 3 5 2 1}. And then sort it both ways as before.

Int pivotRandom(int a[], int l, int u) {int rand = randInt(l, u); swapInt(a, l, rand); // Swap hub elements to position Lreturna[l]; } /** * pivotMedian3(int a[], int l, int u) {int m = l + (u)-l) / 2; /* * * * * */if( a[l] > a[m] )
        swapInt(a, l, m);

     if( a[l] > a[u] )
        swapInt(a, l, u);

     if( a[m] > a[u] ) swapInt(a, m, u); /* assert: a[l] <= a[m] <= a[u] */ swapInt(a, m, l); // Swap hub elements to position Lreturn a[l];
}
Copy the code

In addition, when the data is basically ordered, you can get good performance by using insert sort, and it is faster than quicksort when sorting small subarrays. You can use insert sort when the array size is small, but quicksort when the array size is large.

Write non-recursive quicksort

Non-recursive quicksort writing is really rare, but it’s always good to get your hands on it. You need to use stacks, and pay attention to the order in which you push them. The code is as follows:

Void quickSortIter(int a[], int n) {Stack * Stack = stackNew(n); int l = 0, u = n-1; int p = partition(a, l, u);if(p-1 > l) {// The left half of the two boundary values push(stack, p-1); push(stack, l); }if(p+1 < u) {// Push (stack, u); push(stack, p+1); }while(! IS_EMPTY(stack)) {// if the stack is not empty, then the loop partition process l = pop(stack); u = pop(stack); p = partition(a, l, u);if (p-1 > l) {
            push(stack, p-1);
            push(stack, l);
        }

        if(p+1 < u) { push(stack, u); push(stack, p+1); }}}Copy the code

The resources

  • Data Structures and Algorithms -C language implementation
  • Introduction to Algorithms