C language quicksort algorithm sample code sharing

  • 2020-04-02 02:12:11
  • OfStack


Steps as follows:
1. Select an element from the sequence, called pivot;
2. Reorder the sequence so that all elements smaller than the base value are placed in front of the base value, and all elements larger than the base value are placed after the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the sequence. This is called a partition operation.
3. Recursively sorts substrings of elements less than the base value and greater than the base value.
At the very bottom of the recursion, the size of the sequence is zero or one, so it's always sorted. This algorithm always exits, even though it recurses, because it puts at least one element in its last position in each iteration.


#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define RANDOM(i) (rand()%i)
#define N 9    //Set array length
//To partition
int Partition(int array[], int left, int right)
{
 int i,j;
 int temp;
 j = left-1;
 for (i=left; i<=right; i++)
 {
  if (array[i] <=  array[right]) //Base on the value of the last array
  {
   j++;
   temp = array[j];
   array[j] = array[i];
   array[i] = temp;
  }
 }
 return j;
}
//Iterative arithmetic
void QuikSort(int array[], int left, int right)
{
 int pivot;
 if (left < right)
 {
  pivot = Partition(array, left, right);
  QuikSort(array, left, pivot-1);
  QuikSort(array, pivot+1, right);
 }
}
//The sample
int main()
{
 int i = 0;
 int a[N];
 srand((int)time(0));  //Set the random number seed
 for (i=0; i<N; i++)  //Before ordering
 {
  a[i] = RANDOM(100);
  printf("%dt", a[i]);
 }
 printf("nn");
 QuikSort(a, 0, N-1);
 for (i=0; i<N; i++) //After ordering
 {
  printf("%dt", a[i]);
 }
}


Related articles: