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

fgStudy·2022년 5월 31일
0
post-thumbnail

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


버블정렬 정의

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

(오름차순 정렬 시) 작은 수가 올라오는 과정이 거품같다고 해서 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;
}
profile
지식은 누가 origin인지 중요하지 않다.

0개의 댓글