Direct insert sort and Hill sort

Preface ： Both direct insertion sort and Hill sort belong to insertion sort , The idea of sorting them is ： Insert the records to be sorted into an ordered sequence one by one according to their key values , Until all the records are inserted, a new ordered sequence is obtained

Be careful ： All sorts in the following are in ascending order

One 、 Direct insert sort

  Insert sort ideas directly ： Each time a record to be sorted （ Elements ）, Insert the size of its key into the proper position of a set of records that have been arranged , Until all records to be sorted are inserted

1.1 Single pass sorting

Insert the element to be inserted x Insert [0,end] An ordered sequence of , Compare from back to front , When x Less than arr[end] when ,arr[end+1] = arr[end],end reduce 1. When end < 0 or x >= arr[end] When , Exit loop , and arr[end+1] = x

Code implementation

int	Sort(int* arr,int size,int x)
{
    
	int end = size-1; 
	while(end >= 0)
	{
    
		if(x < arr[end])
		{
    
			arr[end+1] = arr[end];
			end--;
		}
		else
		{
    
			break;
		}
	}
	arr[end+1] = x;
}

1.2 Direct insertion sort implementation

  When an array has n Elements , The array subscript range is : [0,n-1], You can put the second 1 Elements as an ordered sequence , Will be the first 2 Elements are sorted in a single pass , And then 2 Elements as an ordered sequence , Will be the first 3 Elements are sorted in a single pass … … Until the front n-1 Elements as an ordered sequence , Will be the first n Elements are sorted in a single pass

void InsertSort(int* arr, int n)
{
    
	assert(arr);
	for (int i = 0; i < n - 1;i++) //  The number of times to be sorted is n-1, Subscript less than or equal to i The elements of are already ordered , By default, the first element is ordered , So the subscript is from 0 Start 
	{
     
		int end = i;  
		int elem = arr[end+1]; //  Elements to be inserted 
		while (end >= 0)
		{
    
			if (elem < arr[end])
			{
    
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
    
				break;
			}
		}
		arr[end + 1] = elem; 
	}
}

1.3 Time complexity and space complexity

When the sequence to be sorted is in reverse order , Time complexity is the worst ：O(N^2) When the sequence to be sorted itself is ordered , The time complexity is the best ：O(N) . Direct insertion sorting uses only constant auxiliary variable space , Spatial complexity ：O(1)

explain ：
 ● The closer the elements in the sequence are to order , The more time efficient it is to insert the sort directly , Sequence reverse , Efficiency is very low
 ● Direct insertion sorting is a stable sorting algorithm

Two 、 Shell Sort

  Direct insertion sorting is very efficient in two cases , Situation 1 ： When the sequence to be sorted itself is close to order , Only a few insertion operations are needed to complete the sorting of the whole sequence . Situation two ： When the number of elements in the sequence to be sorted is relatively small .

  Hill sort is an optimization of direct insert sort , Hill's idea of sequencing ： Choose an integer first gap, hold The sequence to be sorted is divided into gap Subsequence （ Group ）, All distances are gap The elements of are in the same subsequence , At this time, the number of elements in each subsequence is relatively small , then Perform direct insertion sort on each subsequence . Repeat the above work of grouping and sorting . When the whole sequence is basically in order, a direct insertion sort is performed , Make all the elements in the sequence orderly

1. Multiple grouping pre sorting （ Make the sequence close to order ）
2. Direct insert sort （ Make the sequence orderly ）
   

2.1 The first sequence of a set of subsequences

int gap = 5;
int end = 0; //  Because it is the first group of subsequences ,end=0
int elem = arr[end+gap];
while(end>=0)
{
    
	if(elem < arr[end])
	{
    
		arr[end+gap] = arr[end];
		end-=gap;	
	}
	else
	{
    
		break;
	}
}

arr[end+gap] = elem;

2.2 Direct insertion sorting of a set of subsequences

int gap = 2;
for(int i = 0;i < n-gap;i += gap) // n  Is the number of array elements 
{
    
	int end = i; 
	int elem = arr[end+gap];
	while(end >= 0)
	{
    
		if(elem < arr[end])
		{
    
			arr[end+gap] = arr[end];
			end-=gap;	
		}
		else
		{
    
			break;
		}
	}
	arr[end+gap] = elem;
}

2.3 One pre sort

