Analysis and optimization of C++ quicksort

I believe that the friends who have learned the data structure and algorithm should be familiar with the quick sort, this paper introduces the analysis and optimization of C++ quick sort with an example, which has a good reference value for the design of C++ algorithm. Specific analysis is as follows:

I. introduction to quicksort

Quick sort is a sorting algorithm, containing n number of input arrays, in the worst case running time for Θ (n2) [ Θ read theta]. Although the worst-case run time is poor, quicksort is often the best practical choice for sorting. This is because their average performance is quite good: the desired run time for Θ (NLGN), and Θ (NLGN) mark implied in the constant factor is small. It also has the ability to sort in place and work well in a virtual memory environment.

Like merge sort, quicksort is based on Divide and conquer:

Decomposition: array A [p.. r] is divided into two (possibly empty) of subarray A [p.. the q - 1] and A [q + 1.. r], made A/p.. the q - 1 of each element is less than or equal to A [q], A [q + 1.. r] greater than or equal to every element of A [q]. So element A[q] is in its final position.

Solution: sort the subarrays A[p..q-1] and A[q+1..r] by recursively calling quicksort.

Merge: because the two subarrays are sorted in place, there is no need to merge and the entire array is in order.

The pseudo-code is as follows:

PARTITION(A, p, r) 
  x = A[p] 
  i = p 
  for j=p+1 to r 
    do if A[j] <= x 
      then i = i+1 
         exchange(A[i],A[j]) 
  exchange(A[p], A[i]) 
  return i 
 
QUICKSORT(A, p, r) 
  if p < r 
    then q = PARTITION(A, p, r) 
       QUICKSORT(A, p, q-1) 
       QUICKSORT(A, q+1, r) 

Ii. Performance analysis

1. Worst case

The worst case of quicksort occurs when the array is already sorted or in reverse order. In this case, one of the two regions produced by the partition process has no elements, and the other contains n-1 elements. The running time of the algorithm is able to recursively expressed as: T = T (n) (n - 1) + T (0) + Θ (n), recursion solution for T (n) = Θ (n ^ 2). As you can see, quicksort does not run any better than insertion sort at worst.

2. Best case

If we are lucky enough to have the most balanced partition per partition, we divide the array into n/2:n/2. Now get recursion for T (n) = 2 T (n / 2) + Θ (n), according to the circumstance of the main theorem 2 available T (n) = Θ (NLGN).

3. Average situation

Hypothesis 1: the partition points in the quicksort are very skewed, such as dividing the array into two subregions of 1/10:9/10 each time. What is the running time in this case? Run time recursion to T (n) = T (n / 10) + T (9 n / 10) + Θ (n), using recursive tree can solve T (n) = Θ (NLGN). It can be seen that when the points are divided into skewed, running time is still Θ (NLGN).

Assumption two: Partition produces both "good" and "bad" partitions, which alternate. What is the average running time in this case? The recurrence is (G for Good, B for Bad) :

G (n) = 2 b (n / 2) + Θ (n)

B (n) (n - 1) + Θ = G (n)

Solution: G (n) = 2 (G (n / 2-1) + Θ (n / 2)) + Θ (n) = 2 G (n / 2-1) + Θ (n) = Θ (NLGN)

As you can see, when good, difference divided appear alternately, fast line of run time as a whole is good, is still Θ (NLGN).

Three, the optimization of quick arrangement

The above analysis shows that quicksort is slow when the input is ordered or reversed, and performs well in the rest of the case. Bad if the input itself is sorted. So how do we make sure that it gets good average case performance for all inputs? For quicksort we default to using the first element in the array as the primary element. Assuming that the elements in a randomly selected array are the primary elements, the running time of quicksort will not depend on the order of the input sequence. We call a Quicksort with randomly selected pivot elements a random Quicksort.

In randomized quicksort, instead of always selecting the first element as the primary element, we select A random element from the array A[p... r] and swap it with the first element. Since the pivot elements are chosen at random, we expect the partition of the input array to be symmetric on average.

The pseudo-code is as follows:

