Bubble Sort
버블 정렬은 배열의 가장 앞 인덱스부터 차례대로 두 수를 비교하여 큰 수와 작은 수의 위치를 변경하여 가장 마지막 인덱스에 제일 큰 수를 고정하는 정렬 방식이다. 한 번 순회하면 가장 끝의 수는 배열에서 가장 큰 수가 고정되므로 고정된 인덱스를 제외하고 비교한다. 그러므로 순회가 끝나면 그 다음 순회에서는 비교할 인덱스가 하나 적어진다.
이를 코드로 작성하면 아래와 같다. 외부 for문은 배열을 순회할 횟수를 정한다. 예를 들어,[1,12,9,7]의 배열을 순회한다고 한다면 첫 번째 순회에서는 [1,12,9,7], 두 번째 순회에서는 [1,9,7], 세번째 순회에서는 [1,7]을 검사하므로 총 세번 돌게 된다. 이러한 로직을 배열의 길이를 통해 작성할 수 있다.
내부 for문에서는 비교할 인덱스 번호들을 나타낸다. j는 첫번째 비교할 수, j+1은 두번째 비교할 수이다. j+1이 검사할 가장 마지막 인덱스가 되어야 하므로 j+1<i -> j<i-1의 조건문을 이용한다. 콘솔로그로 반복문마다 값을 출력해보면 j는0,1,2,0,1,0 순으로 j+1은 1,2,3,1,2,1 순이 된다.
이제 인덱스 값에 따른 배열의 요소를 비교하여 만약 앞의 값이 더 크면 뒤의 값과 앞의 값을 swap한다. temp에 arr[j]를 담아 놓고 arr[j]에 arr[j+1]를 할당한다. arr[j+1]는 앞서 앞의 수를 담아놓았던 temp를 할당하여 swap할 수 있다.
function bubbleSort(arr) {
for (let i = arr.length; i > 1; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
//swap
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
bubbleSort([1, 12, 9, 7]); // [1,7,9,12]
<br>
Destructuring
구조분해 할당을 이용하여 swap 로직을 아래와 같이 간결하게 작성할 수도 있다. 위 코드와 결과는 같다.
function bubbleSort(arr) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
for (let i = arr.length; i > 1; i--) {
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
}
bubbleSort([1, 12, 9, 7]);
최적화
위의 정렬 방식은 정렬이 거의 마쳐진 배열에서도 무조건 모든 인덱스의 검사를 거쳐야 한다는 점에서 시간 복잡도의 효율이 떨어진다. 중첩 for문이므로 O(n^2)의 시간 복잡도를 가질 것이다. 만약 swap이 없다면 검사를 중단하는 조건을 추가한다면 필요없는 연산 과정을 줄일 수 있다. 아래 예시와 같이 거의 정렬되어 있는 배열이라면 최적화 코드에서 시간 복잡도는 O(n)이다.
noSwaps이라는 변수를 하나 선언하여 매번 연산을 시작할 때 값을 true로 할당한다. 만약 swap이 일어나면 값은 false가 된다. 한 번의 순회가 끝났을 때 swap이 한 번이라도 있었다면 다음 순회로 넘어가고, 한 번도 swap이 없었다면 반복문을 빠져나와 모든 연산을 종료한다. 아래 예시에서는 첫 순회에서 완벽한 정렬이 되므로 2번째 순회에서는 noSwaps 변수의 값이 변하지 않고 그대로 반복문을 빠져나와 배열을 반환한다.
function bubbleSort(arr) {
let noSwaps;
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
for (let i = arr.length; i > 1; i--) {
noSwaps = true;
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
noSwaps = false;
}
}
if (noSwaps) break;
}
return arr;
}
bubbleSort([1, 9, 7, 10]);
Selection Sort
선택 정렬은 가장 앞 인덱스부터 배열의 최소값을 저장해나가는 식으로 정렬하는 방식이다.
순회마다 저장할 인덱스와 최소값을 비교하여 나간다.
아래 코드르 예시로 외부 for문에서는 lowest변수에 순회 끝에 찾아낸 최소값을 저장할 index를 초기값으로 할당한다. 내부 for문에서는 초기값으로 할당한 index의 다음 index부터 비교를 시작하여 더 작은 값을 가지면 lowest에 저장되는 index가 변경된다. 만약 초기에 할당했던 index가 결국 순회 끝에 찾아낸 최소값과 같다면 swap이 수행되지 않고, lowest값이 변경되었다면 swap을 실행한다.
시간 복잡도는 중첩 for문으로 매 순회마다 모든 요소를 비교하므로 O(n^2)이다. Bubble Sort는 두 수를 비교하여 큰 수를 계속해서 swap해야 한다면 Selection Sort는 순회당 한 번의 swap이 이루어진다는 점에서 이점이 있다.
function selectionSort(arr) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
for (let i = 0; i < arr.length; i++) {
let lowest = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) {
lowest = j;
}
}
if (i !== lowest) swap(arr, i, lowest);
}
return arr;
}
console.log(selectionSort([1, 9, 7, 10]));
Insertion Sort
삽입 정렬은 정렬된 숫자들에 비교과정을 통해 해당 인덱스가 삽입되어 정렬하는 방식이다. 실시간으로 입력받은 데이터가 중간에 삽입되어 정렬되어야 할 때 유용하다.
맨 처음 요소부터 정렬되어 있는 숫자라 가정한다. 그러므로 두번재 요소부터 순회를 시작하며 currentVal에 두번째 인덱스의 값을 담는다. currentVal는 바로 앞의 인덱스부터 0번째 인덱스까지 거꾸로 하나씩 비교한다. 이때 비교할 값이 currentVal보다 클 때 반복문을 수행한다는 조건을 추가하여 불필요한 연산을 줄여준다. 그러므로 이러한 조건을 충족하지 못하면 while문은 실행되지않고 j도 -1의 연산이 수행되지 않으므로 j+1=i이고 원래 인덱스에 그대로 currentVal을 다시 담는다. 만약 비교할 값이 더 크다면 반복문을 수행하게 되는데 currentVal를 삽입하기 위하여 arr[j]를 다음 값에 한 칸씩 미루어 담는다.
시간 복잡도는 정렬할 숫자가 얼마나 정렬되어있는지에 따라 다르다. 만약 [4,3,2,1]의 배열을 Insert Sort의 방식으로 정렬한다면 매번 앞의 요소들의 비교과정과 연산을 수행하야 하므로 O(n^2)의 시간 복잡도를 가진다. 반대로 거의 정렬되어 있는 배열인 [1,2,3,0]을 정렬한다면 가장 마지막 요소인 0만 비교와 연산을 수행하므로 O(n)의 시간복잡도를 가질 수도 있다.
function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > currentVal) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = currentVal;
}
return arr;
}
insertSort([2, 1, 9, 76, 4]); // [ 1, 2, 4, 9, 76 ]Bubble Sort, Selection Sort, Insert Sort 비교
평균 시간 복잡도
세 정렬의 방식 모두 중첩된 반복문의 형태로 O(n^2)이다.
거의 정렬되어 있는 데이터의 시간 복잡도
-
Bubble Sort와 Insert Sort는 요소들의 값을 비교하여 조건에 충족할 때만 연산을 수행하므로 O(n)이다.
-
Selection Sort는 무조건 모든 요소들을 비교하여 최소값을 찾아내야 하므로 O(n^2)이다.
공간 복잡도
배열의 길이가 늘어나도 변수가 추가되거나 하지 않고 늘 같은 알고리즘의 형태를 가지므로 O(1)이다.
Reference