int gap = 2;
for(int j = 0;j<gap;j++) //  Yes gap Group subsequences are sorted by direct insertion 
{
    

	for(int i = j;i < n-gap;i += gap) //  Directly insert and sort each group of subsequences 
	{
    
		int end = i; 
		int elem = arr[end+gap];
		while(end >= 0) //  Sort a certain trip of a group 
		{
    
			if(elem < arr[end])
			{
    
				arr[end+gap] = arr[end];
				end-=gap;	
			}
			else
			{
    
				break;
			}
		}
		arr[end+gap] = elem;
	}
}

2.4 One pre sort （ Code simple version ）

/* 2.3  The idea of one-time pre sorting ： It's right gap Group subsequences are sorted by direct insertion , That is, insert and sort the first group of subsequences directly 、  Then insert and sort the second group of subsequences directly ...... Finally, to the gap Group subsequence direct insertion sort  2.4  The idea of one-time pre sorting ： Yes gap Group subsequences are mixed for direct insertion sorting , Because a group of subsequences needs to be sorted multiple times , You can start with   The first set of subsequences is sorted for the first time 、 Sort the second set of subsequences for the first time ...... Right. gap Group subsequences for the first sorting .  Then sort the first group of subsequences for the second time 、 Sort the second subsequence ...... Right. gap Group subsequences for the second sorting . ......  Finally, the first group of subsequences is sorted for the last time 、 Then sort the second group of subsequences for the last time ...... Finally, to the gap Group subsequences for the last sorting . */
int gap = 2;
for(int i = 0;i < n-gap;i++) //  Yes gap Group subsequences are mixed for direct insertion sorting 
{
    
	int end = i; 
	int elem = arr[end+gap];
	while(end >= 0) 
	{
    
		if(elem < arr[end])
		{
    
			arr[end+gap] = arr[end];
			end-=gap;	
		}
		else
		{
    
			break;
		}
	}
	arr[end+gap] = elem;
}

2.5 Shell Sort

Shell Sort ：1. Perform multiple grouping pre sorting 2. Direct insert sort

To carry out multiple grouping and pre sorting, you must first determine gap Value , But yes. gap How to get the value to maximize the efficiency of hill sorting time is a mathematical problem . Here we use gap=[n/2]
gap = [gap/2] How to choose , That is, the first grouping pre sorting gap The value is half the number of array elements , Subsequent grouping pre sorting gap The value is pre sorted by the last grouping gap Half of the value , When gap=1 It is equivalent to direct insertion sorting

void ShellSort(int* arr, int n)
{
    
	assert(arr);
	int gap = n;
	while (gap > 1)
	{
    
		gap /= 2; //  When gap Greater than 1 It is multiple grouping and pre sorting , When gap be equal to 1 It is a direct insertion sort 
		for (int i = 0; i < n - gap; i++) 
		{
    
			int end = i;
			int elem = arr[end + gap];
			while (end >= 0)
			{
    
				if (elem < arr[end])
				{
    
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
    
					break;
				}
			}
			arr[end + gap] = elem;
		}
	}
}

2.6 Time complexity and space complexity

about gap There are many ways to get values , And the array is close to order after multiple grouping and pre sorting , Subsequent grouping pre sorting and direct insertion sorting have fewer and fewer comparisons per trip . So the time complexity analysis of Hill sort is a very complex problem , The time complexity is about O(N^1.3) . Spatial complexity ：O(1)

explain ：
 ● Hill sort is suitable for the case of a large number of elements in the sequence
 ● Hill sort is an unstable sort algorithm

3、 ... and 、 Direct insertion sort and Hill sort performance test

Sorting time efficiency and CPU Closely related , The results measured on different computers may be different , We only need to pay attention to the time difference between the two sorts on the same computer

3.1 Basic code

Because it needs to be tested in many cases , To avoid unnecessary code , In subsequent tests, you only need to paste the basic code

#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <stdlib.h>

void InsertSort(int* arr, int n)
{
    
	assert(arr);
	for (int i = 0; i < n - 1;i++) //  The number of times to be sorted is n-1, Subscript less than or equal to i The elements of are already ordered 
	{
     
		int end = i;  
		int elem = arr[end+1]; //  Elements to be inserted 
		while (end >= 0)
		{
    
			if (elem < arr[end])
			{
    
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
    
				break;
			}
		}
		arr[end + 1] = elem; 
	}
}

void ShellSort(int* arr, int n)
{
    
	assert(arr);
	int gap = n;
	while (gap > 1)
	{
    
		gap /= 2; //  When gap Greater than 1 It is multiple grouping and pre sorting , When gap be equal to 1 It is a direct insertion sort 
		for (int i = 0; i < n - gap; i++) 
		{
    
			int end = i;
			int elem = arr[end + gap];
			while (end >= 0)
			{
    
				if (elem < arr[end])
				{
    
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
    
					break;
				}
			}
			arr[end + gap] = elem;
		}
	}
}

