Bubble Sort - 버블 정렬

 

https://en.wikipedia.org/wiki/Bubble_sort

Bubble sort - Wikipedia

Buble Sort 알고리즘은 가장 간단하지만 성능은 그리 좋지 않은 알고리즘입니다.

각 배열의 앞자리와 바로 뒷자리 값을 비교해 위치를 이동시키며 정렬하게 됩니다.

아래 링크에도 자세히 설명되어 있습니다.

https://www.geeksforgeeks.org/bubble-sort/ 

 

Go로 구현한 코드입니다.

package main

import "fmt"

func main() {
	arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")

	tmp := 0

	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr)-1-i; j++ {
			if arr[j] > arr[j+1] {
				tmp = arr[j]
				arr[j] = arr[j+1]
				arr[j+1] = tmp
			}
		}
	}

	fmt.Println("Sorted array is: ", arr)
}

 

각 코드에 대한 설명을 주석으로 달았습니다.

package main

import "fmt"

func main() {
	// 길이가 10인 int 형식의 배열을 만들고 0부터 9까지의 숫자를 정렬하지 않고 담습니다.
	arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")

	// 임시 저장용 tmp 변수를 선언합니다.
	tmp := 0

	// arr 배열의 길이만큼 for 문을 돌립니다.
	for i := 0; i < len(arr); i++ {

		// i가 증가함에 따라 j는 0부터 8까지, 0부터 7까지 그리고 마지막에 i가 8이 될때 j는 0이 됩니다.
		// j loop가 한번 진행되면 오름차수일 경우 arr 변수의 가장 큰 값 이 가장 뒷자리로 이동됩니다.
		// 그래서 첫 번째 loop에서 j는 0부터 8까지 가지고 가장 큰 수를 마지막 자리로 이동시키게 됩니다.
		// 두 번째 loop에서 j는 0부터 7까지 가지고 그 다음으로 큰 수를 마지막에서 바로 앞 자리로 이동 시킵니다.
		for j := 0; j < len(arr)-1-i; j++ {
			// fmt.Println("i: ", i, ", j:", j)

			// arr 배열의 두 자릿수를 비교합니다.
			// 앞자릿수 < 뒷자릿수 비교일 경우 내림차수로 정렬합니다. [9 8 7 6 5 4 3 2 1 0]
			// 앞자릿수 > 뒷자릿수 비교일 경우 오름차수로 정렬합니다. [0 1 2 3 4 5 6 7 8 9]
			if arr[j] > arr[j+1] {

				// 앞 자릿수가 뒷 자리수보다 크다면 tmp 변수에 값을 임시로 저장합니다.
				tmp = arr[j]

				// 뒷 자릿수의 값을 앞자리로 옮김니다.
				arr[j] = arr[j+1]

				// 임시로 저장했던 값을 뒷자리로 옮김니다.
				arr[j+1] = tmp
			}
		}
	}

	fmt.Println("Sorted array is: ", arr)
}

 

Bubble Sort를 구현한 다른 코드입니다.

아래 코드는 배열의 뒤에서부터 비교하고 있습니다. 그래서 오름차수 정렬일 경우 가장 앞자리에 작을 값을 먼저 넣습니다.

package main

import (
	"fmt"
)

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

func main() {
	unsorted := []int{1, 199, 3, 2, 5, 80, 99, 500}

	fmt.Println("Before : ", unsorted)

	bubbleSort(unsorted)

	fmt.Println("After : ", unsorted)
}

tmp 변수를 사용하지 않고 아래처럼 바로 값을 대입합니다.

tosort[j], tosort[j-1] = tosort[j-1], tosort[j]