Sorting algorithm: insertion sort and shell sort

Today we will talk about two classic sorting methods, insertion sorting and shell sorting. You can think of shell sort as an upgraded version of insertion sort.

Insertion Sort

The algorithm description of Insertion-Sort is a very simple and intuitive sorting algorithm. Its complexity is similar to bubble sort. The working principle is to construct an ordered sequence. For unsorted data, scan from back to front in the sorted sequence to find the corresponding position and insert it.

I found an animated picture from the Internet as follows:

The process is as follows:

• From the first element Initially, the element can be considered to have been sorted;

• Take out the next element and scan from back to front in the sorted element sequence;

• If the element (sorted) is greater than the new element, move the element to the next position;

• Repeat step 3 until you find the sorted element that is less than or equal to the new element Position;

• After inserting the new element at this position;

• Repeat steps 2~5.

Code implementation (C language is used here):

void insort (int arr[], int len)
{
    int i,current,preindex;
    for (i = 1; i < len; i++) {
        preindex = i - 1;
        current = arr[i];
        while (preindex >= 0 && current < arr[preindex]) {
            arr[preindex + 1] = arr[preindex];
            preindex --;
        }
        arr[preindex + 1] = current;
    }
}

shell sorting

After understanding insertion sort, it is easy to understand shell sort.

Shell sorting algorithm was invented by D.L.Shell in 1959. Its basic idea is to compare distant elements first, which can quickly reduce a large number of disordered situations, thus easing subsequent work. The distance between the compared elements gradually decreases until it is reduced to 1, at which time the sorting becomes the exchange of adjacent elements.

Hill sorting is to group records according to a certain increment in the table, and use the direct insertion sorting algorithm to sort each group; as the increment gradually decreases, each group contains more and more keywords. When When the increment is reduced to 1, the entire file is divided into one group, and the algorithm terminates.

Process demonstration (this picture was also found online):

Code implementation (C language is used here):

void shell_sort (int arr[], int len)
{
    int gap,i,current,preindex;
    for (gap = len / 2; gap > 0; gap /= 2) {
        for (i = gap; i < len; i++) {
            preindex = i - gap;
            current = arr[i];
            while (preindex >= 0 && current < arr[preindex]) {
                arr[preindex + gap] = arr[preindex];
                preindex -= gap;
            }
            arr[preindex + gap] = current;
        }
    }
}

The above is the detailed content of Sorting algorithm: insertion sort and shell sort. For more information, please follow other related articles on the PHP Chinese website!