[Golang]bubble sort(버블 정렬)

버블 정렬(bubble sort) 알고리즘 개념 

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
  • 인접한 2개의 레코드 비교, 크기가 순서대로 되어있지 않으면 서로 교환
• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, …
  이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬
• 1회전 수행하면 가장 큰 자료가 맨 뒤로 이동 하므로 2회전에는 맨 끝에 있는 자료는 제외되고, 
  2회전에는 끝에서 두 번째 자료까지는 정렬에서 제외 
  => 정렬을 1회전 수행할때마다 정렬에서 제외되는 데이터가 하나씩 증가 

 

 

알고리즘 특징

• 장점
  • 구현이 매우 간단하다.(옆에 레코드와 비교해서 큰 값을 뒤로 넘겨주면 됨)
• 단점
  • 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
  • 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
  • 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

 

 

시간 복잡도

• 비교 횟수
  최상, 평균, 최악 모두 일정
  n-1, n-2, … , 2, 1 번 = n(n-1)/2
• 교환 횟수
  • 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
  • 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
• T(n) = O(n^2)

 

버블 정렬(bubble sort)의 c언어 코드 

# include <stdio.h>
# define MAX_SIZE 5

// 버블 정렬
void bubble_sort(int list[], int n){
  int i, j, temp;

  for(i=n-1; i>0; i--){
    // 0 ~ (i-1)까지 반복
    for(j=0; j<i; j++){
      // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
      if(list[j]<list[j+1]){
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {7, 4, 5, 1, 3};

  // 버블 정렬 수행
  bubble_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

 

Go언어로 된 버블 정렬 알고리즘은?

//bubble sort func
package bubblesort

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


//main
package main

import (
	"fmt"
	"study01/package1/bubblesort"
)
func main() {
	fmt.Print(bubblesort.Bubble_sort([]int{11, 8, 2, 3, 4, 5}))
}