선택 정렬(Selection Sort)
매 단계에서 ‘아직 처리되지 않은 가장 작은 원소를 선택’해서 앞으로 보내는 정렬 방법
→ 앞으로 보내진 원소는 더 이상 위치가 변경되지 않음!
→ 선형 탐색: 매 단계에서 가장 작은 것 선택하는 데 약 N번의 연산 필요
→ 시간 복잡도: O() → 비효율적
[동작 방식]
- 각 단계에서 가장 작은 원소 선택
- 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치 교체
[JS에서의 선택 정렬]
function selectionSort(arr){
for (let i=0; i< arr.length; i++) {
let minIndex = i; // 가장 작은 원소의 인덱스
for (let j = i+1; j < arr.length; j++){
if(arr[minIndex] > arr[j]){
minIndex=j;
}
}
// 스와프(swap)
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}버블 정렬(Bubble Sort)
인접한 두 원소를 확인하여, 정렬이 안되어 있다면 위치를 서로 변경
⇒ 각 단계를 거칠 떄마다 가장 큰 값을 하나씩 확실하게 결정!
즉, 오른쪽부터 차례대로 정렬됨
💡 버블? 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 해서 붙여진 이름
→ 시간 복잡도: O() → 비효율적
[동작 방식]
첫째와 둘째 비교, 둘째와 셋째 비교, 셋째와 넷째 비교하는 방식
→ 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동(그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제외함)
[JS에서의 버블 정렬]
‣function bubbleSort(arr) {
for(let i= arr.length-1; i > 0; i--){
for (let j = 0; j < i; j++) {
if (arr[j] < arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}삽입 정렬(Insertion Sort)
각 숫자를 적절한 위치에 삽입하는 정렬 기법
→ 시간 복잡도: O(N)[최선인 경우], O()[최악의 경우]→ 비효율적
→ 이미 정렬이 되어 있는 경우는 빠르게 수행 가능(선택, 버블과 달리 속도 빠름)
[동작 방식]
- 각 단계에서 현재 원소가 삽입될 위치를 찾음
- 적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동
❗️ 삽입 정렬 처음에 첫 번째 원소를 정렬이 되어 있다고 가정
[JS에서의 삽입 정렬]
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j > 0; j--) {
// 인덱스 j부터 1까지 1씩 감소하며 반복
if (arr[j] < arr[j-1]) {
// 한 칸씩 왼쪽으로 이동
// 스와프(swap)
let temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
} else {
// 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break;
}
}
}
}병합(=합병) 정렬(Merge Sort)
전형적인 분할 정복(divide and conquer) 알고리즘 중 하나
빠른 정렬 알고리즘 중 하나
- 분할(divide): 큰 문제를 작은 부분 문제(쉬운 문제)로 분할
- 정복(conquer): 작은 부분 문제를 각각 해결
- 조합(combine): 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결
⇒ 큰 문제를 쪼개기 → 작은 문제 각각 해결 → 다시 합쳐 큰 문제 해결
→ 재귀 함수 이용하여 구현(더 이상 쪼갤 수 없는 크기가 될 때까지 계속해서 분할)
이럴 경우 오버 헤드(overhead)로 이어짐 → 메모리 소모가 큼
→ 시간 복잡도: O(NlogN)
- 직관적으로 생각했을 때, 높이가 O(logN)이고, 너비가 O(N)인 정사각형과 유사
- 장점: 최악의 경우에도 O(NlogN)을 보장할 수 있음
- 단점: 일반적인 경우, 정복 과정에서 임시 배열이 필요
[동작 방식]
- 분할 정복을 이용하는 가장 기본적인 정렬 알고리즘
-
분할(divide): 정렬할 배열(큰 문제)을 같은 크기의 부분 배열(작은 문제) 2개로 분할
→ 단순히 배열의 크기를 절반으로 쪼개는 것
-
정복(conquer): 부분 배열을 정렬 → 작은 문제를 해결
→ 두 개의 부분 배열을 “정렬된 하나의 배열”로 만든다
💡 정복(conquer) 아이디어
- 각 부분 배열은 이미 정렬된 상태로 봄
- 각 부분 배열에 대하여 첫째 원소부터 시작하여 하나씩 확인
- 총 원소의 개수가 N개일 때, O(N)의 시간 복잡도가 요구됨
- 조합(combine): 정렬된 부분 배열을 하나의 배열로 다시 병합
[JS에서의 병합 정렬]
// 병합(merge) 수행 함수
function merge(arr, left, mid, right) {
let i = left;
let j = mid+1;
let k = left; // 결과 배열의 인덱스
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
else sorted[k++] = arr[j++];
}
// 왼쪽 배열에 대한 처리가 다 끝난 경우
if (i > mid) {
for(; j <= right; j++) sorted[k++] = arr[j];
}
// 오른쪽 배열에 대한 처리가 다 끝난 경우
else {
for(; i <= mid; i++) sorted[k++] = arr[i];
}
// 정렬된 배열 결과를 원본 배열에 반영하기
for (let x = left; x <= right; x++) {
arr[x] = sorted[x];
}
}
// 병합 정렬(merge sort) 함수
// 분할 수행
function mergeSort(arr, left, right) {
// 원소가 1개인 경우, 해당 배열은 정렬된 상태로 이해 가능
if(left < right) {
// 원소가 2개 이상이라면
let mid = parseInt((left+right)/2); // 2개의 부분 배열로 분할(divide)
mergeSort(arr, left, mid); // 왼쪽 부분 배열 정렬 수행(conquer)
mergeSort(arr, mid+1, right); // 오른쪽 부분 배열 정렬 수행(conquer)
merge(arr, left, mid, right); // 정렬된 2개의 배열을 하나로 병합(combine)
}
}