C language data structure quick sort example details

C data structure quick sort example details

1. Introduction to quicksort

Quicksort adopts the idea of divide-and-conquer. In the first step, a string of Numbers is divided into two parts. The value of the first part is smaller than that of the second part.

2. Code implementation

#include <stdio.h>


/*  Exchange the two data  */
void swap(int* Ina , int* Inb)
{
  int temp = *Ina;
  *Ina = *Inb;
  *Inb = temp;
}

/*  for 1 Quick sort through, put 1 The sequence is divided into two parts  */
int getPartion(int* InArry,int InBegin,int InEnd)
{
  /*  The first line of separation is number one 1 a  */
  int part = InBegin;
  int index = 0;

  if(InEnd >= InBegin)
  {
    part = InBegin;
    for(index = InBegin+1; index <= InEnd; index++)
    {
      if(InArry[InBegin] >= InArry[index])
      {
        /*  Swap places  */
        swap(&InArry[part+1],&InArry[index]);
        part++;
      }
    }

    /*  The first 1 The number on the part Where to go  */
    swap(&InArry[InBegin],&InArry[part]);

    return part;
  }

}

/*  Quicksort function 
* InArry: Input array 
* InBegin: The beginning of an array 
*  InEnd: End of array 
*/
void quickSort(int* InArry,int InBegin,int InEnd)
{
  if(InArry == NULL || InEnd <= InBegin)
  {
    return;
  }

  int part = 0;
  part = getPartion(InArry,InBegin,InEnd);

  /*  Recursive calls  */
  quickSort(InArry,0,part-1);
  quickSort(InArry,part+1,InEnd);
}

int main()
{
  int a[] = {49,38,65,97,76,13,27};
  int index = 0;

  int len = sizeof(a)/sizeof(int);

  /*  So let's go through the print 1 The next element of the array  */
  for(index = 0; index < len; index++)
  {
    printf("%d ",a[index]);
  }
  printf("\n");

  /*  Call the quicksort function  */
  quickSort(a,0,len-1);

  /*  Go through the print again 1 The next element of the array  */
  for(index = 0; index < len; index++)
  {
    printf("%d ",a[index]);
  }
  printf("\n");



  return 0;
}

The above is the use of C language data structure quick sorting example details, if you have any questions please leave a message or to the site community exchange discussion, thank you for reading, hope to help you, thank you for the support of the site!