[Algorithm] Bubble Sort(버블 정렬)

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum

[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의

 

3강 버블 정렬 강의 복습 겸 일지다.

 

버블 정렬의 경우 array가 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 이렇게 있다면

 

1, 10 => 1, 10

 

10, 5 => 5, 10

 

10, 8 => 8, 10

 

이런 식으로 두 수를 비교한 다음 작은 수를 왼쪽으로 보내는 정렬이다.

 

 

 

이것도 마찬가지로 회수는 n (n + 1) / 2 로 시간 복잡도는 O(N*N) 이나

 

같은 시간 복잡도를 가진 선택정렬, 삽입정렬과 비교해봤을 때 가장 비효율적인 정렬 방법이다.

 

 

 

C++ 로 작성한 버블정렬은 다음과 같다.

 

#include <stdio.h>

int main(void) {
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9 - i; j++) {
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
	return 0;
}

 

보면 array[j], array[j+1] 양옆의 값을 비교해보는 것을 알 수 있다.

 

 

javascript 로도 작성을 해보면

 

function bubbleSort() {
    let i, j, temp;
    let array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
    for (i = 0; i < 10; i ++) {
        for (j = 0; j < 9 - i; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    console.log(array.join(", "));
}

bubbleSort();

 

 

이렇게 된다.

 

 

Java로는 

 

public class BubbleSort
{
    public static void main(String[] args) {
        int i, j, temp;
        int[] array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        for (i = 0; i < 10; i++) {
            for (j = 0; j < 9 - i; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        for (i = 0; i < 10; i++) {
            System.out.printf("%d ", array[i]);
        }
    }
}

 

 

이렇게 작성하면 된다.

 

 

좀 더 가독성 있게 정리한다면

 

public class Sort
{
    public static void bubbleSort(int[] arr) {
        int i, j, temp;
        int[] array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        for (i = 0; i < array.length; i++) {
            for (j = 0; j < array.length - i; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < 10; i++) {
            System.out.printf("%d ", array[i]);
        }
    }
}

 

이렇게 된다.