[Data Structures] Sorting Algorithms – Bubble Sort, Quick Sort, Normalize Sort, Counting Sort

catalogs

preamble

1. Bubble Sort

2. Quick Sort

2.1Hoare version

2.2 Pit occupancy version

2.3 Front and rear pointer version

2.4 Optimization of fast sorting by triple number picking

2.5 Non-recursive version

3. Summation Sort

3.1 Recursive version

3.2 Non-recursive version

3.3 Out-of-order problems

4. Counting Sort

---

preamble

In this post, the blogger will continue to bring sorting algorithm implementation, mainly explaining the exchange sort idea of bubble sort,Three recursive and one non-recursive version of fast sorting, the recursive and non-recursive versions of the subsumption sort, and counting sorts.

---

Welcome.favorite So that you can quickly find ideas for future questions, a clever approach can be twice the result with half the effort. ========================================================================= GITEE related code:🌟fanfei_c’s warehouse🌟 =========================================================================

---

1. Bubble Sort

Bubble sort as the name suggests, the whole process of sorting is like a bubble rising, in ascending order, for example, the larger values will be exchanged with smaller values, each trip sorting can be placed in a number to the appropriate position, such as the maximum value at the end, the next largest value put the penultimate position, etc..

Image taken fromGITHUB-Olivier Wietrich

---

So we need a double layer of loop control.

• While traversing the entire sequence, the internal single-trip sort has to reduce the comparison one comparison at a time (because every time an element comes to the right place in the sort, it needs to be eliminated from the next sort)
• In the same way we know that the outer loop needs to be executed n times to get all the elements in the right place.

A summary of the properties of bubbling sort:

• Bubble sort is a very easy to understand sorting
• Time complexity: O(N^2)
• Space complexity: O(1)
• Stability: Stable

Code Implementation:

