Eight Sorts of Data Structures

1. Direct insertion sort


Green is the insertion element, red is the insertion element.
For each number inserted, the element to be inserted is compared in turn with the element previously inserted. If it is larger than it, it covers the position of the element to be inserted and places the element to be inserted in the position of the first element. If it is smaller than it, it is inserted directly in the back.

#include<stdio.h>
void InsertSort(int *a, int length)
{
	int i, j, tmp;
	for(i = 1; i < length; i++)		//Because of 10 numbers, the array coordinates range from 0 to 9. The first number does not need to be sorted. So loop length - 2 times
	{
		tmp = a[i];  //Record inserted elements
		for(j = i - 1; j >= 0; j--) //Because j=i - 1 refers to the remaining elements in front of it, it is compared in turn with the elements to be inserted.
		{
			if(a[j] > tmp)  
			{
				a[j + 1] = a[j];   //If the preceding element is larger than the element to be inserted, move the preceding element to the position of the inserted element.
			}
			else  
			{
				break;  //If it's smaller than that, don't execute it. Jump out of the loop and execute the following commands.
			}
		}
		a[j + 1] = tmp;   //Put the recorded element in the next place of the array element, which is after the element that has been compared.
	}
}

int main()
{
	int array[] = {32,45,65,12,56,76,56,12,84,23};
	int length = sizeof(array) / sizeof(array[0]);
	int i;
	for (i = 0; i < length; i++)
	{
		InsertSort(array,  length);
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

2. Hill Sorting


#include<stdio.h>
void ShellSort(int *a, int length)
{
	int i, j, tmp, h;
	for(h = length / 2; h > 0; h = h / 2)  //Define the increment, which is the number of iterations of the step size. Half of the data is the most.
	{
		for(i = h; i < length; i++)  //Define the number of cycles, because Hill sort needs to be compared by step size. 
		{
			tmp = a[i];   //Recording step element
			for(j = i - h; j >= 0; j = j -h) //Number of comparisons of step-size elements
			{
				if(a[j] > tmp)
				{
					a[j + h] = a[j];
				}
				else
				{
					break;
				}
			}
			a[j + h] = tmp;
		}
	}
}

int main()
{
	int array[] = {32,45,65,12,56,76,56,12,84,23};
	int length = sizeof(array) / sizeof(array[0]);
	int i;
	for (i = 0; i < length; i++)
	{
		ShellSort(array,  length);
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

3. Sorting by Bubble Method

#include<stdio.h>

void maopaoSort(int *a, length)
{
	int i,j,tmp;
	for(i = 1; i < length ; i++) //The total number of cycles to find the largest element, according to the bubble method, the last number of emergence must be the smallest.
												//No looping is required. So the number of cycles is length - 1 
	{
		for(j = 0; j < length -i -1; j++) // Compare the elements in turn, and put the big ones behind.
		{
			if(a[j] > a[j + 1])
			{
				tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
			}
		}
	}
}
int main()
{
	int array[] = {32,45,65,12,56,76,56,12,84,23};
	int length = sizeof(array) / sizeof(array[0]);
	int i;
	for (i = 0; i < length; i++)
	{
		maopaoSort(array,  length);
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

4. Quick Sorting

An array, select a partition (cardinality), put the smaller cardinality to the right, and the larger cardinality to the left.
Then the small part and the large part are divided into a new array, and then a base number is selected from the small array, in which the small part is divided into smaller and larger parts. In dividing these two parts into two new arrays, the above steps are carried out...
We now rank (66, 38, 55, 93, 20, 42, 54, 95, 70, 68)
First, we define three quantities, i, j, flag (cardinality). I is the following table of the first value of the array, i=0. J is the bottom table of the last value of the array, j=9, flag is the first value of the array, flag=56. Now what we need to do is to put all the smaller numbers in the array in front of him and all the larger ones behind him.

The first step is to look left (front) from j and find the first number smaller than the cardinal number, which is 54 with the subscript of 6. We exchange 54 with the cardinal number 66 so that the array becomes
(54, 38, 45, 93, 20, 42, 66, 95, 70, 68), j=6

The second step is to look right (after) from i and find the first number larger than the cardinality, which is the number 93 with the subscript of 3. We exchange 93-with the cardinality 66 so that the array becomes
(54, 38, 55, 66, 20, 42, 93, 95, 70, 68), i=3

The third step is to continue to look left from J (at this time j=6) and find the number smaller than the cardinal number, which is the number 42 with the subscript of 5. We will exchange 42 with the cardinal number.
Get the array (54, 38, 55, 42, 20, 66, 93, 95, 70, 68), where j=5

The fourth step is to look right from I (i = 3 at this time), find the number larger than the cardinal number, until i=j, we find that before j, we can not find the number larger than the cardinal number, and then the first round of quick sorting has ended. At this time, the number before the cardinal number is smaller than him, after him, it is larger than him, and we will go before the cardinal number. The latter two regions are redefined into two new disordered arrays, and the process is repeated until they are decomposed into one value in each re-divided region (an individual, the divided array has only one element), and the sorting is completed.

#include<stdio.h>
void QuickSort(int *a, int low, int high) //low and high are the head and tail of the subscripts of the array, respectively.
{
	if(low >= high)
	{
		return;
	}
	int i = low;  //Subscript i is the part less than the cardinality, from 0 to right of the array subscript
	int j = high; //Subscript j is the number of parts larger than the cardinality, moving from the last bit of the array to the left.
	int base = a[low]; //Take the cardinality, usually the first element of an array.
	while(i < j)   //When i = j, the array has been split into two parts
	{
		while(i < j && a[j] > base)  
		{
			j--;       //If the element in the position J is larger than the cardinality, that is normal, just move the subscript j one bit to the left. Then look for it.
		}
		if(i < j)
		{
			a[i++] = a[j];   //If the element of subscript j is less than the cardinality, the position is exchanged with the cardinality
		}
		while(i < j && a[i] < base)   
		{
			i++;  //If the element in the position of I is less than the cardinality, it is normal, just move the subscript i one bit to the right. Then look for it.
		}
		if(i < j)
		{
			a[j--] = a[i]; //If the element of subscript i is larger than the cardinality, the radix is exchanged.
		}
	}
	QuickSort(a, low, i -1);      //The decimal parts are reassembled into an array, which is called and then divided downward.
	QuickSort(a, i + 1, high);   //The large part of the partition is re-divided into an array, which is called and then divided downward.
}

int main()
{
	int array[] = {32,45,65,12,56,76,56,12,84,23};
	int length = sizeof(array) / sizeof(array[0]);
	int i;
	for (i = 0; i < length; i++)
	{
		QuickSort(array,  0, length - 1);
		printf("%d ", array[i]);
	}
	printf("\n");
	return 0;
}

5. Simple selection sort.

For a given set of records (usually taking array[0], the first element of the array), record the data class size of its subscripts, then compare the size in turn, find smaller than it, record subscripts, and record data. After the first round of comparison, the minimum record is obtained, and then the record is exchanged with the location of the first record.
Secondly, the records other than the first record are sorted in the second round, and the smallest record is obtained and the position of the second record is exchanged.
Load the process until there is only one record for comparison.

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

void SelectSort(int *a, int length)
{
	int i, j, tmp, mIndex;  //(tmp is recorded data, mIndex is recorded coordinates)
	for(i = 0; i < length - 1; i++)
	{
		tmp = a[i];  //Record the contents of the first element.
		mIndex = i; //Record the subscript of the first element.
		for(j = i + 1; j < length; j++)  //The order is larger, starting with the second element.
		{
			if(a[j] < tmp) 
			{
				mIndex = j;  //If it's smaller than that, update the subscript
				tmp = a[j];  //Less than it, update the content
			}
		}
		if(mIndex != i)
		{
			a[mIndex] = a[i];  //Give the first recorded decimal a new minimum
			a[i] = tmp; // Put the smallest number in the first element.
		}
	}
}

int main()
{
	srand(time (NULL));
	int array[10] = {43,54,12,54,34,67,87,97,23,64};
	int i, length = sizeof(array) / sizeof(array[0]) ;
	for(i = 0; i < length; i++)
	{
		SelectSort(array, length);
		printf("%d ", array[i]);
	}
	printf("\n");
}

6. Heap sorting

      Heap sorting is a special tree-like data structure. Each node has a value. Usually, the heap refers to a complete binary tree. The value of the root node is less than (or greater than) the value of two sub-nodes. At the same time, the two sub-trees of the root node are also a heap. The heap sorting mainly includes two processes: one is to build the heap, the other is to exchange the position of the top element and the last element of the heap. Steps:
  1. The sequence is constructed into a complete binary tree.
  2. The minimum value can be obtained by transforming this ordinary complete binary tree into a heap.
  3. Minimum output value;
  4. By deleting the root node and continuing to transform the remaining trees into piles, the sub-minimum value can be obtained.
  5. Output sub-small value;
  6. Repeated transformation, output sub-small value, sub-small value, until all nodes are output, and then get a sort.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void HeapAdjust(int *a, int root, int last)   //Root denotes the root node subscript last denotes the last subscript
{
	int i;
	int tmp = a[root];

	for (i = 2 * root + 1; i <= last; i = i * 2 + 1)
	{
		if (i + 1 <= last && a[i] < a[i + 1])   //Find the maximum of two numbers
		{
			i++;
		}
		if (a[i] > tmp)
		{
			a[root] = a[i];    //Covering Root Nodes with Larger Numbers
			a[i] = tmp;
			tmp = a[i];
			root = i;
		}
		else
		{
			break;
		}

	}
}

void swap(int *x, int *y)
{
	int t = *x;
	*x = *y;
	*y = t;
}

void HeapSort(int *a, int length)
{
	int i;
	for (i = length / 2 - 1; i >= 0; i--)
	{
		HeapAdjust(a, i, length - 1);    //Building Big Top Reactor
	}

	for (i = length - 1; i >= 1; i--)
	{
		swap(&a[0], &a[i]);
		HeapAdjust(a, 0, i - 1);
	}
}

int main()
{
	srand(time(NULL));
	//int array[10] = {4, 5, 3, 8, 0, 78, 5, 3, 9, 10};
	int array[2048] = {0};

	int i;
	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		array[i] = rand() % 1000;
	}
	
	printf("Start sorting\n");
	HeapSort(array, sizeof(array) / sizeof(array[0]));
	printf("End of Sort\n");

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");

	return 0;
}

7. Merge Sort

The principle is as follows: For a given set of records, two adjacent subsequences of length 1 are merged and n/2 ordered subsequences of length 2 or 1 are obtained. After merging the two subsequences, the process is repeated until an ordered sequence is obtained.

Divide the array into half, try to make the left and right arrays into ordered arrays, and then divide them into half, until the left and right arrays are merged into ordered arrays.
Merge operation: the first element of the two arrays compares the size, the small element is placed in the first element of the original array, and then the first element of the two arrays is compared.
(That is to say, except for the original array, two arrays need to be rebuilt)

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

void Merge(int *a, int start, int middle, int end)   //(array, array header subscript, array middle subscript, array tail subscript)
{
	int left_length = middle - start + 1;   //Length on the left is the middle subscript minus the head subscript plus 1
	int right_length = end - middle;
	int *L = (int *)malloc(sizeof(int) * left_length);  //Apply for continuous left-length byte space on the left
	int *R = (int *)malloc(sizeof(int) * right_length);

	int k, i, j;    //k denotes the original array subscript i denotes the L subscript j denotes the R subscript

	for (k = start, i = 0; i < left_length; i++, k++) 
	{ 
		L[i] = a[k];   //Put the elements of the left array into the left space of the application
	} 

	for (k = middle + 1, j = 0; j < right_length; j++, k++)
	{
		R[j] = a[k]; //Put the array elements on the right into the right space of the application.
	}

	for (i = 0, j = 0, k = start; i < left_length && j < right_length; k++)
	{
		if (L[i] < R[j]) 
		{
			a[k] = L[i];
			i++;
		}
		else
		{
			a[k] = R[j];
			j++;
		}
	}
//If there are any left or right arrays left, put them in directly.
	for (; i < left_length; i++, k++)  
	{
		a[k] = L[i];
	}

	for (; j < right_length; j++, k++)
	{
		a[k] = R[j];
	}
}

void MergeSort(int *a, int start, int end)    //Split (array, subscript of array head, subscript of array tail)
{
	if (start >= end)   //When the head subscript is larger than the tail subscript, jump out of the cycle (when divided into a single individual)
	{
		return;
	}

	int middle = (start + end) / 2; // Find the middle point
	MergeSort(a, start, middle); //Then split the left array
	MergeSort(a, middle + 1, end);   //Divide the array on the right and then split it up

	Merge(a, start, middle, end); //Merge operation
}

int main()
{
	srand(time(NULL));
	//int array[10] = {4, 5, 3, 8, 0, 78, 5, 3, 9, 10};
	int array[2048] = {0};

	int i;
	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		array[i] = rand() % 1000;
	}
	
	printf("Start sorting\n");
	MergeSort(array, 0, sizeof(array) / sizeof(array[0]) - 1);
	printf("End of Sort\n");

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");

	return 0;
}

8. Cardinal Sorting

Radix Sorting is a method of relating single logical keywords with the help of the idea of multi-keyword sorting. Cardinal sorting does not require comparison between recorded keywords.
There are two main processes:
(1) Distribution, starting from the bit, is put into barrels 0-9 according to the bit value (0-9) (for example, 53, 3, and 3).
(2) Collect and place the data in barrels 0-9 in an array in order.

The order of new arrays collected is sorted from the elements in bucket 0-9.
Put them into barrels 0-9 in sequence.

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

void RadixSort(int *a, int length)    //split
{
	int max = a[0], i, radix = 1;
	for (i = 1; i < length; i++)
	{
		if (a[i] > max)
			max = a[i];
	}

	int *tmp = (int *)malloc(sizeof(int) * length);

	while (max / radix != 0)
	{
		int bucket[10] = {0};
		for (i = 0; i < length; i++)             //Get the bits of each element (ten...).
		{
			tmp[i] = a[i] / radix % 10;     
			bucket[tmp[i]]++;                   //Statistics of the number of elements per barrel
		}

		for (i = 1; i < length; i++)
		{
			bucket[i] += bucket[i - 1];
		}

		for (i = length - 1; i >= 0; i--)    //Collect and place a[i] elements in tmp arrays in order
		{
			tmp[bucket[a[i] / radix % 10] - 1] = a[i];
			bucket[a[i] / radix % 10]--;
		}

		for (i = 0; i < length; i++)
		{
			a[i] = tmp[i];
		}

		radix = radix * 10;
	}

	free(tmp);
}

int main()
{
	srand(time(NULL));
	//int array[10] = {4, 5, 3, 8, 0, 78, 5, 3, 9, 10};
	int array[2048] = {0};

	int i;
	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		array[i] = rand() % 1000;
	}
	
	printf("Start sorting\n");
	RadixSort(array, sizeof(array) / sizeof(array[0]));
	printf("End of Sort\n");

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");

	return 0;
}

Tags: less

Posted on Wed, 14 Aug 2019 06:40:20 -0700 by ozace