How to rank golang bubbling

Golang bubble sorting algorithm detailed explanation

Bubble sorting is a common sorting algorithm. Its principle is very simple, it is a kind of exchange sorting. The core idea of ​​this algorithm is to compare the sizes of two adjacent elements, and then exchange their positions according to the size relationship. In each round, the largest or smallest element is arranged at one end of the sequence. There are two specific implementation methods: one is from front to back, and the other is from back to front. This article will introduce the implementation of bubble sorting in golang.

First, we create an integer array and pass in the bubble sort function:

package main

import "fmt"

func main() {
    arr := []int{3, 7, 1, 4, 2, 8, 5, 9, 6}
    fmt.Println("排序前:",arr)
    BubbleSort(arr)
    fmt.Println("排序后:",arr)
}

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

In the BubbleSort function, we first get the length of the array, and then set up two loop nests. The outer loop is a loop over the entire array, and the inner loop is a loop over the elements. In the inner loop, we compare the sizes of adjacent elements and then swap their positions based on the size relationship.

The exchange method is implemented through golang's multiple assignment, that is, "arr[j], arr[j 1] = arr[j 1], arr[j]". This statement assigns the value of arr[j 1] to arr[j], and the value of arr[j] to arr[j 1]. This way the exchange between two elements can be completed.

It should be noted that each round of sorting will move the smallest or largest element to one end of the sequence. In order to ensure efficiency, we need to subtract the number of sorted elements i in the outer loop, that is, "for j := 0; j < n-1-i; j ". In this way, the number of comparisons in each round of sorting will not include elements that have already been sorted.

Finally, we call the BubbleSort function in the main function and print the array results before and after sorting on the console.

Next we test the performance of this algorithm. We can use golang's own testing library for testing. The specific test code is as follows:

package main

import (
    "testing"
)

func TestBubbleSort(t *testing.T) {
    arr := []int{3, 7, 1, 4, 2, 8, 5, 9, 6}
    BubbleSort(arr)
    if !checkSort(arr) {
        t.Error("BubbleSort test failed")
    }
}

func checkSort(arr []int) bool {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        if arr[i] > arr[i+1] {
            return false
        }
    }
    return true
}

In the main function, we define a function called TestBubbleSort, which is used to test the correctness of the BubbleSort function we wrote. In the test function, we call the BubbleSort function and use the checkSort function to determine whether the sorting result is correct. If the sorting result is incorrect, the error message "BubbleSort test failed" will be output.

Next, we use the go test command to run the test. Enter the following command on the command line:

go test -v -run="TestBubbleSort"

This command will run the TestBubbleSort function and output the test results on the console. The results are as follows:

=== RUN   TestBubbleSort
--- PASS: TestBubbleSort (0.00s)
PASS
ok      _/home/go_ws/src/gotest/src/TestBubbleSort   0.097s

As can be seen from the test results, the sorting algorithm passed the unit test, and the test time was only 0.097 seconds. Therefore, the bubble sort algorithm performs well in terms of efficiency.

Summary

This article introduces the implementation of bubble sorting in golang, and verifies the correctness and efficiency of the sorting algorithm through unit testing. In practical applications, we can appropriately optimize this algorithm as needed to achieve better sorting results.

The above is the detailed content of How to rank golang bubbling. For more information, please follow other related articles on the PHP Chinese website!