1. Introduction
Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly swapping adjacent elements if they are in the wrong order until the entire array is sorted. Its name comes from the way smaller elements "bubble" to the top of the list.
2. Implementation Steps
1. Traverse through the array.
2. Compare adjacent elements.
3. Swap if they are in the wrong order.
4. Repeat the process for every pair of adjacent elements, from the first pair to the last.
5. Reduce the length of the array for each outer loop iteration, as the highest value in the unsorted part will always move to its correct position.
3. Implementation in Golang
package main
import (
"fmt"
)
func BubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
swapped := false
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
// swap arr[j] and arr[j+1]
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true
}
}
// If no two elements were swapped by the inner loop, then the array is sorted
if !swapped {
break
}
}
}
func main() {
data := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("Original array:", data)
BubbleSort(data)
fmt.Println("Sorted array: ", data)
}
Output:
Original array: [64 34 25 12 22 11 90] Sorted array: [11 12 22 25 34 64 90]
Explanation:
1. BubbleSort function sorts an array using the bubble sort algorithm.
2. The outer loop runs for each element in the array.
3. The inner loop traverses the array and compares adjacent elements.
4. If two adjacent elements are in the wrong order, they are swapped.
5. The variable swapped is used to check if any swapping took place in the inner loop. If no swapping took place, it indicates that the array is already sorted, and the algorithm can break out of the loop early, optimizing the process.
6. The main function initializes an array, displays its original state, sorts it, and then displays the sorted state.
Though Bubble Sort is straightforward and easy to understand, it's not the most efficient for large datasets due to its average and worst-case time complexity of O(n^2).
Comments
Post a Comment