“This is the 30th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

The sorting

The concept of ordering and its application

The concept of ordering

Sort: the so-called sort, is to make a string of records, according to the size of one or some key words, increasing or decreasing the operation of the arrangement. Stability: It is assumed that there are multiple records with the same keywords in the sequence of records to be sorted. If the relative order of these records remains unchanged after sorting, that is, in the original sequence, R [I]=r[j], and r[I] is before r[j], and in the sorted sequence, r[I] is still before r[j], then the sorting algorithm is stable. Otherwise it is called unstable. Internal sort: Sort all data elements in memory. External sort: There are too many data elements to be in memory at the same time, and the sorting process requires that the data is not moved between internal and external memory.

Sorting using

Come on jingdong

University rankings

Common sorting algorithms

Common sorting algorithm implementation

Insertion sort

The basic idea

Direct insertion sort is a simple insertion sort method. Its basic idea is to insert the records to be sorted into an ordered sequence one by one according to the size of their key code values, until all the records are inserted, a new ordered sequence is obtained.

In fact, when we play poker, we use the idea of insertion sort

But the array is definitely not sorted, so we have to make the array sorted first

Let’s just strip out the print array

// Prints the array
void PrintArray(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}
Copy the code

Insertion sort

// Insert sort
void InsertSort(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; i++)	{
		int end = i;
		int x = a[end+1];
		while (end >= 0) {
			// If the number to be inserted is smaller than the number in the order, prepare to move
			if (a[end] > x) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				// If the number inserted is larger than the order, jump out
				break; }}// There are two cases
		//1. End == -1
		/ / 2. The break time
		// put x one bit before end
		a[end + 1] = x; }}Copy the code

Insert sort time complexity: O(N^2^)

Best: O(N) — Ordered (nearly ordered)

Worst: O(N^2^) — reverse order

Space complexity of insertion sort: O(1)

Hill sort (reduced incremental sort)

Hill sort is optimizing direct insert sort, and it’s super obvious, why is it optimizing, because we know that direct insert sort is very fast when it’s close to ordered, so I’m going to create that order, and get it close to O(N), and we know that the best case for sorting is O(N), And we’re pretty darn close to O(N), we’re pretty close to the ceiling

Hill sort method is also called reduced increment method. The basic idea of Hill sorting method is: first select an integer, divide all records in the file to be sorted into groups, all records with distance are divided into the same group, and sort the records in each group. Then, take, repeat the above grouping and sorting work. When =1 is reached, all records are sorted within the unified group.

Hill sequence

1. Grouping presort —- array is nearly ordered

Group by GAP, insert the group values into gap group

2. The time complexity of direct insertion is O(N).

More than a single set of lying

Multiple sets of insert

Time complexity O(GAP *(1+… +N/gap))

Best: O (N)

Best: O (N)

The bad: O (gap * (1 +… +N/gap))

The larger the gap, the faster the pre-arrangement, the less close to order after the pre-arrangement

The smaller the gap, the slower the pre-arrangement, the closer to order after the pre-arrangement

Multiple groups in a pot stew (if the group insert trouble we can also stew)

Multiple pre-sort (gap > 1)+ direct insert (gap1)= =

gap/2

gap/3

Time order N^1.3^, just remember, but Hill is cool, hill sorts fast

Test performance of direct insert sort and Hill sort (let you see what hill sort is)

code

Sort.h

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

// Sort the interface implemented
// Prints the array
extern void PrintArray(int* a, int n);
// Insert sort
extern void InsertSort(int* a, int n);
// Hill sort
extern void ShellSort(int* a, int n);
// Select sort
extern void SelectSort(int* a, int n);
/ / heap sort
extern void AdjustDwon(int* a, int n, int root);
extern void HeapSort(int* a, int n);
// Bubble sort
extern void BubbleSort(int* a, int n);
// Quicksort recursive implementation
// Quicksort the Hoare version
extern int PartSort1(int* a, int left, int right);
// Quick sort digging method
extern int PartSort2(int* a, int left, int right);
// Quick sort before and after Pointers
extern int PartSort3(int* a, int left, int right);
extern void QuickSort(int* a, int left, int right);
// Quicksort is non-recursive
extern void QuickSortNonR(int* a, int left, int right);
// merge sort recursive implementation
extern void MergeSort(int* a, int n);
// Merge sort is non-recursive
extern void MergeSortNonR(int* a, int n);
// Count sort
extern void CountSort(int* a, int n);


Copy the code

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

// Prints the array
void PrintArray(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}
// Insert sort
void InsertSort(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; i++)	{
		int end = i;
		int x = a[end+1];
		while (end >= 0) {
			// If the number to be inserted is smaller than the number in the order, prepare to move
			if (a[end] > x) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				// If the number inserted is larger than the order, jump out
				break; }}// There are two cases
		//1. End == -1
		/ / 2. The break time
		// put x one bit before end
		a[end + 1] = x; }}// Hill sort
void ShellSort(int* a, int n) {
	/ / group
	int gap = n;
	// Multiple pre-sort (gap>1) + direct insert (gap == 1)
	while (gap>1) {//gap /= 2;
		// Divide by three and we know it doesn't have to pass 1, so we add 1 to give him a condition that he must pass 1
		gap = gap / 3 + 1;
		// Lie down in groups
		int i = 0;
		for (i = 0; i < n - gap; i++) {
		int end = i;
		int x = a[end + gap];
		while (end >= 0) {
			if (a[end] > x) {
				a[end + gap] = a[end];
				// Step size is gap
				end -= gap;
			}
			else {
				break; } } a[end + gap] = x; }}}Copy the code

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

// Test sort performance comparison
void TestOP(a)
{
	// Set a random starting point
	srand(time(NULL));
	// Size of the array to be created
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		// Make sure both arrays are the same
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();// Start time
	InsertSort(a1, N);
	int end1 = clock();  // End time
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	printf("InsertSort:%d\n", end1 - begin1);// End time minus start time
	printf("ShellSort:%d\n", end2 - begin2);
	free(a1);
	free(a2);
}
// Test insert sort
void TestInsertSort(a) {
	int a[] = { 1.5.3.7.0.9 };
	InsertSort(a, sizeof(a) / sizeof(a[0]));	
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
// Test hill sort
void TestShellSort(a) {
	int a[] = { 9.1.2.5.7.4.8.6.3.5 };
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
int main(a){
	//TestInsertSort();
	//TestShellSort();
	TestOP();
	return 0;
}
Copy the code