Ten basic ideas of sorting algorithm, animation demonstration and C language implementation

Ten basic ideas of sorting algorithm and C language implementation

A few days ago, I wanted to take a look at the sorting algorithm. As a result, there were problems in several blogs, so I wrote a new one. The level is limited. 99% of the code below is manually typed, has been tested and is safe to eat with reference to many sources.

Recommended learning site: Rookie tutorial – Top 10 classic sorting algorithms (some places or slightly obscure, but provides a variety of languages, the code may be a little difficult for beginners to understand)

B station (a lot of video can be seen)

Top 10 classic sorting algorithms

1. Bubble sort

The basic idea

It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if the order is wrong (from largest to smallest, Z to A). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted.

The algorithm gets its name from the fact that smaller elements slowly “float” to the top of the sequence (ascending or descending) through exchange, just as bubbles of carbon dioxide in a carbonated drink eventually rise to the top.

animation

implementation

void bubbleSort(a)
{
   / / C implementation
   int arr[] = {5.9.3.8.6};
   int len = 5; // The array length can also be obtained using the strlen function in 
      
   int temp;
   for (int i = 0; i < len - 1; i++) // From small to big
   {                                 // The number of loops is len-1
      for (int j = 0; j < len - 1 - i; j++)
      { // The inner loop is the number of comparisons per trip. The I trip compares len-i times, because the first time has bubbled the largest element to the last position
         if (arr[j] > arr[j + 1])
         { // Compare adjacent elements, reverse order will switch positions
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp; }}}// Prints the array
   for (int i = 0; i < len; i++)
      printf("%d\t", arr[i]);
}

Copy the code

2. Select sort

The basic idea

The smallest (or largest) element is first selected from the data elements to be sorted and stored at the beginning of the sequence. The smallest (or largest) element is then found from the remaining unsorted elements and placed at the end of the sorted sequence. And so on until the total number of data elements to be sorted is zero.

animation

implementation

  int arr[] = {100.92.5.9.3.8.23.17.50.6};
  int len = 10;                 // The array length can also be obtained using the strlen function in 
      
  int index = 0;                // Will be used to store the location index of the smallest element in the unsorted region
  for (int i = 0; i < len; i++) // From small to big
  {
    index = i;
    for (int j = i + 1; j < len; j++) // Compare the size of each element after I with that of the I element. If arr[I] is less than arr[I], update the minimum element index
    {
      if (arr[j] < arr[index])
        index = j;
      // The index can be swapped directly, but the memory footprint is considered, so we only store indexes that meet the criteria
    }
    // Swap I with the index element
    // Note that the transposed function cannot be written into the second for loop, i.e., for(int) J = I +1), since the objects pointed to by I and min will be exchanged after the exchange, then the loop may appear that the elements less than arr[I](at this point, min position has been changed) but not less than arr[min](at this point, I position) will also be exchanged with the initial position, the specific situation can be tested!
    if(i ! = index)// To determine if transposition is required, swap the smallest element position to the first unsorted position
    {
      inttemp = arr[i]; arr[i] = arr[index]; arr[index] = temp; }}// Prints the array
  for (int i = 0; i < len; i++)
    printf("%d\t", arr[i]);
}
Copy the code

3. Insert sort

The basic idea

Insertion sort is one of the simplest sorting methods. Its basic idea is to insert a record into an ordered list, so as to form a new ordered list with the number of records increasing by one.

Orderly generally will be the first element as the smallest group, and then use the second element is inserted into the first element of order in the table (in fact is a simple comparison of size), then the third element is inserted into the orderly in the table, the first two elements, three elements to form a ordered list, and so on, finally get a table contains all the elements of the order

implementation

