원본 글
버블 정렬 알고리즘 - DEV 커뮤니티
Maximilian
소개
저는 최근 저수준 프로그래밍과 컴퓨터 과학 개념을 배우기 위한 여정의 일환으로 자료구조와 알고리즘 강의를 수강했습니다. 속담에도 있듯이, 어떤 것에 대한 지식을 확고히 하는 가장 좋은 방법은 그것을 가르치는 것입니다. 그리고 이번 달(아마 올해) 분량으로 파트너에게 코딩 이야기로 지루함을 안겨줄 할당량은 이미 채웠기 때문에, 제가 배운 것들을 담은 글을 연재하기로 했습니다. 이 글도 그중 하나입니다.
버블 정렬 알고리즘이란
버블 정렬 알고리즘은 일반적으로 효율성보다 단순함이 우선시되는 경우에 사용됩니다. 시간 복잡도는 O(n^2)이며, 리스트가 클 때는 이상적이지 않습니다.
어떻게 동작하나요
동작 방식을 설명하기 위해 의사 코드를 소개합니다:
for pointer1 in list
for pointer2 in list
if list[j] > list[j + 1]
swap list[j] and list[j + 1]
pointer2++
pointer1++
이 알고리즘의 아이디어는 리스트에서 더 큰 항목을 끝까지 '버블업'하는 것입니다. 이는 pointer1과 pointer2라는 두 개의 포인터로 생각할 수 있습니다. 먼저 두 포인터를 모두 리스트의 첫 번째 항목으로 설정합니다. 그런 다음 pointer2로 리스트 전체를 순회하면서, pointer2 + 1 위치의 항목 값이 더 크면 pointer2 위치의 항목과 교환합니다. 리스트의 끝에 도달할 때까지 이 과정을 계속 반복합니다. 그런 다음 pointer1을 1만큼 이동하고 pointer2로 다시 과정을 시작합니다.
이미 정렬된 항목을 다시 검사하지 않도록 하는 방법이 필요하다는 것을 눈치채셨을 수도 있습니다. 각 반복의 목적이 더 큰 항목을 리스트 끝으로 옮기는 것이므로, pointer2의 경계를 pointer1 + 1의 값으로 제한하여 이를 수행할 수 있습니다.
어떻게 구현하나요
주석을 많이 단 Typescript 구현은 다음과 같습니다:
function bubbleSort(arr: number[]): void {
// pointer 1
for (let i = 0; i < arr.length; ++i) {
// pointer 2 + limit iterations by pointer1 + 1
for (let j = 0; j < arr.length - 1 - i; ++j) {
// check if current item is larger than the next item
if (arr[j] > arr[j + 1]) {
// temporarily store the current item so we don't lose it
const tmp = arr[j];
// swap the items in the array
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
정렬 완료
대부분의 경우 가장 먼저 떠올릴 만한 알고리즘은 아니지만, 시작하기에 쉽고 좋은 알고리즘이라고 생각합니다. 유용하게 보셨기를, 아니면 적어도 조금은 흥미로우셨기를 바랍니다!