// bubbling sort
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n ; i++)
	{
		int flag = 0;
		for (int j = 1; j < n - i; j++)//decrease one element to be sorted at a time
		{
			if (a[j-1] > a[j])
			{
				swap(&a[j], &a[j - 1]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}

---

2. Quick Sort

The fast sorting algorithm was developed byTony Hall.The design is proposed, and I will explain the Hall version of the fast row, and the optimization and optimization and optimization of the fast row by the various bigwigs behind it.

fastSummary of featuresI put it at the end of the quick sort section to list it.

2.1Hoare version

Hoare’s version of the idea is not easy to understand. First of all whichever version of fast platoon.core ideaAll are arbitrary elements in the sequence of elements to be sorted as a reference value, according to the sort code will be sorted into two sub-sequence of the set, the left sub-sequence of all the elements are smaller than the reference value, the right sub-sequence of all the elements are larger than the reference value (can be interpreted as a binary tree structure), and then most of the left and right sub-sequence to repeat the process until all the elements are aligned in the corresponding position. So how do we proceed? The idea of single-trip sorting: The first lie sorting, for example, do not consider the back of the recursion, first of all, the sequence to be sorted at the left end of the elements set to the first lie sorting we need to find the appropriate location of the root (code in the notes of the number of three places to take the place we can not care, first grasp the idea, will speak later).

int keyi=left。

We know that the left pointer left is at the leftmost point, and the right pointer right is at the rightmost point, so we make the right go first.(the right side must go first to ensure that the point where left and right meet is smaller than the point of the root keyi, this will also be discussed later, we first run backward ideas)When the right pointer right points to a point smaller than the root, stop, and similarly, when the left pointer left points to a point larger than the root, stop, and then exchange the elements they point to, at this time is not the element pointed to by the left is also smaller than the root, right the same way.

while (left < right && a[right] >= a[keyi]) { right–; } while (left < right && a[left] <= a[keyi]) { left++; } swap(&a[left], &a[right]);

That is to say, we can use this operation to realize that the value of the left is less than the root, the value of the right is greater than the root, when the left meets the right, because the meeting point must be less than the root, so we exchange the elements of the root pointing to the elements pointed to by the meeting point, at this point a trip to the completion of the sorting, and also successfully achieved the function we need to complete the above. The idea of recursion: We can put an element in the right place for each sorting trip, and all the values on the left side of the element are less than it, and all the values on the right side are greater than it, then we can use that element as a split point, and the sequence on his left side performs the algorithm for a single sort, and the sequence on the right side has to perform the same algorithm for a single sort.

But in fact, recursion to the back there is a large degree of waste, for example, the last layer of the binary tree occupies 50% of the number of nodes in the entire binary tree, the penultimate layer of 25% ……, we find that in the later sort, in fact, there is a large degree of waste of recursion, so we can be in the end of the last few layers of the recursion is not used directly to use insertion sorting We can use insertion sort instead of recursion in the last few levels.

if ((end - begin + 1) > 10)
{
    ……;
}
else
{
    InsertSort(a + begin, end - begin + 1);
}

Actually, the impact is not that big under the Release version because the compiler has optimized the cost of recursion to be very small.

But why wouldn’t this be an optimization tool that might be useful in an interview?

Did you notice that this is one of the binary treespreorder traversalThe idea is to take care of the root first, then the left subtree, then the right subtree, the difference being that we only need to control the subscript range of the left subtree and the subscript range of the right subtree.

Image taken fromwikipedia-Quicksort 

---

So why does going right first guarantee that the meeting point must be less than the keyi point?

• Meet before the last move of the pointer, if the right pointer, on behalf of the left pointer has just encountered a value greater than the keyi point, and completed the exchange, and then a new round of the cycle of the right pointer first, then the right pointer right to stop the position must be the time just after the exchange of the value of the location of the left pointer, and we know that the left pointer at this time pointing to the value of the value must be less than the keyi point.
• Meet before the last move of the pointer, if the left pointer, on behalf of the right pointer has just encountered the value of less than keyi point, the left pointer at this time to the right to meet with the right pointer, so the value of the meeting point at this time must be less than keyi point.

Code Implementation:

// Quick sort hoare version
int PartSort1(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);//Three numbers to take the middle, will talk about later
	swap(&a[midi], &a[left]);

	int keyi = left;
	while (left < right)
	{
        //right goes first, making sure that left meets right at a point less than key
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		swap(&a[left], &a[right]);//at this point the content of left is greater than the content of right, swap the two
	}
	swap(&a[left], &a[keyi]);//put the contents of keyi where left meets right
	return left;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	// Interval optimization, intervals are no longer recursively partitioned to reduce the number of recursions
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort3(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

---

2.2 Pit occupancy version

The core idea remains the same, with a tweak to the idea of single-trip sorting. Thoughts: The first data is first stored in the key to form the first pit bit.

int key = a[left]; int hole = left;

Because the first value of your key is taken on the leftmost side, i.e., the pit is on the leftmost side, the search for the next pit should start from the right, when the element pointed to by the right pointer is less than keyFormation of new pits, start looking from the left again, and when the element pointed to by the left pointer is larger than key, a new pit is formed, and the process is repeated;

while(left<right) { while (left<right && a[right] >= key) { right–; } a[hole]=a[right]; hole = right; while (left<right && a[left] <= key) { left++; } a[hole] = a[left]; hole = left; }

Until the left and right pointers meet, when they do we put the key value we saved at the very beginning into the pit position and return the pit position.

a[hole] = key; return hole;

TIP: The recursion idea is the same as the Hoare version. Code Implementation:

// Rapid Sorting Trenching
int PartSort2(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	swap(&a[midi], &a[left]);

	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left<right && a[right] >= key)
		{
			right--;
		}
		a[hole]=a[right];
		hole = right;
		while (left<right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	// Interval optimization, intervals are no longer recursively partitioned to reduce the number of recursions
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort3(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

---

2.3 Front and rear pointer version

Before and after the pointer version of the idea is even simpler, he defined two pointers, a pointer in the front to point to left, a pointer in the back of a position left +1, and save left at this time the position (because left will be moved away later);

int prev = left; int cur = left+1; int keyi = left;

When the content pointed to by cur is smaller than the content pointed to by keyi, exchange the element pointed to by prev+1 with the element pointed to by cur(You can’t exchange the prev position because prev is first in the left position, and the element in the left position, which is the position of keyi, is an important reference condition to be exchanged at the end)The process is repeated until cur exceeds right, regardless of whether the element pointed to by cur is less than or greater than or equal to the element pointed to by keyi, and the process is repeated until cur exceeds right;

while (cur <= right) { //when the content pointed to by the cur pointer is less than the key, exchange the content pointed to by the prev pointer and the cur pointer. // Because the next one to be exchanged is prev, add this judgment, if the position of prev+1 is equal to the position of cur, don’t exchange it if (a[cur] < a[keyi] && ++prev!=cur) { swap(&a[prev], &a[cur]); } cur++; //cur advances one square regardless of whether it is greater than or less than cur }

Finally, the reference value is exchanged with prev, returning the position.

swap(&a[prev], &a[keyi]); return prev;

Essentially it can be understood as taking an interval greater than the key, thePush the box to the right., and dumped the smaller one to the left. Code Implementation:

// Quick Sort Before and After Pointer Method
int PartSort3(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	swap(&a[midi], &a[left]);

	int prev = left;
	int cur = left+1;
	int keyi = left;
	while (cur<=right)
	{
		if(a[cur] < a[keyi])
		{
			swap(&a[++prev],&a[cur]);//Here is equivalent to the position of prev+1 is equal to the position of cur also swap, waste of resources
		}
		cur++;
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}

// Quick Sort Before and After Pointer Method(优化版)
int PartSort3_1(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	swap(&a[midi], &a[left]);

	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		//when the content pointed to by the cur pointer is less than the key, exchange the content pointed to by the prev pointer and the cur pointer.
		// Because the next one to be exchanged is prev, add this judgment, if the position of prev+1 is equal to the position of cur, don't exchange it
		if (a[cur] < a[keyi] && ++prev!=cur)
		{
			swap(&a[prev], &a[cur]);
		}
		cur++; //cur advances one square regardless of whether it is greater than or less than cur
	}
	swap(&a[prev], &a[keyi]);
	return prev;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	// Interval optimization, intervals are no longer recursively partitioned to reduce the number of recursions
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort3(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

---

2.4 Optimization of fast sorting by triple number picking

This is a pre-sort operation that is used in all of the above fast-sort methods, so why add this section of the operation? We until the fast sort is an extremely efficient sorting method, but when he encounters a more ordered sequence to sort, or to the extreme, when he sorts an already ordered section of the sequence, his time complexity is O(N^2), each sort time complexity order of magnitude of N, it takes N trips. Because of the ordering, the root of each of his selections is on one side, not in the optimal middle position, which means that this recursive binary tree is seriously off.

Figure Ideal vs. Worst Case Scenario

---

So what to do? We just need to utilize the middle of the triple to avoid taking the smallest value or the largest value as the pit position (reference value) every time; Compare the values on both sides of the sequence with the middle value, and just take the middle-sized one and swap it with the content pointed to by left. Code Implementation:

//Three numbers in the middle
//Three numbers in the middle对于已经有序的序列使用快速排序有很好的优化作用
int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if(a[left]>a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else//a[mid]<a[left]
	{
		if (a[right] > a[left])
		{
			return left;
		}
		else if(a[right]<a[left] && a[right]<a[mid])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
}

---

2.5 Non-recursive version

The non-recursive way to implement the fast-execute can be done using the data structure of the stack can also use the data structure of the queue to assist in the completion of the queue. For example, implement it with a stack data structure. Code Implementation:

// Rapid sort non-recursive implementation
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right); // From right to left
	STPush(&st, left);//Into left to take right
                      //First in, first out
	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort3_1(a, begin, end);

		if (keyi+1<end)//stack the right half of the sequence
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (begin<keyi-1)//stack the left half of the sequence
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}
	STDestroy(&st);
}

---

A summary of the properties of quick sort:

• The overall overall performance and usage scenarios of quick sort are better
• Time Complexity: O(N^logN) //after optimization using ternary neutrality
• Space complexity: O(logN)
• Stability: Unstable

---

3. Summation Sort

mergedCore ideas：

• The already ordered subsequences are merged to obtain a fully ordered sequence;
• That is, each subsequence is first ordered, and then the subsequence segments are ordered among themselves.

normalized sorttheSummary of featuresI’ll put it at the end of the list in the subsumption and sorting section.

3.1 Recursive version

In the recursive version, according to the core idea of the subsumption sort, we need to first order the subsequence, and then finally merge the subsequence, then it is easy to associate the binary tree part of thebackward traversal idea, i.e., solve the left and right subtrees first and the root last.

Returning to sorting, it is sufficient to first split the entire sequence to be sorted into N or more subsequences (left and right subtrees) and then perform the sorting operation on the subsequences (roots).

Now all we need to solve is the problem of how to sort the subsequence. Subsequence ordering:

1. We can create a temporary array, the sub-sequence will be split again to imagine two segments, in these two segments on the definition of the left and right pointers, the right pointer is used to mark the end of the position, the left pointer in turn with the other end of the left pointer to compare the size;
2. Assuming ascending order, then we will put the small section of the first temporary array, and so on, if there is a section of the first end of the (left pointer over the right pointer), then prove that another section of the sequence of the rest of the data are greater than the section of the sequence of the value of the left pointer at this point in time, so directly append to the temporary data can be;
3. Finally, you can copy the sorted temporary array back to the original array.

Code Implementation:

//Subfunctions of the merge sort
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (end <= begin)
	{
		return;
	}
	int mid = (begin + end) / 2;
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid + 1, end);
    //Post-sequential ideas
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int inrex = begin;
	while (begin1<=end1 && begin2 <= end2)
	{
		if(a[begin1] <= a[begin2])// here if it is < then the sort method is unstable
			tmp[inrex++] = a[begin1++];
		else
			tmp[inrex++] = a[begin2++];
	}
    
    //If any segment of the two-segment comparison sequence is left over
    //States that the rest of the data in the sequence is either greater or less than a value in the other sequence.
    // then just append the segment to the tmp array.
	while (begin1 <= end1)
	{
		tmp[inrex++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[inrex++] = a[begin2++];
	}
    //finally copy the sorted tmp array into the a array
	memcpy(a+begin, tmp+begin, (end - begin + 1)*sizeof(int));
}

// Recursive implementation of the merge sort
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(n*sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	_MergeSort(a, tmp, 0, n - 1);
	return;
}

---

3.2 Non-recursive version

The idea of the non-recursive version is to first divide the entire sequence into more than N sub-sequences, and then put these sub-sequences into a temporary array after comparing and sorting them two by two, and after executing it once, reduce the sub-sequences by half (the code is using gap to implement this idea), and then repeat the process. But there is a very easy problem with non-recursion:Array out-of-bounds access。 We are using gap*=2 to halve the subsequence after each execution, but each time the gap is doubled, since the values of begin and end are defined based on the gap.

For example: end2=i+2*gap-1;

Think about how easy it is to cross the line. So how do we solve this problem?

Figure Situation analysis of transboundary

---

if (begin2 >= n)//includes the first three cases mentioned in the above figure, direct break { break; } if (end2 >= n)//go to this to show that begin2 is not out of bounds, end2 is out of bounds, re-correct end2 { end2 = n – 1; } Code Implementation:

// Non-recursive implementation of the merge sort
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(n * sizeof(int));
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2*gap)
		{
			int begin1 = i;
			int end1 = i + gap-1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			int inrex = i;
			// If begin2 has already crossed the border, skip this subsumption.
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)//go to this to show that begin2 is not out of bounds, end2 is out of bounds, re-correct end2
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])// here if it is < then the sort method is unstable
					tmp[inrex++] = a[begin1++];
				else
					tmp[inrex++] = a[begin2++];
			}

			while (begin1 <= end1)
			{
				tmp[inrex++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[inrex++] = a[begin2++];
			}
			//copy the result of this merge back to the a-array.
			memcpy(a + i, tmp + i, (end2-i+1)* sizeof(int));
            //The third parameter here is also important to avoid overstepping boundaries
		}
		gap *= 2;
	}
	free(tmp);
	return;
}