void insertionSort(a)
{
   int arr[] = {1.5.3.9.7};
   int len = 5;

   int i, j, key;
   for (i = 1; i < len; i++) // Start at 1 because by default the first element is the smallest ordered table
   {
      key = arr[i];
      j = i - 1; //a[j] is the first element in an ordered table and the first element in an unordered table
      while ((j >= 0) && (arr[j] > key)) // If j>=0 is greater than the number to be inserted j>=0 is to prevent the array from exceeding the bounds (previous bounds)
      {
         arr[j + 1] = arr[j];
         j--;
      }
      arr[j + 1] = key; // A [j] is the first element smaller than key that escapes the loop, putting key one place after it, because all values larger than key are moved one place back in the loop
   }

   // Prints the array
   for (int i = 0; i < len; i++)
      printf("%d\t", arr[i]);
}
Copy the code

4. Hill sort

The basic idea

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort

The basic idea is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sort respectively. When the records in the whole sequence are “basically ordered”, the direct insertion sort of all records is carried out successively.

B station reference video: Bilibili

animation

implementation

Specific implementation methods:

1. Divide the sequence to be arranged into multiple sub-sequences with gaps,
2. Insertion sort is then performed on each subsequence
3. Repeat the above, each interval gap is different (and the smaller the meter), until the last time to select gap=1, complete the sorting.
4. We usually take half of the length of the array as the first interval, that is, the first time the entire array is divided into len/2 subsequence (subsequence 0 and gap(len/2) is a subsequence), and then insert sort, and then repeat the above operation with len/2/2 as the interval until gap=1

