An example of the basic sorting algorithm in C language

  • 2020-05-30 20:52:20
  • OfStack

This paper illustrates the basic sorting algorithm of C in bucket sorting. I will share it with you for your reference as follows:

Bucket sort is an array a[n] with n integer elements, i for any value, 0 < = a[i] < = m special sorting algorithm.

n==m, n! = m. One thing to note when writing code is that a[i] accesses the i-1 element, not the i element.


/************************************************************************************/
/* Bucket_Sort.h  Bucket sorting algorithm  */
/*  The problem: 1 a n An integer element a[0],a[1], ... ,a[n-1] Array sort, where 0 <= a[i] <= m, any i */
/*  Program: the running time is O(m+n), The auxiliary space is O(m) */
/*  when  n=m  , the running time is O(N),  The auxiliary space is O(1) */
/************************************************************************************/
#include <vector>
/*m != n */
void Bucket_Sort_m(int *a, int n, int m)
{
  std::vector<int> temp(m,0);
  int i;
  for(i = 0; i != n; ++i) // traverse a[]
    ++temp[a[i]-1]; // If there is a value corresponding to the subscript, mark as 1 , or for 0
  i = 0;
  for(int j = 1; j <= m; ++j) // traverse temp vector 
    if(temp[j-1]) a[i++] = j;
  temp.clear();
}
/* m == n */
/*  The end result is a[i-1] = i */
void Bucket_Sort(int *a,int n)
{
  for(int i = 1; i <= n; ++i)
  {
    while(a[i-1] != i)
    {
       int temp = a[a[i-1]-1];
       a[a[i-1]-1] = a[i-1];
       a[i-1] = temp;
    }
    /*  Pseudo code : If the hypothesis can pass a[i] Access the first part of the array i Elements, not the first i-1 a  */
    /*while(a[i] != i)
    {
       int temp = a[a[i]];
       a[a[i]] = a[i];
       a[i] = temp;
    }
    */
  }
}

I hope this article has been helpful to you in programming C.


Related articles: