정렬이란 단어는 알고리즘을 몰라도 이미 익숙한 단어이다. 엑셀에도 여러 값이 있는 자료를 '정렬'하면 해당 값들이 오름차순 또는 내림차순으로 정렬된다. 정렬 알고리즘도 이와 같이 '정렬되지 않은 배열을 오름차순으로 정렬'하는 방법들이다. 컴퓨터 과학분야에서 오랜 기간동안 다양한 정렬 알고리즘들이 연구 & 개발되었다.
버블 정렬 (Bubble sort)
그 중 가장 기본적인 (그리고 상대적으로 비효율적인) 정렬 알고리즘인 버블 정렬은 아래 gif와 같이 진행된다.(출처)
버블정렬은 원소를 순서대로 두 개씩 비교하면서, 왼쪽 값이 오른쪽 값보다 큰 경우 두 값을 서로 교환하고(swap), 그렇지 않으면 그대로 둔다. 그 다음 오른쪽으로 한 칸 이동해서 똑같은 작업을 수행한다. 이렇게 가장 오른쪽 원소까지 이동하면 첫 번째 패스스루(pass-through), 즉 처음부터 끝까지 모든 원소를 관통하며(through) 지나간(pass) 것이다. 이렇게 첫 패스스루가 완료되면, 전체 원소 중 가장 큰 값이 맨 오른쪽으로 가게 된다.
이제 가장 오른쪽 원소는 완전히 정렬된 값이다. 따라서 가장 오른쪽 원소는 제외하고 두번째 패스스루를 시작한다. 처음부터 끝에서 두번째 원소까지 두번째 패스스루를 마치고 나면, 그 중 가장 큰 값이 맨 오른쪽으로 가게 된다. 패스스루에서 한 번이라도 교환(swap)이 일어나게 되면 다시 새로운 패스스루를 진행한다. 한 번이라도 교환이 일어나지 않는 패스스루가 생기면 더 이상 새로운 패스스루를 진행하지 않는다. 이를 통해 전체 배열이 오름차순으로 정렬된다.
버블 정렬은 왜 '버블' 정렬인가?
버블 정렬의 특징 중 하나는, 한 번의 패스스루가 끝나면, 패스스루가 확인한 값들 중 가장 큰 값이 가장 오른쪽으로 이동한다는 것이다.
bubble은 동사로 '거품이 뽀글뽀글 표면으로 올라간다'는 의미가 있다. 거품이 표면으로 떠올라가듯, 버블 정렬에서도 가장 큰 값이 가장 오른쪽으로 이동하게 되기 때문에 bubble sort 라는 이름이 붙었다.
버블정렬의 이름은 '(내림차순일 경우)작거나 (오름차순일 경우)큰 원소가 데이터셋의 가장 큰 위치(top)로 떠오른다(bubble)는 사실에서 생겨났다. [3,1,4,2] 의 배열 예시에서 3과 4는 자신이 위치해야 하는 적절한 위치로 떠오르게 (bubble up) 된다.
The name bubble sort comes from the fact that smaller or larger elements "bubble" to the top of a dataset. In the previous example of [3, 1, 4, 2], the 3 and 4 are bubbling up the dataset to find their proper positions.
참고: https://airfocus.com/glossary/what-is-bubble-sort/
버블 정렬 구현하기 (javascript)
function bubbleSort(array) {
let swap = 1 ;
let passthrough = 0 ;
while (swap >0) {
swap = 0 ;
passthrough += 1;
let i = 0 ;
while(i <= array.length - passthrough - 1) {
if (array[i] > array[i+1]) {
let temp_value = array[i+1];
array[i+1] = array[i] ;
array[i] = temp_value ;
swap += 1 ;
}
i++
}
}
return array;
};
버블 정렬의 효율성
버블 정렬에서는 두 값을 비교하고, 교환한다. 그렇다면 배열 원소의 갯수가 N개일 때, 몇 번의 비교와 몇 번의 교환이 이루어질까?
비교
첫 번째 패스쓰루에서 1번째 원소와 2번째 원소, 2번째 원소와 3번째 원소, 이렇게 N-1번째 원소와 N번째 원소와의 비교까지 진행한다. (총 N-1번 비교)
두 번째 패스쓰루에서는 맨 오른쪽 값은 이미 정렬이 완료된 값이므로 1번째 원소와 2번째 원소, 2번째 원소와 3번째 원소, 이렇게 N-2번째 원소와 N-1번째 원소와의 비교까지 진행한다. (총 N-2번 비교)
세 번째 패스쓰루에서는 맨 오른쪽 두 값은 이미 정렬이 완료된 값이므로 1번째 원소와 2번째 원소, 2번째 원소와 3번째 원소, 이렇게 N-3번째 원소와 N-2번째 원소와의 비교까지 진행한다. (총 N-3번 비교)
...
최악의 시나리오의 경우, 비교해야 하는 원소가 하나만 남을 때까지 패스쓰루를 진행해야 한다. 이 마지막 패스쓰루에서는 맨 왼쪽 원소 두 개를 제외한 모든 값이 이미 정렬이 완료된 값이므로 1번째 원소와 2번째 원소만 비교한다. (총 1번 비교)
즉, 모든 패스쓰루에서 일어나는 비교의 단계를 모두 더하면 (N-1) + (N-2) + (N-3) + ... + (1) 이다.
교환
알고리즘의 효율성은 항상 최악의 시나리오를 상정하므로, 최악의 시나리오를 떠올리면 이는 비교를 할 때마다 교환을 하는 경우일 것이다.
즉, 최악의 시나리오에서 일어날 수 있는 교환의 수는, 비교의 수와 동일한, (N-1) + (N-2) + (N-3) + ... + (1) 이다
이렇게 구한 비교의 수와 교환의 수를 더하면 N^2 - N 이 된다.
즉, 버블 정렬의 효율성은 N^2 - N 으로 나타낼 수 있다. 아래 y=x^2 - x 그래프의 모양을 참고해보자. N이 늘어날 때마다 알고리즘에 필요한 단계는 2차 함수의 모양처럼 기하급수적으로 증가한다. 이에 버블 정렬은 빅오 카테고리 O(N^2)에 속한다.
O(N)과 O(N^2)의 비교
O(N)과 O(N^2)을 비교해보자. 아래 파란 그래프가 O(N)을 나타내고, 빨간 그래프가 O(N^2)를 나타낸다.
O(N^2)가 O(N) 조금 비효율적인 것같아 보인다. 그렇다면, N값이 더 커지면 어떨까?
O(N^2)가 O(N)보다 말도 안되게 비효율적이다.
버블 정렬의 효율성 높이기 - 선형 해결법
이렇게 느린 O(N^2)알고리즘은 '선형해결법' 이라는 방법을 사용해서 O(N)알고리즘으로 대체할 수 있다.
댓글