void shellSort(a)
{

   int arr[] = {1.5.3.9.7};
   int len = 5;

   int gap, i, j;
   int temp;

   for (gap = len / 2; gap >= 1; gap /= 2) // The first interval is len/2, and then it keeps shrinking
   {
      for (i = gap; i < len; i++) // Iterate over each element with subscript greater than gap (0-(gap-1) is the first ordered list of each subsequence)
      {
         temp = arr[i]; // The value to be inserted is assigned to temp because its position may be overwritten
         for (j = i - gap; arr[j] > temp && j >= 0; j -= gap)
         {                         I i-gap i-2gap i-n*gap(i-n*gap >= 0)
            arr[j + gap] = arr[j]; //arr[j]; //arr[j]
         }
         arr[j + gap] = temp; // If arr[j]}}// Prints the array
   for (int i = 0; i < len; i++)
      printf("%d\t", arr[i]);
}
Copy the code

5. Merge sort

The basic idea

For two ordered sequences, imagine a contest in which each side starts with the weakest player, and the winner is the winner, and continues to line up against the weakest player on the field.

B station reference video: Bilibili

animation

implementation

//5. Merge sort
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if(a ! = arr) {int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}
Copy the code

6. Quicksort

The basic idea

1. Pick an element from the sequence, called pivot;

2. Reorder the array 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 behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation;

3. Recursively sorts subsequences of elements less than the base value and subsequences of elements greater than the base value;

animation

implementation

void quickSort(a)
{
   int arr[10] = {11.7.9.3.4.6.2.8.5.3};
   quick_sort(arr, 0.9);
   for (int i = 0; i < 10; i++)
      printf("%d\t", arr[i]);
}

int partition(int arr[], int start, int end)
{
   int temp = arr[start];
   int li = start, ri = end;
   while (li < ri)
   {
      while (li < ri && arr[ri] > temp)
         ri--;
      if (li < ri)
      {
         arr[li] = arr[ri];
         li++;
      }
      while (li < ri && arr[li] < temp)
         li++;
      if (li < ri)
      {
         arr[ri] = arr[li];
         ri--;
      }
   }
   arr[li] = temp;
   return li;
}

void quick_sort(int arr[], int start, int end)
{
   if (start < end)
   {
      int index = partition(arr, start, end);
      quick_sort(arr, start, index - 1);
      quick_sort(arr, index + 1, end); }}Copy the code

7. The heap sort

The basic idea

1. Create a heap H[0…… n-1];

2. Swap the heap head (maximum) with the heap tail;

3. Reduce the size of the heap by 1 and call shift_down(0) to move the top of the new array into position.

4. Repeat step 2 until the heap size is 1.

   Recommended resources: Graphical algorithms for heap Sorting B station video ‘

animation

implementation

/ / 7. Heap sort
void heapSort(a)
{
   int arr[] = {3.5.3.0.8.6.1.5.8.6.2.4.9.4.7.0.1.8.9.7.3.1.2.5.9.7.4.0.2.6};
   int len = (int)sizeof(arr) / sizeof(*arr);
   for (int i = len; i > 1; i--)
      heap_Sort(arr, i); // Build the heap each time with size -1

   for (int i = 0; i < len; i++)
      printf("%d ", arr[i]);
   return 0;
}

// Construct a big top heap and swap the maximum to the last bit
void heap_Sort(int arr[], int len)
{
   int dad = len / 2 - 1; // The last parent node
   int son = 2 * dad + 1; // The first child of the parent node
   while (dad >= 0)
   {
      // Determine if there are two child nodes. If so, find the largest child node
      if (son + 1 <= len - 1 && arr[son] < arr[son + 1])
         son++;
      if (arr[dad] < arr[son]) // If the parent node is smaller than the child node, swap places
         swap(&arr[dad], &arr[son]);
      dad--;             // Fall back to the previous parent node
      son = 2 * dad + 1; // The first child of the previous parent
   }
   swap(&arr[0], &arr[len - 1]);
}

void swap(int *a, int *b)
{
   int temp = *a;
   *a = *b;
   *b = temp;
}
Copy the code

8. Counting sort

The basic idea

1. Find the largest and smallest elements in the array to be sorted
2. Count the number of occurrences of each element of value I in the array, stored in the i-th entry of array C
3. Add up all the counts (starting with the first element in C, adding each term to the previous one)
4. Reverse populating the target array: place each element I in the C(I) item of the new array, subtracting C(I) by 1 for each element

animation

implementation

void countingSort(a)
{
   int arr[] = {3.5.3.0.8.6.1.5.8.6.2.4.9.4.7.0.1.8.9.7.3.1.2.5.9.7.4.0.2.6};
   int len = (int)sizeof(arr) / sizeof(*arr);
   counting_Sort(arr, len);

   for (int i = 0; i < len; i++)
      printf("%d ", arr[i]);
}

void counting_Sort(int arr[], int LEN)
{
   // Find the maximum and minimum values
   int max = arr[0], min = arr[0], i, j = 0;
   for (i = 0; i < LEN; i++)
   {
      if (arr[i] < min)
         min = arr[i];
      if (arr[i] > max)
         max = arr[i];
   }

   // Build the count array
   int new_len = max - min + 1;
   printf("%d\n", new_len);
   int conunting_arr[new_len];
   / / count
   for (i = 0; i < new_len; i++) / / initialization
   {
      conunting_arr[i] = 0;
   }
   for (i = 0; i < LEN; i++)
   {
      conunting_arr[arr[i] - min]++;
   }

   // Sort by counting results
   for (i = 0; i < new_len; i++)
   {
      int index = conunting_arr[i];
      while(index ! =0) { arr[j] = i + min; index--; j++; }}}Copy the code

9. Bucket sorting

The basic idea

Bucket sort, or an updated version of so-called box sort, works by sorting an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or to continue sorting using bucket sort recursively).

Each bucket corresponds to a data or a data segment (actually when each bucket corresponds to a data is actually the previous counting sort)

Here we make each bucket correspond to a data segment and use bubble sort to sort the elements in the bucket

animation

implementation

void bucketSort(a)
{
   int arr[] = {3.5.3.0.8.6.1.5.8.6.2.4.9.4.7.0.1.8.9.7.3.1.2.5.9.7.4.0.2.6};
   int len = (int)sizeof(arr) / sizeof(*arr);
   bucket_Sort(arr, len);

   for (int i = 0; i < len; i++)
      printf("%d ", arr[i]);
}

void bucket_sort(int arr[], int LEN)
{
   int bucket[5] [6] = {0}, i, j, k, temp; // Initialize the bucket, each bucket holds 6 data
   // Find the maximum and minimum values
   int min = arr[0], max = arr[0];
   for (i = 0; i < LEN; i++)
   {
      if (arr[i] < min)
         min = arr[i]; / / 0
      if (arr[i] > max)
         max = arr[i]; / / 9
   }
   // Iterate through the array and place the elements in the corresponding bucket
   int index0 = 0, index1 = 0, index2 = 0, index3 = 0, index4 = 0;
   for (i = 0; i < LEN; i++)
   {
      if (arr[i] < min + (max - min + 1) / 5 * 1 && index0 < 7)
      {
         bucket[0][index0] = arr[i];
         index0++;
      }
      else if (arr[i] < min + (max - min + 1) / 5 * 2 && (index1 < 7 || index0 >= 7))
      {
         bucket[1][index1] = arr[i];
         index1++;
      }
      else if (arr[i] < min + (max - min + 1) / 5 * 3 && (index2 < 7 || index1 >= 7))
      {
         bucket[2][index2] = arr[i];
         index2++;
      }
      else if (arr[i] < min + (max - min + 1) / 5 * 4 && (index3 < 7 || index2 >= 7))
      {
         bucket[3][index3] = arr[i];
         index3++;
      }
      else if (arr[i] < min + (max - min + 1) / 5 * 5 && (index4 < 7 || index3 >= 7))
      {
         bucket[4][index4] = arr[i]; index4++; }}// Use bubble sort on each bucket
   for (i = 0; i < 5; i++)
   {
      for (int j = 0; j < 5; j++) // From small to big
      {                           // The number of loops is len-1
         for (int k = 0; k < 5 - i; k++)
         { // The inner loop is the number of comparisons per trip. The I trip compares len-i times, because the first time has bubbled the largest element to the last position
            if (bucket[i][k] > bucket[i][k + 1])
            { // Compare adjacent elements, reverse order will switch positions
               temp = bucket[i][k];
               bucket[i][k] = bucket[i][k + 1];
               bucket[i][k + 1] = temp; }}}}// Restore the sorted result in the bucket to the original array
   for (i = 0; i < 5; i++)
   {
      for (j = 0; j < 6; j++)
      {
         arr[i * 6+ j] = bucket[i][j]; }}}Copy the code

10. Radix sort

The basic idea

Radix sort is a kind of non-comparative integer sort algorithm. Its principle is to cut the integers into different numbers according to the number of digits, and then compare them according to each number. Since integers can also represent strings (such as names or dates) and floating-point numbers in a particular format, radix sort is not restricted to integers.

animation

implementation

void radixSort(a)
{
   int arr[] = {31.25.33.40.78.26.1.52.88.63.22.44.69.42.17.10.11.28.19.47};
   int LEN = (int)sizeof(arr) / sizeof(*arr);

   int LEVEL = 0; // The largest number of digits
   // Find the maximum number to determine the number of digits
   int max = arr[0], i;
   for (i = 0; i < LEN; i++)
   {
      if (arr[i] > max)
         max = arr[i];
   }
   for (i = max; i > 0; i /= 10)
   {
      LEVEL++;
   }
   // printf("%d",LEVEL);

   for (i = 0; i < LEVEL; i++)
   {
      radix_sort(arr, LEN, i);
      for (int i = 0; i < LEN; i++)
         printf("%d ", arr[i]);
      printf("\n");
   }

   for (int i = 0; i < LEN; i++)
      printf("%d ", arr[i]);

   return 0;
}

void radix_sort(int arr[], int LEN, int level)
{
   int bucket[10] = {0}, temp[LEN], i, j;

   int flag = pow(10, level); // What bit is used to determine the current comparison

   // Get bits and do the first radix sort
   // Get bits and store them in buckets
   for (i = 0; i < LEN; i++)
   {
      bucket[arr[i] / flag % 10] + +; } bucket[0]--;
   for (i = 1; i < 10; i++)
   {
      bucket[i] += bucket[i - 1];
   }

   // Copy the original array into the temp array after sorting it for the first time based on the bucket result
   // Note that reverse traversal is required
   for (i = LEN - 1; i >= 0; i--)
   {
      temp[bucket[arr[i] / flag % 10]] = arr[i];
      bucket[arr[i] / flag % 10]--;
   }

   // Use temp array to modify the original array
   for (i = 0; i < LEN; i++) { arr[i] = temp[i]; }}Copy the code

---