This is the 14th article in a series on Data Structures and Algorithms: Simple Methods.

  1. | sequence table data structure
  2. | linked list data structure
  3. | stack data structure
  4. | queue data structure
  5. | double linked list data structure and circular linked list
  6. | binary tree data structure of the concepts and principles
  7. | binary tree data structure to create and traverse the implementation
  8. Binary tree data structure | cues
  9. | binary heap data structure
  10. | priority queue data structure
  11. | sequential search and binary search algorithm
  12. | binary search tree data structure
  13. Sorting algorithm animation solution | violence sorting and bubble sort

In article [sort bubble sort algorithm animation | violence sorting and solution 】, we introduced the violent sort bubble sort and the two sorting algorithm, is a starting point. At the same time points out the shortcomings of violence sort and bubble sort hard.

The simple selection sort described in this article “cures” the “hard wounds” of the violence and bubble sorts mentioned above.

The idea is to start with the first element in the array and use it as the base element. Then find the smallest element after the base element. If the smallest element is smaller than the base element, swap the two. Otherwise, no swap.

So, like this, the minimum must be sorted by a number of comparisons and a swap, and then we say that one round of sorting is done, and after a number of rounds of sorting, the sorting is done.

We need three variables:

  • variablei: used to control the number of rounds;
  • variablej: The subscript of the element after the base element;
  • variablemin: subscript of the smallest element found.

Two nested loops are required:

  • The outer loop is used to control the number of rounds;
  • The inner loop is used to control a number of comparisons and at most one exchange per round.

The dynamic process is as follows:

Violent sorting and bubble sorting are more like “mindless” swap sorting, that is, we don’t know what the maximum or minimum value is until the round is over, so we have to iterate, swap all the elements of the round as we go, and when the round is over, we have an element. Usually, there are several comparisons and exchanges in a round of sorting.

A simple selection sort is a “smart” sort, in which we compare all the elements of the round before swapping, find the smallest element, and swap it directly to where it belongs. Typically, there are several comparisons and at most one swap in a round of sorting.

The code implementation is as follows:

/* * Simple selection sort * array: array * length: array length */
void simple_selection_sort(int *array.int length)
{
    int i, j, min;
    for (int i = 0; i < length - 1; i++) {
        min = i; // The minimum element is initialized to the base element
        // Find the smallest element
        for (int j = i + 1; j < length; j++) {
            if (array[min] > array[j]) { min = j; }}// A value smaller than the base element is found in the element following the base element
        if(i ! = min) { swap(array, i, min); / / exchange}}}Copy the code

Complete code please visit lot | Gitee acquisition.

Please correct me if there are any mistakes.