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);
  }
 }
}

Related articles: