preface

This is the fifth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

The top ten sorts are: bubble sort, selection sort, insertion sort, Hill sort, merge sort, quicksort (quicksort), bucket sort, count sort, radix sort, and heap sort.

This article mainly describes the principles and implementation of bubble sort and selection sort, and a simple comparison between the two.

If you want to understand each sort of time complexity comparison, as well as some sort of basic knowledge, such as stable sort and non-stable sort, in situ sort and non situ sort, you can see the hand tore sorting algorithm ten (preface), I believe can help you!

Note: This code is implemented by Golang.

Bubble sort

Bubble sort is summed up in one sentence: from left to right, two adjacent elements in an array are compared, and the larger one is put behind. The detailed process is shown in the figure below.

As above, if you have an array: [5, 3, 2, 4, 1], you can start by swapping them, and you can see that the largest number is shifted to the right (so you don’t have to compare it in the next round), while the smaller number slowly moves to the left, and so on.

There are two ways to implement bubble sort, both of which have different optimal and worst time complexity.

Bubble to achieve one

// Implement bubble sort
// From small to large: move the maximum value all the way to the right
func bubbleSort1(arr []int) []int {
	n := len(arr)
	for i := 0; i < n- 1; i++ {
		// k < n-1- I: the following numbers do not need to compare
		for k := 0; k < n- 1-i; k++ {
			if arr[k] > arr[k+1] {
				arr[k], arr[k+1] = arr[k+1], arr[k]
			}
		}
	}
	return arr
}
Copy the code

Summary: This is a common bubble sort, which consists of two for loops, so the average, best and worst time complexity are all O (n2n^2n2), and the space complexity is O (1) because the above solution does not use other data structures for storage.

Bubble implementation two

func bubbleSort2(arr []int) []int {
	n := len(arr)
	for i := 0; i < n- 1; i++ {
		flag := 0 // Can be replaced with a Boolean value
		for k := 0; k < n- 1-i; k++ {
			if arr[k] > arr[k+1] {
				arr[k], arr[k+1] = arr[k+1], arr[k]
				flag += 1}}// When the array is in order, flag is still 0, indicating that the array itself is ordered, so the complexity is O(n).
		if flag == 0 {
			break}}return arr
}
Copy the code

Summary: This is a modified bubble sort, the worst time complexity is O (n2n^2n2), when the array itself is ordered, the optimal time complexity is O (n).

Selection sort

Selection sorting is summed up in one sentence: start at the first position, compare with the following numbers, find the smallest, and swap with the first position (so that the smallest number is always on the left).

As above, suppose you have an array: [5, 3, 2, 4, 1]. Start by comparing the first number to the rest, move the smallest number to the far left, then move the second smallest number to the left, and so on.

Code implementation is as follows:

func selectSort(arr []int) []int {
	n := len(arr)
	for i := 0; i < n; i++ {
		// k= I +1, indicating the next number
		for k := i + 1; k < n; k++ {
			if arr[i] > arr[k] {
				arr[i], arr[k] = arr[k], arr[i]
			}
		}
	}
	return arr
}
Copy the code

Conclusion: The average, worst, and best complexity of sorting are all O (n2n^2n2), because the traversal can only know which number is the smallest, so the worst and best complexity are all O (n2n^2n2), and the space complexity is O (1) because no other data structure is utilized.

Bubble sort vs. selection sort

Before, I was a bit silly to distinguish bubble sort and selection sort, after recent sorting, summed up the differences between them:

1. Different comparison methods: Bubble sort is adjacent comparison, and selection sort is the first number compared with other numbers, as follows:

If you are still not clear, you can compare Figure 1 with Figure 2 to make it easier to understand.

2. Different time complexity: in special cases, bubble sort can reach the complexity of O(n); And selection sort is always O(n2).

3. Bubble sort is stable, and selection sort is unstable. Take an array [4, 6, 4, 3, 3] for example. In the first round of comparison, we know that the first 4 will switch positions with the first 3, and the order of the original 4 will be broken, so select sort is not a stable sort algorithm.

Write in the last

If there are any mistakes in this article, please point them out in the comment section, and thank you very much. In addition, if this article is useful to you, please also ask guests to point a little love 💖!