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

A drop in the universe 2022-01-26 15:00:03 阅读数:432

follow bubble sorting animation data

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),

  1. Compare a pair of adjacent elements (a,b),
  2. 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 )
  3. 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 :

 Follow animation Go Bubble sort of data structure # Share the actual operation of private items #_ Array

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  Follow animation Go Bubble sort of data structure # Share the actual operation of private items #_ Bubble sort _02.

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  Follow animation Go Bubble sort of data structure # Share the actual operation of private items #_ Array _03( Even in the best of circumstances ), The space complexity is   Follow animation Go Bubble sort of data structure # Share the actual operation of private items #_ Array _04.

 Follow animation Go Bubble sort of data structure # Share the actual operation of private items #_ Array _05

Bubble sorting is also a stable algorithm .

copyright:author[A drop in the universe],Please bring the original link to reprint, thank you. https://en.javamana.com/2022/01/202201261500001488.html