Bubble Sort / Selection Sort

김석재·2024년 1월 27일

거품정렬(Bubble Sort)

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘

거품 정렬은 선택 정렬과 유사한 알고리즘이다.

정렬 방법

1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를... 이런 식으로 마지막 -1 번째 원소와 마지막 원소를 비교하며 조건에 맞지 않는다면 서로 교환한다.
1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

Java Code

void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length; i++) {       // 1.
		for(int j= 1 ; j < arr.length-i; j++) { // 2.
			if(arr[j-1] > arr[j]) {             // 3.
                // swap(arr[j-1], arr[j])
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

i는 제외될 원소의 갯수를 의미한다. 1회전이 끝난 후 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜준다.
원소를 비교할 index를 뽑는 반복문으로 j는 현재 원소를 가리키고, j-1은 이전 원소를 가리키게 되므로, j는 1부터 시작한다.
현재 가리키고 있는 두 원소의 대소를 비교한다, 해당 코드는 오름차순 정렬이므로 현재 원소보다 이전 원소가 더 크다면 이전 원소가 뒤로 가야하므로 서로 자리를 교환해준다.

시간복잡도

(n-1) + (n-2) + (n-3) + ..... + 2 + 1 => n(n-1) / 2
이므로 O(n^2)이다

Bubble Sort는 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 푀악의 경우 모두 시간 복잡도가 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n)이다.

장점

구현이 간단하고, 소스코드가 직관적
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
안전 정렬(stable Sort)이다.

단점

시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

선택 정렬(Selection Sort)

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

선택 정렬은 거품 정렬과 유사한 알고리즘이다.

정렬방법

주어진 배열 중에 최소값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다.(pass)
맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

Java Code

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
}

위치(index)를 선택해준다.
i + 1 번째 원소부터 선택한 위치(index)의 값과 비교를 시작한다.
오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신해준다.
'2'번 반복문이 끝난 뒤에는 indexMin에 '1'번에서 선택한 위치(index)에 들어가야하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap)해준다.

시간복잡도

데이터의 개수가 n개라고 했을 때,

첫 번째 회전에서의 비교횟수 = 1 ~ (n-1) => n-1
두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
...

(n-1) + (n+2) + .... + 2 + 1 => n(n-1) / 2

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일하다.

공간복잡도

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 이다.

장점

Bubble Sort와 마찬가지로 알고리즘이 단순하다.
정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)