버블정렬
버블정렬이란?
버블정렬은 배열을 오름차순으로 정렬을 한다고 할 때, 더 큰 숫자가 한번에 하나씩 뒤로 이동을 하는 방식이다. 루프를 돌면서 각 항목을 다음 항목과 비교해서 해당 숫자가 비교 대상보다 더 큰지 확인하고, 만약 더 크다면 교환한다.
📚여기서 교환(swap)이란?
자바스크립트에서 교환 방법은 대표적으로 두 가지가 있다.
//ES5 => temp라는 변수에 따로 idx1의 값을 저장해두고 바꾸는 방식
function swap(arr, idx1, idx2) {
var temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
//ES6 => syntax를 통해 서로의 값을 교환하는 방법
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
이 루프는 처음 수부터 마지막 수까지 계속 움직이면서 교환하지만, 바로 뒤의 숫자밖에 교환할 수 없기 때문에 앞의 숫자는 관여할 수 없다. 그렇기 때문에 이러한 루프는 마지막에서부터 1개씩만 정렬이 100% 보장되기 때문에 n-1개씩 계속해서 루프를 돌려야 한다.
구현
ES5 방식의 교환으로 구현
function bubbleSort(arr) {
// 맨 뒤는 하나씩 무조건 정렬되기 때문에 정렬 횟수를 줄이기
for (let i = arr.length; i > 0; i--) {
//i-1까지 반복시키면서 불필요한 초과정렬연산 막기
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
//ES5방식의 swap
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
console.log(bubbleSort([37, 45, 29, 8, 12, 88, -3]));
ES6방식으로 구현
function bubbleSort(arr) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
// 맨 뒤는 하나씩 무조건 정렬되기 때문에 정렬 횟수를 줄이기
for (let i = arr.length; i > 0; i--) {
//i-1까지 반복시키면서 불필요한 초과정렬연산 막기
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
//ES6방식의 swap
swap(arr, j, j + 1);
}
}
}
return arr;
}
console.log(bubbleSort([37, 45, 29, 8, 12, 88, -3]));
최적화
만약 데이터가 거의 정렬이 된 상태거나, 이미 정렬이 완료된 상태라면 버블 성렬을 할 필요가 없어진다. 기본적인 버블 정렬 알고리즘은 해당 데이터를 다르게 처리하지 않고 여전히 항목 하나하나를 정렬하려고 하기 때문에 정렬 과정에서 필요없는 비교가 너무 많아지게 된다.
function bubbleSort(arr) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};
// 맨 뒤는 하나씩 무조건 정렬되기 때문에 정렬 횟수를 줄이기
for (let i = arr.length; i > 0; i--) {
//i-1까지 반복시키면서 불필요한 초과정렬연산 막기
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
//ES6방식의 swap
swap(arr, j, j + 1);
}
}
}
return arr;
}
// 정렬이 돼 있음에도 7!의 비교를 수행한다
console.log(bubbleSort([8, 1, 2, 3, 4, 5, 6, 7]));그렇기 때문에 버블 정렬을 최적화하는 방법은, 해당 루프가 마지막으로 실행됐을 때 교환을 하지 않았다면 정렬이 완료된 상태임을 알고 정렬이 된 부분을 생략하는 것이다.
let noSwaps;
// 맨 뒤는 하나씩 무조건 정렬되기 때문에 정렬 횟수를 줄이기
for (let i = arr.length; i > 0; i--) {
noSwaps = true;
//i-1까지 반복시키면서 불필요한 초과정렬연산 막기
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
//ES5방식의 swap
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//swap이 이루어졌으므로 false로 바꾸기
noSwaps = false;
}
}
//한 번도 교환이 없었다 = 더이상 정렬할 것이 없음
//한 번도 교환이 이루어지지 않았으면 true값으로 유지되기 때문에 바로 break를 통해 빠져나감
if (noSwaps) break;
}
return arr;
}
console.log(bubbleSort([-8, 1, 2, 3, 4, 5, 6, 7]));
시간복잡도
Average: 배열을 반복해서 돌면서 각 항목마다 n번의 비교를 해야 하기 때문
Best Case: 0데이터가 거의 정렬됐거나 이미 정렬이 끝난 상태에서 noSwaps 변수가 있는 최적화 버전을 사용했을 때
Worst Case:
선택정렬
선택정렬이란?
- 버블정렬과 비슷하지만, 큰 값을 배열의 끝에 위치시키는 대신 작은 값을 한 번에 하나씩 위치에 배열하는 방식
- 버블정렬과 같이 처음부터 끝까지 움직이지만, 실제 정렬된 데이터는 처음부터 누적됨
- 배열을 돌며 최소값을 찾아 맨 앞에서 하나씩 증가하는 인덱스와 바꾸어 정렬하는 방식
- 이러한 방식으로 정렬을 하면 맨 앞부터 하나씩 정렬이 될 것이고, 최솟값을 찾는 것도 앞에서 하나씩 뒤로 당기면서 최솟값을 찾는 범위를 줄여가면 됨
구현
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 min = i;
// 안쪽 루프문 => 최솟값 비교
for (let j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
// 굳이 바꿀 필요가 없는 경우에 바꾸지 않도록 조건 명시
if (i !== min) swap(arr, i, min);
}
return arr;
}
selectionSort([34, 22, 10, 19, 17]);시간복잡도
Average:
Best Case:
Worst Case:
삽입정렬
삽입정렬이란?
버블정렬이나 선택정렬같이 한 번에 가장 큰 요소를 찾거나 한 번에 가장 작은 요소를 찾는 대신 앞에서부터 순서대로 각 요소를 취하여 정렬되어 있는 요소들 속에 위치를 찾고 배치하면서 점진적으로 정렬을 구축한다.
구현
function insertionSort(arr) {
// 바깥쪽 루프문 -> 정렬할 숫자 고르기
for (var i = 1; i < arr.length; i++) {
var currentVal = arr[i];
// 안쪽 루프문 -> 정렬할 숫자 왼쪽에 있는 요소들이 정렬되어 있기 때문에 해당 배열 범위 안을 거꾸로 돌며 위치 찾기
for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
// 새로 들어오는 수의 공간을 만들기 위해 오른쪽으로 하나씩 밀어내기
arr[j + 1] = arr[j];
}
arr[j + 1] = currentVal;
}
return arr;
}
insertionSort([2, 1, 9, 76, 4]);
시간복잡도
Average:
Best Case: O(n) 온라인 알고리즘 데이터의 경우 실시간으로 최신 데이터가 들어올 때마다 필요한 자리에 정렬시킬 수 있음(정렬된 부분을 유지하고 적절한 위치에 항목을 삽입하기 때문)
Worst Case: 배열의 길이가 늘어날 수록 비교 횟수를 기본적으로 n제곱해야 함 특히 가장 최악인 케이스는 역순으로 정렬(내림차순)되어있을 때 가장 느림
정렬 알고리즘 비교
| 알고리즘 | 시간복잡도(Best) | 시간복잡도(Average) | 시간복잡도(Worst) | 공간복잡도 |
|---|---|---|---|---|
| 버블정렬 | ||||
| 삽입정렬 | ||||
| 선택정렬 |