~51일차~
코딩테스트 스터디에서 강의를 듣고 정리해보았다.
1. 선택정렬(Selection Sort)
- 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법
- 시간 복잡도 O(N2)로 비효울적인 정렬 알고리즘 중 하나
1) 동작 방식
- 각 단계에서 가장 작은 원소를 선택
- 현재 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교체
2) 소스코드 예시
//선택 정렬 함수
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[min Index] = temp;
}
}3) 시간 복잡도
- 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법
- 매 단계에서 가장 작은 것을 선택하는 데에 약 N번의 연산이 필요(선형 탐색)
- 결과적으로 약 N개의 단계를 거침 -> 최악의 경우 O(N2)의 시간 복잡도를 가짐
2. 버블 정렬(Bubble Sort)
- 인접한 두 원소를 확인, 정렬이 안 되어 있다면 위치를 서로 변경
- 시간 복잡도 O(N2)로 비효율적인 정렬 알고리즘 중 하나
1) 동작 방식
- 인접한 두 개의 원소를 비교, 필요 시 위치 변경
- 따라서, 그 다음 단계에서, 맨 뒤로 이동한 데이터는 정렬에서 제외
중요 - 각 단계를 거칠때마다 가장 큰 값을 하나씩 확실하게 결정하는 것
- 구현은 쉬우나, 비효율적이기에 큰 데이터에는 사용해선 안된다.
2) 소스코드 예시
//버블 정렬 함수
function bubbleSort(arr) {
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] < arr[j + i]) {
let temp = arr[j];
arr[j] = arr[j + i];
arr[j + 1] = temp;
}
}
}
}3) 시간 복잡도
- 최악의 경우 O(N2)의 시간 복잡도를 보장 (이중 반복문의 전형적인 예시)
- 이미 정렬된 배열에 대해 모든 비교가 필요 -> 굉장히 비효율적
3. 삽입 정렬(Insertion Sort)
- 각 숫자를 적절한 위치에 삽입하는 정렬 기법
1) 동작 방식
-
각 단계에서 현재 원소가 삽입될 위치를 찾는다
-
적절한 위치에 도달할 때까지 반복적으로 왼쪽으로 이동
-
동작과정이 매우 직관적이나, O(N2)의 시간 복잡도를 가져 비효율적
-
처음에 첫번째 원소는 정렬이 되어 있다고 고려
-
선택적보다는 효율적일 수 있음
2) 소스코드 예시
//삽입 정렬 함수
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-i]) {
// 한 칸씩 왼쪽으로 이동
//스와프(swap)
let temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
} else {
// 작은 데이터를 만나면 그 위치에서 멈춤
break;
}
}
}
}
3) 시간 복잡도
-각 원소를 적절한 위치에 삽입하는 정렬 기법
- 매 단계에서 현재 처리 중인 원소가 삽입될 위치를 찾기 위해 약 N번의 연산이 필요
- 결과적으로 약 N개의 단계를 거침 -> 최악의 경우 O(N제곱)의 시간 복잡도
4. 병합 정렬(Merge Sort)
- 전형적인 분할 정복(divide and conquer) 알고리즘
- 비교적 빠르고 상대적으로 효율적으로 동작
- 굉장히 많이 사용
1) 분할 정복
-일반적으로 재귀 함수를 이용하여 구현
-> 큰 문제를 작은 문제로 "분할하는 방식이 동일한" 경우가 많기 때문
-더 이상 쪼갤 수 없는 크기가 될 때까지 계속하여 분할
① 분할 정복 동작방식
- 분할(divide) : 큰 문제를 작은 부분 문제(쉬운 문제)로 분할
- 정복(conquer): 작은 부분 문제를 각각 해결
- 조합(combine): 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결
② 분할 정복의 단점
- 재귀함수 -> 함수 호출 회수가 많이 발생
- 너무 깊어지면 스택오버플로우 발생
- 오버헤드(overhead)로 이어짐
2) 병합 정렬의 특징
시간 복잡도 O(NlogN)을 보장하는 빠른 정렬 알고리즘 중 하나
3) 동작 방식
분할 정복을 이용하는 가장 기본적인 정렬알고리즘
1. 분할(divide) : 정렬할배열(큰 문제)을 같은 크기의 부분 배열(작은 문제) 2개로 분할
2. 정복(conquer): 부분 배열 정렬
3. 조합(combine): 정렬된 부분 배열을 하나의 배열로 다시 병합
- 각 부분 배열은 이미 정렬된 상태로 봄
- 각 부분 배열에 대하여 첫째 원소부터 시작, 하나씩 확인
- 총 원소 개수 N개 -> O(N)의 시간 복잡도 요구
4) 시간 복잡도
직관적으로 생각
-> 높이가 O(logN), 너비 O(N)인 정사각형과 유사
- 장점 : 최악의 경우에도 시간 복잡도 O(NlogN) 보장하는 점이 효율적
- 단점: 일반적인 경우 정복 과정에서 임시 배열이 필요
//(정복 이후) 병합(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 (; <= mid; i++) sorted[k++] = arr[i];
}
// 정렬된 배열 결과를 원본 배열에 반영하기
for (let x = left; x <= right; x++) {
arr[x] = sorted[x];
}
}
//실질적 병합 정렬(merge sort) 함수
//left:첫번째 원소의 인덱스, right:마지막 원소의 인덱스
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)
}
}