RANDOMIZED-PARTITION(A, p, r) 
  i = RANDOM(p, r) 
  exchange(A[p], A[i]) 
  return PARTITION(A, p, r) 
 
RANDOMIZED-QUICKSORT(A, p, r) 
  if p < r 
    then q = RANDOMIZED-PARTITION(A, p, r) 
      RANDOMIZED-QUICKSORT(A, p, q-1) 
      RANDOMIZED-QUICKSORT(A, q+1, r) 

We conducted traditional quicksort and randomized quicksort for the ordered sequence of 30,000 elements, and compared their running time:

 
#include<iostream> 
#include<cstdlib> // srand rand 
#include<ctime> // clock_t clock 
using namespace std; 
 
void swap(int &a, int &b) 
{ 
  int tmp = a; 
  a = b; 
  b = tmp; 
} 
 
//Traditional partition operation
int Partition(int A[], int low, int high) 
{ 
  int pivot = A[low]; 
  int i = low; 
  for(int j=low+1; j<=high; ++j) 
  { 
    if(A[j] <= pivot) 
    { 
      ++i; 
      swap(A[i], A[j]); 
    } 
  } 
  swap(A[i], A[low]); 
  return i; 
} 
 
//Randomize the partition operation, randomly select pivot
int Partition_Random(int A[], int low, int high) 
{ 
  srand(time(NULL)); 
  int i = rand() % (high+1); 
  swap(A[low], A[i]); 
  return Partition(A, low, high); 
} 
 
//Traditional fast row
void QuickSort(int A[], int low, int high) 
{ 
  if(low < high) 
  { 
    int pos = Partition(A, low, high); 
    QuickSort(A, low, pos-1); 
    QuickSort(A, pos+1, high); 
  } 
} 
 
//Randomized quicksort
void QuickSort_Random(int A[], int low, int high) 
{ 
  if(low < high) 
  { 
    int pos = Partition_Random(A, low, high); 
    QuickSort_Random(A, low, pos-1); 
    QuickSort_Random(A, pos+1, high); 
  } 
} 
 
int main() 
{ 
  clock_t t1, t2; 
  //Initialize array
  int A[30000]; 
  for(int i=0; i<30000; ++i) 
    A[i] = i+1; 
     
  t1 = clock(); 
  QuickSort(A, 0, 30000-1); 
  t1 = clock() - t1; 
  cout << "Traditional quicksort took "<< t1 << " clicks(about " << ((float)t1)/CLOCKS_PER_SEC << " seconds)." << endl; 
 
  t2 = clock(); 
  QuickSort_Random(A, 0, 30000-1); 
  t2 = clock() - t2; 
  cout << "Randomized quicksort took "<< t2 << " clicks(about " << ((float)t2)/CLOCKS_PER_SEC << " seconds)." << endl; 
 
  return 0; 
}

The operation results are as follows:

[songlee@localhost ~]$ ./QuickSort  
Traditional quicksort took 1210309 clicks(about 1.21031 seconds). 
Randomized quicksort took 457573 clicks(about 0.457573 seconds). 
[songlee@localhost ~]$ ./QuickSort  
Traditional quicksort took 1208038 clicks(about 1.20804 seconds). 
Randomized quicksort took 644950 clicks(about 0.64495 seconds). 

As you can see from the results, the randomized version of quicksort is much more efficient for ordered input.

Problem record:

We know that there are three ways to exchange the values of two variables:

int tmp = a; //Methods a
a = b; 
b = tmp 
 
a = a+b; //Method 2
b = a-b; 
a = a-b; 
 
a = a^b; //Methods three
b = a^b; 
a = a^b;

However, you will find that in this program, if the swap function USES the latter two methods, it will make an error. Since methods 2 and 3 do not use intermediate variables, they swap values by operating directly on the memory unit of the variable. If two variables correspond to the same memory unit, the value of the memory unit has changed to 0 after two addition and subtraction or xor operations, so the variable value exchange cannot be realized. Therefore, when the variable that needs to exchange the value may be the same variable, the third variable must be used for exchange, otherwise the variable will be cleared.