This is the 13th 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

This article first briefly introduces what sort is, and then introduces violent sort and bubble sort with animation.

1. What is sorting?

Sorting is ubiquitous in everyday life. Such as the ranking of test scores, the formation of PE classes from low to high, online shopping in ascending or descending order of price, and so on.

The name Student id The class results
Zhang SAN 1001 Class 2 100
Li si 1003 Class one 90
Cathy 1000 Class 3 80
Zhao six 1006 Class 2 70

In this table, we call a row of data as a record, in which name, student number and other data items are keywords, keywords are the basis of our sorting. A keyword can be a primary keyword or a secondary keyword, or even a combination of several data items.

For example, in this table, we sort by grade (secondary keywords) in descending order. You can also sort according to your student number, or sort according to your student number and your score at the same time: first arrange your score in descending order, and if your score is the same, arrange your score in ascending order.

Therefore, the essence of sorting multiple records is the sorting of keywords. If the sorting is based on multiple keywords, it can be transformed into the sorting of a single keyword.

The so-called sorting is to arrange all the elements of a sequence in an orderly manner according to the specified keywords.

So how do you implement sorting?

For example, according to the sorting of height on PE class, it is to compare the height of two people, and then short station in front, high station behind. If the tall one is first and the short one is last, switch places; Otherwise it won’t work.

Yes, sorting is done by comparison and interchange. We’re comparing keywords, and that’s what we’re sorting by. We swap the positions of the two elements, and usually we don’t really swap positions, but we swap positions by assigning intermediate variables.

/* A swap function that swaps the positions of the elements with subscripts I and j */
void swap(int *array.int i, int j)
{
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}
Copy the code

When implementing the sorting algorithm, we should pursue fewer comparisons and swaps to improve the performance of the algorithm.

For the sake of clarification, here are a few rules:

  • Sort only the array and specify the length of the arraylength = 10
  • All sorting algorithms sort in ascending order
  • Since this is for arrays, the key is the element value itself. The compare keyword is used to compare element values without distinction.

2. Violent Sort

By violence, it means that there is no trick to it, it simply runs through an array, constantly comparing and swapping. This is the easiest sorting algorithm to understand.

The core idea: starting with the first element of the array, each element is used as a base element. The base element is compared with all the elements following it. If the base element is larger than one of the elements following it, it is swapped. Otherwise the position stays the same.

When the base element is swapped with all subsequent elements, the minimum value must be sorted, and the sorting round is said to be complete. Each round has several cycles for comparison and swapping. After several rounds of sorting like this, the sorting is done.

We need two variables to mark the subscripts of the two elements being compared:

  • variablei: The index of an element;
  • variablej: the subscriptiAnd then the subscript.

We need two nested loops:

  • Outer cycle control wheel number;
  • The inner loop controls the comparison and exchange of each round.

The dynamic process is as follows:

The code implementation is as follows:

/* Violence sort * array: array * length: array length */
void violent_sort(int *array.int length)
{
    int i, j;
    // Set the number of cycles in the loop
    for (i = 0; i < length; i++) {
        // Inner loop, which compares array[I] with the element after it and controls the number of loops
        for (j = i + 1; j < length; j++) {
            if (array[i] > array[j]) { // If greater than, swap
                swap(array, i, j); }}}}Copy the code

Through the above violence ranking, we can get a first taste of the idea of ranking, that is, constant comparison and exchange.

Violent sorting has the obvious drawback that each element is compared to all the elements following it, which can easily destroy the original order of the entire array. For example, in the dynamic process above, element 40 was swapped further down after some swap. In order to arrange one element well, messing with all the elements after it, even breaking the order between them, affects efficiency.

3. Bubble Sort

Bubble sort is a very simple sorting algorithm, improved from the violence sort.

Core idea: compare two adjacent elements, when the current is greater than the latter, swap their positions; Otherwise the position stays the same.

Note: Bubble sort compares and swaps two adjacent elements, whereas violent sort compares and swaps one element with all elements following it.

When all of the adjacent elements in the array are paged and swapped, a maximum value is found and swapped at the end of the array, the sorting is done, and there are a number of loops for comparison and swapping. After a few rounds of sorting like this, the sorting is done.

We need two variables:

  • Variable I: used to control the number of rounds;

  • Variable j: element subscript, j+1 is the subscript of its adjacent elements.

We need two nested loops:

  • The outer loop controls the number of rounds
  • The inner loop controls the comparison and interchange of all adjacent elements in each round

The dynamic process is as follows:

The code implementation is as follows:

/* Bubble sort * array: array * length: array length */
void bubble_sort(int *array.int length)
{
    int i, j;
    // The outer loop controls the number of rounds. Line up one element for each round
    for (i = 0; i < length; i++) {
        // Inner loop, loop over the unsorted elements of the array
        for (j = 0; j < length - i - 1; j++) {
            // If the former is greater than the latter, swap
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1); }}}}Copy the code

Since the two elements are next to each other, after a round of comparison, one of the largest elements must be swapped to the far right, like a “big bubble” rising to the surface of the water, so we call this “bubbling sort”.

Although bubble sort ameliorates the shortcomings of violence sort, it still has some optimizations.

In the above dynamic process, the sorting is completed by round 7 (I = 6), but the comparison is still carried out after three rounds. These last three rounds are completely unnecessary, so we can improve to avoid unnecessary comparisons.

The method is to add a token variable, unsorted, to indicate whether the array is sorted. If unsorted = 0, the array is sorted, and if unsorted = 1, the array is unsorted.

Unsorted records whether an exchange has occurred in a particular sort round, and if it hasn’t, it means it’s sorted.

void bubble_sort_v3(int *array.int length)
{
    int i, j;
    int unsorted = 1; // Identify variables
    for (i = 0; i < length && unsorted; i++) {
        unsorted = 0;
        for (j = 0; j < length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                unsorted = 1; // The order is not yet in order}}}}Copy the code

Although bubble sort can avoid unnecessary comparisons and swaps, bubble sort is still similar in nature to violent sort, in that there are numerous exchanges, either between one element and all subsequent elements, or between two adjacent elements. It can also be seen from the GIF that in order to arrange an element in its correct position, we often need to exchange with multiple elements, which is the “hard wound” affecting efficiency.

Complete code please visit lot | Gitee acquisition.

Please correct me if there are any mistakes.

If you think it’s good, you can like it and follow it. More data structures and algorithms will follow.