Getting started with sorting - insert sorting and Hill sorting

Catalog

One . Sort

Two . Stability of sequencing

3、 ... and . Direct insert sort

# Insert the complexity analysis of sorting

Four . Shell Sort

# Pre sort

---

One . Sort

Sorting refers to the operation of rearranging a group of records according to the decreasing or increasing order of keywords .

There are many application scenarios of sorting in life , For example, on the shopping platform, the price or sales volume commonly used when we screen products ranges from low to high , From high to low ,csdn In essence, the ranking list on the is a sort , So learning to sort is necessary .

Two . Stability of sequencing

When the keywords in the sequence are different , Then the sorting result is unique . But when there are the same results in the sequence , Then sorting has many results . for instance , For example, there is the following array ：

int arr[] = {1, 3, 9, 3};

If you sort this array, the result is undoubtedly 1,3,3,9. But these two 3 Which row is in the front and which row is in the back ？ If these two are sorted 3 Arrange in the original relative order , Then we call this sort method stable , Otherwise it will be unstable . There is no absolute distinction between stability and instability , Each has its own application .

3、 ... and . Direct insert sort

The idea of insertion sorting is to insert an element to be sorted into an appropriate position in an ordered sequence every time , Make the sequence still orderly after insertion , Until all elements are inserted .

This idea is very similar to our playing cards , Every time we catch a card, we will insert it into the right position to make the cards in our hand orderly , Until all the cards are caught .

  So we can fight with the landlord , Grab one card at a time , And then insert it in place . Still take the above array ( In ascending order ) give an example ： In this array 1 Is the first card we caught , It's obvious that the first card doesn't have to be sorted , We continue to draw cards , The second card you catch is 3, Catch and 1 Compare ,3 No comparison 1 Small ones are in the back , Then catch 9,9 No comparison 3 Small , At the back , The last card is 3,3 Than 9 Small ones need to be compared ： Let's dial 9 This card , notice 9 In front of is a 3,3 No comparison 3 Small , So the back one 3 Put it on the front one 3 Behind ,9 In front of , Then the draw is over . Here, because of the space problem, the array setting is simple , But no matter how complicated , The process is like this .

According to the above ideas, we can think like this , Think of the first data as an ordered sequence , Then insert the latter element into the sequence , If the latter element is smaller than the previous element , Then move the previous element back a position ( Set aside this card to make room for the cards behind ), Go ahead and compare , If the latter element is larger than the former , Then insert the latter element into the next position of the previous element ( Take the next one 3 Put it on the previous one 3 Behind ,9 In front of ), A new ordered sequence is generated , Insert the next element , And so on , The sorting is completed until the last element is inserted . You can see the dynamic diagram to understand the process .

  The sorting code is as follows ：

void Insert_sort(int* arr, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int end = i;   //end Record the last element of the ordered sequence 
		int tmp = arr[end + 1];// Record the elements to be inserted , Because moving elements may overwrite the elements to be inserted 
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				--end;
			}
			else
			{
				break; // If the following element is larger than the previous element , Just jump out of the loop , Don't compare 
			}
		}
		arr[end + 1] = tmp;  // Assign the element to be inserted to the next position 
	}
}

# Insert the complexity analysis of sorting

  The time complexity of insertion sort ： The worst case is in reverse order , At this time, every element has to move , The time complexity is O(n^2).

Spatial complexity ： Insert sorting only requires constant variables , So the spatial complexity is O(1).

Four . Shell Sort

For insertion sort , When the sequence itself is relatively orderly , The efficiency of this sort of sorting is still very high , But if the processing sequence is very disordered , Time efficiency will be extremely low . At this time, a man named Hill proposed , You can pre sort , Make the sequence more orderly before inserting and sorting .

So Hill sort is essentially still insert sort , The idea is ：

1. Pre sort

2. Insertion sort

# Pre sort

The method of group insertion , Divide the sequence to be sorted into several groups , This reduces the amount of data that can be directly inserted into the sort , Insert and sort each group separately . Note that grouping data is not simple “ Piecewise segmentation ”, Instead, the elements separated by a certain increment are divided into a group .

  Take this sequence as an example , Suppose you set the increment to 2, The grouping is as follows , The elements connected by the same color line form a group .

Note that the increment is 1 Is to insert sort directly , That is, when the increment is smaller , This sequence will become more orderly . So we can gradually reduce the increment after group insertion , The final increment is 1 It's completely orderly .

about 1 One data in the Group , You can write the following code to insert ：

int end = 0;
int gap = 3;
int tmp = arr[end + gap];
while (end >= 0)
{
    if (arr[end] > tmp)
    {
        arr[end + gap] = arr[end];
        end -= gap;   
    }
    else
    {
        break;
    }
}

arr[end + gap] = tmp;

  For a set of data , Then we need to put on a cycle

		for (int i = 0; i < size - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}

explain ： Because I want to visit end + gap The value of the location , To prevent crossing the border , therefore i < size - gap. meanwhile , You can also complete all groups with this layer of circulation , You can draw pictures to feel , The question of length will not be repeated .

control gap The reduction of requires another layer of circulation ：

void Shellsort(int* arr, int size)
{

	int gap = size;   //  Set increment 
	while (gap > 1)
	{
		gap = gap / 3 + 1; 
		for (int i = 0; i < size - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}

}

Test with the following array ：

	int arr[] = { 0,0,9,1,6,8056, 94656, 4568 };
	Shellsort(arr, sizeof(arr) / sizeof(int));

result ：

 # The time complexity of Hill sort is difficult to calculate , I haven't learned yet , Wait for the next blog post to ask the big guys for advice