Golang Algorithm - bubbleSort2

버블정렬이란?

https://ko.wikipedia.org/wiki/%EB%B2%84%EB%B8%94_%EC%A0%95%EB%A0%AC

버블 정렬 - 위키백과, 우리 모두의 백과사전

 

원소의 이동이 거품처럼 수면위에 올라온다고 해서 붙여진 이름이다. 시간 복잡도는 O(n^2)으로 느린 편이다. 

기초적인 개념은 위와 같다.

 

go로 구현하는 bubbleSort2 

 

지난번 포스팅에서 bubbleSort를 했으나 그 때는 정해진 배열 값을 가지고 했다.

이번에는 난수를 생성해서 배열에 넣고 그 배열에 있는 값을 가지고 버블정렬을 실행한다.

 

함수의 역할

main() : 20개의 난수 배열을 생성하는 함수 generateSlice를 호출한 뒤 bubblesort 함수를 호출하는 메인 함수

generateSlice() : slice를 초기화한뒤 slice 배열에 1부터 999까지의 난수 -  1부터 999까지의 난수를 계산한 원소를 삽인한 배열(slice)을 리턴한다. 

bubblesort() : 버블정렬 앞의 원소가 뒤의 원소보다 크면 위치를 바꾼다. (오름차순 정렬로 코딩함)

 

 

Go 소스코드 

package main

import (
	"fmt"       //프린트 패키지
	"math/rand" //난수 패키지
	"time"      //시간 패키지
)

func main(){
	slice := generateSlice(20)
	fmt.Println("\n--- Unsorted --- \n\n", slice)
	bubblesort(slice)
	fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}

func generateSlice(size int) []int {
	slice := make([]int, size, size)
	rand.Seed(time.Now().UnixNano()) //유닉스시간의 나노초 
	fmt.Println(time.Now().UnixNano())

	// rand.Intn(100) > 1부터 100까지 정수 형태의 난수가 출력됨 
	fmt.Println("rand.Intn(100)",rand.Intn(100))
	for i := 0; i < size; i++{
		//1부터 999까지의 난수 - 1부터 999까지의 난수 
		slice[i] = rand.Intn(999) - rand.Intn(999)
	}

	fmt.Println("slice",slice)
	return slice 
}

func bubblesort(items []int){
	var (
		n = len(items) //배열의 길이 
		sorted = false //sorted에 bool값 선언 
	)
	for !sorted{

		swapped := false 
		for i := 0; i < n - 1; i++ {
			//앞의 원소가 뒤 원소보다 크면 swapped  
			if items[i] > items[i+1]{
				items[i+1], items[i] = items[i], items[i+1]
				swapped = true 
			}
		}
		
		//마지막 출력을 위해 선정한 것으로 보임 
		if !swapped{
			sorted = true 
		}
		//n에는 n - 1 값 대입
		n = n - 1 
		
	}
}

 

코드를 보면서 값이 뭐가 나올지 궁금해서 로그를 찍어봤다. 

fmt.Println() 결과값이다. 

go run bubble_sort2.go 
1676200214637739790
rand.Intn(100) 69
slice [648 912 -157 -575 379 218 -491 185 -870 742 241 -417 -28 216 -152 -880 -70 -578 -103 97]

--- Unsorted --- 

 [648 912 -157 -575 379 218 -491 185 -870 742 241 -417 -28 216 -152 -880 -70 -578 -103 97]

--- Sorted ---

 [-880 -870 -578 -575 -491 -417 -157 -152 -103 -70 -28 97 185 216 218 241 379 648 742 912]