3.2 When the number of array elements is small

The number of array elements is ：1 ten thousand , The two array elements are exactly the same , Use direct insert sort and Hill sort respectively

void test()
{
    
	
	int N = 10000; //  Number of array elements 

	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
    
		arr1[i] = rand()%1000; //  Generate [0,999] Random numbers in the range 
		arr2[i] = arr1[i]; //  Array arr2 Element equals array arr1 Elements 
	}

	int begin1 = clock(); //  Time before sorting 
	InsertSort(arr1, N);
	int end1 = clock(); //  Time after sorting 

	int begin2 = clock();
	ShellSort(arr2, N);
	int end2 = clock();

	printf("InsertSort：%d\n", end1 - begin1);
	printf("ShellSort：%d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}


int main()
{
    
	srand((unsigned int)time(NULL));
	test();
	return 0;
}

Output （ The unit is millisecond ）

InsertSort：15
ShellSort：1

Conclusion ： When the number of elements is small , There is not much difference in the time between direct insertion sorting and Hill sorting , When the number of elements is very small , Direct insert sort takes less time than Hill sort

3.3 When the number of array elements is large

The number of array elements is ：100 ten thousand , The two array elements are exactly the same , Use direct insert sort and Hill sort respectively

void test()
{
    
	
	int N = 1000000; //  Number of array elements 

	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
    
		arr1[i] = rand()%1000; //  Generate [0,999] Random numbers in the range 
		arr2[i] = arr1[i]; //  Array arr2 Element equals array arr1 Elements 
	}

	int begin1 = clock(); //  Time before sorting 
	InsertSort(arr1, N);
	int end1 = clock(); //  Time after sorting 

	int begin2 = clock();
	ShellSort(arr2, N);
	int end2 = clock();

	printf("InsertSort：%d\n", end1 - begin1);
	printf("ShellSort：%d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}


int main()
{
    
	srand((unsigned int)time(NULL));
	test();
	return 0;
}

Output （ The unit is millisecond ）

InsertSort：148991
ShellSort：121

Conclusion ： When there are many elements , There is a huge time gap between direct insertion sorting and Hill sorting , Hill sort is far better than direct insert sort

3.4 Direct insertion sorting order and reverse order test

The number of array elements is ：1 ten thousand ,arr1 For order ,arr2 In reverse order , All use direct insertion sorting

void test()
{
    
	
	int N = 10000; //  Number of array elements 

	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
    
		arr1[i] = i; // arr1 For order 
		arr2[i] = N-arr1[i]; // arr2 In reverse order 
	}

	int begin1 = clock(); //  Time before sorting 
	InsertSort(arr1, N);
	int end1 = clock(); //  Time after sorting 

	int begin2 = clock();
	InsertSort(arr2, N);
	int end2 = clock();

	printf("InsertSort  Orderly situation ：%d\n", end1 - begin1);
	printf("InsertSort  In reverse order ：%d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}


int main()
{
    
	test();
	return 0;
}

Output （ The unit is millisecond ）

InsertSort  Orderly situation ：0
InsertSort  In reverse order ：1948

Conclusion ： When the array is close to order , Using direct insert sorting is the most efficient , The time complexity is O(N). When the array is in reverse order , Using direct insert sorting is inefficient , The time complexity is O(N^2)

3.5 Hill sort order and reverse order test

The number of array elements is ：100 ten thousand ,arr1 For order ,arr2 In reverse order , All use Hill sort

void test()
{
    
	
	int N = 1000000; //  Number of array elements 

	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
    
		arr1[i] = i; // arr1 For order 
		arr2[i] = N-arr1[i]; // arr2 In reverse order 
	}

	int begin1 = clock(); //  Time before sorting 
	ShellSort(arr1, N);
	int end1 = clock(); //  Time after sorting 

	int begin2 = clock();
	ShellSort(arr2, N);
	int end2 = clock();

	printf("ShellSort  Orderly situation ：%d\n", end1 - begin1);
	printf("ShellSort  In reverse order ：%d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}


int main()
{
    
	test();
	return 0;
}

Output （ The unit is millisecond ）

ShellSort  Orderly situation ：36
ShellSort  In reverse order ：42

Conclusion ： Hill sort is relative to direct insert sort , In the face of reverse order, there is a good optimization