---

A summary of the properties of subsumption sorting:

• The disadvantage of subsumption is that it requires O(N) space complexity, and subsumption is thought of more as a solution to the problem of out-sorting in disk.
• Time complexity: O(N*logN)
• Space complexity: O(N)
• Stability: Stable

---

3.3 Out-of-order problems

All of the sorting methods described earlier are internal sorts, which are methods that sort in memory.

So can they sort the data on disk? The answer is no, note that subscripted random access is not supported on disk, where it is generally sequential write sequential read.

• You may have had the idea of using fseek to adjust the file pointer, but thatVery poor efficiency。

Instead, the idea of subsumption sorting helps us to implement outer sorting, i.e., sorting in the disk. For example, you now have a data file of 4G size and you are asked to perform a sort operation on the file.

1. Based on the idea of subsumption sorting, we can first cut him into several (4) new files (size 1G), each new file can be read into memory using the internal sorting method for sorting;
2. These ordered new files are then opened with the file pointer, compared using the idea of subsumption and then overwritten by writing a new file that can put down the two sequences;
3. Repeat this process until the overwrite is written to the original 4G sized file.

---

4. Counting Sort

The idea of counting sort is to count the number of times the same data appears and then recycle the sequence back to the original sequence based on the number of times they appear. Keep it simple:

