bubbleSort

Algorithm idea:
Starting from the first element, compare the values of two adjacent elements in pairs, and put the larger one behind (from small to large)
Average time complexity: O(n2)
Worst time complexity: O(n2)
Optimal time complexity: O(n)
Space complexity: 1
Stability: unstable
Suitable for scene: few elements

Code implementation:
Mode 1: double layer loop traversal
i: left boundary of Index currently being sorted
j: Used to traverse the array and bubble

```package main

import "fmt"

func main() {
arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
bubbleSort(arr)
for _, v := range arr {
fmt.Println(v)
}
}

func bubbleSort(arr []int) {
for i := 0; i < len(arr)-1; i++ {
for j := 0; j < len(arr)-1; j++ {
if arr[j] > arr[j+1] {
swap(arr, j, j+1)
}
}
}
}

func swap(arr []int, i, j int) {
tem := arr[i]
arr[i] = arr[j]
arr[j] = tem
}

```

Time complexity: O(n2)
Data exchange times: (n - 1) * (n - 1) =(n - 1)2
Total complexity: (n - 1)2

Method 2: reduce the number of comparisons
Code 1:
i: number of ordered sequences
j: Used to traverse the array and bubble

```package main

import "fmt"

func main() {
arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
bubbleSort(arr)
for _, v := range arr {
fmt.Println(v)
}
}

func bubbleSort(arr []int) {
for i := 0; i < len(arr)-1; i++ {
for j := 0; j < len(arr)-1-i; j++ {
if arr[j] > arr[j+1] {
swap(arr, j, j+1)
}
}
}
}

func swap(arr []int, i, j int) {
tem := arr[i]
arr[i] = arr[j]
arr[j] = tem
}

```

Code 2:
i: left bound index of ordered sequence
j: Used to traverse the array and bubble

```package main

import "fmt"

func main() {
arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
bubbleSort(arr)
for _, v := range arr {
fmt.Println(v)
}
}

func bubbleSort(arr []int) {
for i := len(arr) - 1; i > 0; i-- {
for j := 0; j < i; j++ {
if arr[j] > arr[j+1] {
swap(arr, j, j+1)
}
}
}
}

func swap(arr []int, i, j int) {
tem := arr[i]
arr[i] = arr[j]
arr[j] = tem
}
```

Time complexity: O(n2)
Data exchange times: (n - 1) + (n - 2) + (n - 3) +... + 1 = 1/2n2 - 1/2n
Total complexity: 1/2n2 - 1/2n

Mode 3: external circulation optimization
If it is found that no elements move during a comparison, the next comparison will not be carried out to prove that the order has been arranged.
i: left bound index of ordered sequence
j: Used to traverse the array and bubble
flag: judge whether the array has been ordered

```package main

import "fmt"

func main() {
arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
bubbleSort(arr)
for _, v := range arr {
fmt.Println(v)
}
}

func bubbleSort(arr []int) {
for i := len(arr) - 1; i > 0; i-- {
flag := false
for j := 0; j < i; j++ {
if arr[j] > arr[j+1] {
swap(arr, j, j+1)
flag = true
}
}
if flag == false {
break
}
}
}

func swap(arr []int, i, j int) {
tem := arr[i]
arr[i] = arr[j]
arr[j] = tem
}

```

Worst time complexity: O(n2)
Optimal time complexity: O(n)

Mode 4: internal circulation optimization
Record the position of the last exchange. If there is no exchange value behind, the array must be orderly, and then the next sorting ends from the first comparison to the position of the last record
i: left bound index of ordered sequence
j: Used to traverse the array and bubble
flag: judge whether the array has been ordered
pos: records the element position of the last exchange element
newPos: temporary variable

```package main

import "fmt"

func main() {
arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
bubbleSort(arr)
for _, v := range arr {
fmt.Println(v)
}
}

func bubbleSort(arr []int) {
for i := len(arr) - 1; i > 0; i-- {
flag := false
pos, newPos := i, 0
for j := 0; j < pos; j++ {
if arr[j] > arr[j+1] {
swap(arr, j, j+1)
flag = true
newPos = j
}
}
if flag == false {
break
}
pos = newPos
}
}

func swap(arr []int, i, j int) {
tem := arr[i]
arr[i] = arr[j]
arr[j] = tem
}

```

Worst time complexity: O(n2)
Optimal time complexity: O(n)

Mode 5: bidirectional traversal optimization (cocktail sorting)
Record the position of the last exchange. If there is no exchange value behind, the array must be orderly, and then the next sorting ends from the first comparison to the position of the last record
Left: the right boundary index of the ordered sequence on the left
Right: the left bound index of the ordered sequence on the right

```package main

import "fmt"

func main() {
arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
bubbleSort(arr)
for _, v := range arr {
fmt.Println(v)
}
}

func bubbleSort(arr []int) {
left, right := 0, len(arr)-1
for left < right {
preBubbleSort(arr, left)
left++
if left >= right {
break
}
backBubbleSort(arr, right)
right--
}

}

func preBubbleSort(arr []int, left int) {
for i := left + 1; i < len(arr); i++ {
if arr[i] < arr[left] {
swap(arr, i, left)
}
}
}

func backBubbleSort(arr []int, right int) {
for i := right - 1; i >= 0; i-- {
if arr[i] > arr[right] {
swap(arr, i, right)
}
}
}

func swap(arr []int, i, j int) {
tem := arr[i]
arr[i] = arr[j]
arr[j] = tem
}
```

Worst time complexity: O(n2)
Optimal time complexity: O(n)

Keywords: Algorithm data structure Permutation

Added by blacksnday on Sat, 05 Mar 2022 10:59:02 +0200