Follow the bubble sorting of animation go data structure ＃ practical operation sharing of private items ＃

Bubble sort

Bubble sort is the simplest exchange sort algorithm .

What exchange is ？ Exchange is to compare two by two , If the order is not satisfied, you can exchange positions . such as , We want to sort from small to large , Compare the values in two positions , If it's in reverse order, it's swapped , Make records with large keywords pop up like bubbles and put them at the end .

Repeat bubble sort several times , Finally, we get an ordered sequence .

The name of bubble sort comes from ： Elements with smaller values are like ” Bubble “ Gradually float to the top of the sequence .

thought

1. Given a N Array of elements , Bubble sort will ：

If the element size relationship is incorrect , Exchange these two numbers （ In this case a> b）,

2. Compare a pair of adjacent elements （a,b）,
3. Repeat step 1 and 2, Until we reach the end of the array （ The last pair is the （N-2） and （N-1） term , Because our array starts from zero ）
4. up to now , The largest element will be in the last position . Then we will N Reduce 1, And repeat the steps 1, until N = 1.

The demo

Given an array ​​29, 10, 14, 37, 14, 48, 17​​ , The bubble sorted animation is shown below ：

Code implementation

package
main




import
"fmt"




func
main() {




// index starts from 0


var
nums
= []
int{
29,
10,
14,
37,
14,
48,
17}


var
length
=
len(
nums)




fmt
.
Println(
" Original array ：",
nums)




bubbleSort(
nums,
length)


fmt
.
Print(
" After array sorting :")




for
i :
=
0;
i
<
length;
i
++ {


fmt
.
Printf(
"%d\t",
nums[
i])

 }

}




func
bubbleSort(
nums []
int,
length
int) {


for
i :
=
0;
i
<
length
-
1;
i
++ {


for
j :
=
0;
j
<
length
-
i
-
1;
j
++ {


if
nums[
j]
>
nums[
j
+
1] {
// If big , In exchange for 


var
temp
=
nums[
j]
// Temporary variables save the previous value 


nums[
j]
=
nums[
j
+
1]


nums[
j
+
1]
=
temp

 }

 }

 }

}




1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.

Run the above code , You can see the result of sorting ：

[
Running]
go
run
"e:\Coding Workspaces\LearningGoTheEasiestWay\Go data structure \ Bubble sort \main.go"


 Original array ： [
29
10
14
37
14
48
17]


 After array sorting :
10
14
14
17
29
37
48


1.
2.
3.

Optimization of bubble sort

A flag can be attached to improve the algorithm , During sorting , If there is no swap operation, it means that the sorting is completed . If the sequence is already ordered , You can end the algorithm by judging the flag .

func
bubbleSortImproved(
nums []
int,
length
int) {


swapped :
=
true


for
i :
=
0;
i
<
length
-
1
&&
swapped;
i
++ {


swapped
=
false


for
j :
=
0;
j
<
length
-
i
-
1;
j
++ {


if
nums[
j]
>
nums[
j
+
1] {
// If big , In exchange for 


var
temp
=
nums[
j]
// Temporary variables save the previous value 


nums[
j]
=
nums[
j
+
1]


nums[
j
+
1]
=
temp


swapped
=
true

 }

 }

 }

}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

In the best case , The time complexity of the improved bubbling algorithm is .

summary

The advantage of comparing other sorting algorithms is , It can detect whether the input sequence is already sorted .

The time complexity of bubble sort is （ Even in the best of circumstances ）, The space complexity is  .

Bubble sorting is also a stable algorithm .