Insertion sorting of data structure

Insertion sorting of data structure

Insert some code for sorting

Insert sort includes direct insert sort, half insert sort, 2-way insert sort and table sort.

  1. The idea of direct insertion sorting is to take the first as the sorted one and record it as the current data directly from the second one. Then use the current data to compare with the previous data, and move back the number greater than the current data. When the number less than the current data is found, put the current data in.
  2. Half insert sort is similar to direct insert sort. It only uses the binary search method to find the position of the current data when finding the number smaller than the current data. low is the position that should be inserted, but it only reduces the number of comparisons, and the number of moves does not change.
  3. 2-way insertion sorting: use a circular array (0-1 plus the array length to move from 0 to n-1). The first position (subscript is 0) is placed in the first position of the circular array. First and final both point to the first, and then start from the second.
    If the current data is greater than final, final + + then places the current data in final.
    If the current data is less than first, then (first-1+length)% length and put the current data in first.
    If the current data is less than final and greater than first, you need to move all the numbers in front of the current data that are greater than the current data.
    Table sorting is not written here.
// An highlighted block
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 8
//Direct insert sort
void InsertSort(int a[]){
	printf("Direct insert sort\n");
	int i,j;
	for(i=2;i<9;i++){
		if(a[i]<a[i-1]){
			a[0]=a[i];
			a[i]=a[i-1];
			for(j=i-2;a[0]<a[j];--j){
				a[j+1]=a[j];
			}
			a[j+1]=a[0];
		}
	}
}
//Binary Insertion Sort 
void InsertSort2(int a[]){
	printf("Binary Insertion Sort \n");
	int i,j,m;
	int low,high;
	
	for(i=2;i<9;i++){
		a[0]=a[i];
		low=1;
		high=i-1;
		while(low<=high){
			m=(low+high)/2;
			if(a[0]<a[m])high=m-1;
			else low=m+1;
		}//while
		for(j=i-1;j>=low;--j){
			a[j+1]=a[j];
		}
		a[low]=a[0];//high+1==low;
	}
}

void p2_InsertSort(int a[]){
	printf("2-Path insertion sort\n");
	int *d=(int *)malloc(sizeof(int)*LENGTH);
	int first,final;
	int i,j;
	first=final=0;
	d[0]=a[1];
	for(i=2;i<=LENGTH;i++){
		if(a[i]<=d[first]){
			first=(first-1+LENGTH)%LENGTH;
			d[first]=a[i];
		}else if(a[i]>=d[final]){
			++final;
			d[final]=a[i];
		}else{
			j=final++;
			while(a[i]<d[j]){
				d[(j+1)%LENGTH]=d[j];
				j=(j-1+LENGTH)%LENGTH;
			}
			d[(j+1)%LENGTH]=a[i];
		}
	}
	for(i=1;i<=LENGTH;i++){
		a[i]=d[(first+i-1)%LENGTH];
	}
	
}

int main()
{
	int i;
	int a[9]={0,38,49,65,97,76,13,27,49};	
//	int a[5]={6,5,4,3,2};
//	p2_InsertSort(a);
//	InsertSort2(a);

	for(i=1;i<9;i++){
		printf("%d\t",a[i]);
	}
	printf("\n");
	return 0;
}

Keywords: less

Added by fireant on Wed, 04 Dec 2019 09:12:15 +0200