해당 포스팅에서는 정렬 기법 중 하나인 버블정렬에 대해 설명한 후 버블정렬을 자바스크립트로 구현해보고자 합니다.
버블정렬은 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동
시키는 과정을 반복하는 정렬기법이다.
(오름차순 정렬 시) 작은 수가 올라오는 과정이 거품
같다고 해서 Bubble sort라고 불린다.
input: 크기가 n인 array nums
output: 정렬된 array nums
첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를 ... n-1번째 원소와 n번째 원소를 비교하고 교환하면서 배열을 정렬한다.
그러면 가장 큰 수가 배열의 맨 뒤에 배치된다.
1번째 pass를 수행하고 나면 가장 큰 수가 맨 뒤에 배치되므로, 2번째 pass때는 맨 마지막 원소는 제외하고 정렬을 한다. 2번째 pass를 수행하면 두 번째로 큰 수가 뒤에서 두 번째 위치에 배치된다.
2번째 pass를 수행하고 나면 가장 큰 수와 두 번째로 큰 수가 이미 맨 뒤에 정렬되어 있다. 따라서 그 둘을 제외하고 정렬을 한다. 3번째 pass를 수행하면 3번째로 큰 수가 뒤에서 세 번째 위치에 배치된다.
이렇게 정렬을 수행할때마다 정렬에서 제외되는 원소들이 늘어나게 된다.
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]
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;
}