# The C language implements an improved version of quicksort

• 2020-06-07 05:02:03
• OfStack

The method of 3 - to - center is used to improve quicksort. The details are as follows

The implementation takes the middle element of the first, middle, and last element of the array as the partition element (otherwise the elements are excluded from the partition process). Arrays of size 11 or smaller are ignored during the partition process, and then the insertion sort is used to complete the sort.

``````
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <malloc.h>
using namespace std;
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef int Status;
// Output function
void Print(int a[], int l, int r)
{
int i;
for(i = l; i <= r; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
// Improved insertion sort
void Insertion(int a[], int l, int r)
{
int i, j;
// Loop to find the minimum value in the array
for(i = r; i > l; i--)
{
if(a[i-1] > a[i])
{
swap(a[i-1], a[i]);
}
}
// Because of the loop above ,a[0]a[1] Have already ordered
for(i = l+2; i <= r; i++)
{
int temp = a[i];
j = i;
// At this time a[j] The location has been recorded
//while Shift operation is performed for cyclic comparisons
while(temp < a[j-1])
{
a[j] = a[j-1];
j--;
}
// Place the recorded values where they should be
a[j] = temp;
}
}
// Partition function
int partion(int a[], int left, int right)
{
// Take the rightmost element as the partition element
int temp = a[right];
// record  i = left, j = right
int i = left, j = right-1;
// Loop until the left and right Pointers meet
while(true)
{
// Scan from the left , When there are elements larger than the partition element , Scanning to stop
while(temp > a[i])
{
i++;
}
// Scan from the right , When there are elements smaller than partition elements , Scanning to stop
while(temp < a[j] && j >= left)
{
j--;
}
// if  i >= j,  Cycle as , The following exchange is not performed
if(i >= j) break;
// The element when the exchange stops
swap(a[i], a[j]);
}
// Swap the element with the partition element
swap(a[i], a[right]);
//printf("i = %d\n", i);
//Print(a, 0, 6);
// End of partition process
return i;
}

void qsort(int a[], int left, int right)
{
int i;
if(right-left <= 10)
return;
swap(a[(left+right)/2], a[right-1]);
if(a[left] > a[right-1])
swap(a[left], a[right-1]);
if(a[left] > a[right])
swap(a[left], a[right]);
if(a[right] > a[right-1])
swap(a[right-1], a[right]);
i = partion(a, left+1, right-1);
qsort(a, left, i-1);
qsort(a, i+1, right);
}
void Sort(int a[], int left, int right)
{
qsort(a, left, right);
Insertion(a, left, right);
}

int main()
{
int a[12] = {2, 5, 3, 7, 6, 1, 4, 11, 8, 10, 9, 12};
// Quick Sort improvement
printf(" right 0~11 The sorting \n");
Sort(a, 0, 11);
Print(a, 0, 11);
return 0;
}``````

Related articles: