[알고리즘] - 버블정렬(Bubble Sort)

해당 포스팅에서는 정렬 기법 중 하나인 버블정렬에 대해 설명한 후 버블정렬을 자바스크립트로 구현해보고자 합니다.

---

버블정렬 정의

버블정렬은 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복하는 정렬기법이다.

(오름차순 정렬 시) 작은 수가 올라오는 과정이 거품같다고 해서 Bubble sort라고 불린다.

---

버블정렬 로직

input: 크기가 n인 array nums
output: 정렬된 array nums

1번째 pass

첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를 ... n-1번째 원소와 n번째 원소를 비교하고 교환하면서 배열을 정렬한다.
그러면 가장 큰 수가 배열의 맨 뒤에 배치된다.

2번째 pass

1번째 pass를 수행하고 나면 가장 큰 수가 맨 뒤에 배치되므로, 2번째 pass때는 맨 마지막 원소는 제외하고 정렬을 한다. 2번째 pass를 수행하면 두 번째로 큰 수가 뒤에서 두 번째 위치에 배치된다.

3번째 pass

2번째 pass를 수행하고 나면 가장 큰 수와 두 번째로 큰 수가 이미 맨 뒤에 정렬되어 있다. 따라서 그 둘을 제외하고 정렬을 한다. 3번째 pass를 수행하면 3번째로 큰 수가 뒤에서 세 번째 위치에 배치된다.

이렇게 정렬을 수행할때마다 정렬에서 제외되는 원소들이 늘어나게 된다.

---

버블정렬 PseudoCode

input: 크기가 n인 array nums
output: 정렬된 array nums

for pass=0 to n
	for i=0 to n-pass
		if nums[i] > nums[i+1] then
        	nums[i] <-> nums[i+1]

• pass는 n-1번 수행한다.
• 정렬할 원소의 개수는 pass때마다 한 개씩 늘어나므로, 원소 비교는 n-pass번 수행한다.
• (오름차순 정렬할 때) 현재 원소가 그 다음 원소보다 더 클 시 두 원소를 교환한다.

---

버블정렬 Javascript

input: 크기가 n인 array nums
output: 정렬된 array nums

function solution(nums) {
    for (let pass=0; pass < n; pass++) {
        for (let i=0; i < n-pass; i++) {
            if (nums[i] > nums[i+1]) {
                [nums[i], nums[i+1]] = [nums[i+1], nums[i]];
            }
        }
    }
    return nums;
}