1. First find the maximum and minimum values of the sequence to be sorted, so as to get the range of values of the sequence to be sorted, and then create a counting array with such a large range;
2. After that, the original array is traversed again, and whoever appears, +1 is added to the position of the counting array, which gives you the number of times each element appears;
3. Finally, they are put back in order, depending on how many times they appear.

Although it looks like a very foolproof method, you may want to observe the code implementation part, in fact, the design logicvery cleverI’ve commented it out in the source code, so you can learn from it.

I believe that once you have clarified the idea of counting sort, you will realize that heSuitable for sorting data that is very compactand, in many cases, hisVery low time complexity。

Fig. Comparison of the speed of each sort with data volume 1e6 (unit: ms)

---

Code Implementation:

// Counting order
void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	//Calculation range
	int range = max - min + 1;
	// Create a counting array
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memset(count, 0, sizeof(int) * range);

	Counting the number of occurrences of data (general idea)
	//for (int i = 0; i < range; i++)
	//{
	//	for (int j = 0; j < range; j++)
	//	{
	//		if (count[i] == a[j])
	//			count[i]++;
	//	}
	//}
	//Counting occurrences of data (very clever)
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

---

A summary of the properties of counting sorts:

• Counting sort is efficient when the data range is centralized, but has limited applicability and scenarios.
• Time complexity: O(MAX(N,range))
• Space complexity: O(range)
• Stability: Stable