The C language implements quicksort
- 2020-06-07 05:01:52
- OfStack
Quick sorting algorithm is a kind of partition sorting algorithm. It could be divided into two parts, the array and then to sort by two parts, respectively. We will see, divided depends on the position of the input array elements in the initial position. The key lies in the segmentation process, rearrangement arrays, it makes the following three conditions: (i) for a i, a [i] on the final location (ii) a [left],... , elements in a[ES9en-1] are smaller (iii)a[i+1],... The elements in a[right] are all larger than a[i]. We do the sorting by partitioning, and then recursively apply the method to process the subarrays.
First, we select any a[right] as the partition element, which will be in the final position. Starting from the right end of an array of scan again, until you find one less than the division of elements. The scan to stop the two elements of, apparently in the final division of the array position instead, so the exchange of the two elements. Continue this process, we can guarantee is located in the left side of the pointer on the left side of the element in the array are smaller than dividing element, is located in the right side of the pointer on the right side of the element is bigger than dividing elements.
When dividing, the variable temp preserves the position of the partition element a[right], while i and j are left scanning pointer and right scanning pointer respectively. The partition loop makes i increase j and decrease, while while keeps one constant property -- no element on the left side of i is larger than temp, and no element on the right side of j is smaller than temp Assign a[i], so that the elements on the left side of v are less than or equal to v, and the elements on the right side of v are greater than or equal to v, ending the partition process. Partition loop is an indeterminate loop, when two Pointers meet, it is ended by break statement, testing j=left to prevent partition elements from being the smallest elements in the array.
Quicksort recursive algorithm
#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");
}
// 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]);
Print(a, 0, 6);
//printf("i = %d", i);
// End of partition process
return i;
}
// Quick sort
void qsort(int a[], int left, int right)
{
// Order to complete , Cycle as
if(right <= left)
return;
// Do partition
int i = partion(a, left, right);
// Sort the left part
if(left < (i-1))
printf(" right %d~%d The sorting \n", left, i-1), qsort(a, left, i-1);
// Sort the right part
if(right > (i+1))
printf(" right %d~%d The sorting \n", i+1, right), qsort(a, i+1, right);
}
int main()
{
int a[7] = {2, 5, 3, 7, 6, 1, 4};
// Quick sort
printf(" right 0~6 The sorting \n");
qsort(a, 0, 6);
Print(a, 0, 6);
return 0;
}
Non-recursive quicksort
Quick sort of non-recursive implementation USES a explicit push down stack, using the medium voltage into the parameters to the stack and procedure call/exit from the stack pop-up parameter to replace the recursive call, the process continues until the stack is empty. We put the two subarray supplied by press it into the stack to ensure the maximum stack depth for lgN, if the N element.
void qsort(int a[], int left, int right)
{
int i;
// Define the stack s
stack<int> s;
// First determine if the stack is empty
while(!s.empty())
{
// If the stack is not empty , Remove elements from the stack
s.pop();
}
// will right Into the stack
s.push(right);
// will left Into the stack
s.push(left);
//while cycle , When the stack is empty , End of the cycle
while(!s.empty())
{
// The element left Out of the stack
left = s.top(), s.pop();
// The element right Out of the stack
right = s.top(), s.pop();
// judge left with right The relationship between , if left>=right,continue
if(left >= right)
{
continue;
}
// Is divided
i = partion(a, left, right);
// Compare the sizes of the two subarrays
// Pushes the larger of the subarrays onto the stack
if((i-1-left) > (right-i-1))
{
s.push(i-1);
s.push(left);
s.push(i+1);
s.push(right);
}
else
{
s.push(i+1);
s.push(right);
s.push(i-1);
s.push(left);
}
}
}