정렬 알고리즘은 원소들을 번호순이나 사전 순서와 같이 일정 순서대로 열거하는 알고리즘이다. 정렬이 이루어져야 탐색, 병합 등 다른 알고리즘의 최적화로 이어질 수 있다.
면접을 보다 보니 알고리즘의 특성 및 복잡도에 대해 확실히 해야겠다는 생각이 들어 오늘부터 알고리즘을 정리하기로 함.
1. 선택 정렬
제자리 정렬 알고리즘의 하나로 로직은 다음과 같다.
① 주어진 리스트 중 최소값을 찾는다
② 그 값을 맨 앞에 위치한 값과 교체한다
③ 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다
의사 코드
for i = 0 to n:
a[i]부터 a[n-1]까지 차례로 비교해 최솟값이 a[j]에 있다.
a[i]와 a[j]의 값을 서로 맞바꾼다.실제 코드 (JS)
function selectionSort(array) {
for(let i = 0; i < array.length; i++) {
let temp = i;
for(let j = i; j < array.length; j++) {
if(array[temp] > array[j]) {
temp = j;
}
}
// 최솟값 array[temp]와 array[i]를 서로 맞바꾼다
if (temp !== i) {
let swap = array[temp];
array[temp] = array[i];
array[i] = swap;
}
}
return array;
}복잡도
시간 복잡도 : 정렬이 되어 있는 배열이어도 전체 비교를 진행하므로 O(n^2)
공간 복잡도 : 별도의 추가 공간을 사용하지 않고 주어진 배열 내에서 값들의 위치만 바꾸기 때문에 O(1)
2. 삽입 정렬
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘.
① 두번째 인덱스부터 비교를 시작한다.
② 현재 인덱스와 비교 인덱스의 배열 값을 비교한다.
③ 현재 인덱스의 배열 값이 더 작으면 비교 인덱스를 - 1하여 값을 비교한다.
④ 현재 인덱스의 배열 값이 더 크면 비교 인덱스 + 1 에 변수를 삽입한다.
이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용될 수 있다.
의사 코드
for i = 1 to n:
현재 값, 비교 인덱스
while 현재 값 < 비교 인덱스:
현재 값과 비교 값 위치 바꾼다
비교 인덱스 - 1실제 코드
// 자바스크립트
function insertionSort(array) {
for(let i = 1; i < array.length; i++) {
let cur = arr[i], left = i - 1; // 현재 값, 비교 인덱스
while (left >= 0 && cur < array[left]) {
array[left + 1] = array[left];
array[left] = cur;
cur = array[left];
left--;
}
}
return array;
}# 파이썬
def insertion_sort(arr):
for end in range(1, len(arr)):
i = end
while i > 0 and arr[i - 1] > arr[i]:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
i -= 1
복잡도
시간 복잡도 : 정렬이 하나도 안 되어 있는 경우 O(n^2), 정렬이 되어 있는 경우 O(n)
공간 복잡도 : 별도의 추가 공간을 사용하지 않고 주어진 배열 내에서 값들의 위치만 바꾸기 때문에 O(1)
3. 버블 정렬
두 인접한 원소를 검사해 정렬하는 방법이다.
① 0번 인덱스부터 이웃한 인덱스끼리 값을 비교한다.
② 두 값을 비교해 앞의 값이 더 크다면
③ 두 값을 서로 바꿔준다.
④ (배열 길이 - 순회 횟수)만큼 다시 비교를 시작한다.
이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용될 수도 있다.
의사 코드
for i = 0 to n - 1:
for j = 0 to n - 1 - i:
앞의 값이 뒤의 값보다 크다면
두 값을 바꿔준다실제 코드 (JS)
function bubbleSort(array) {
for(let i = 0; i < array.length - 1; i++) {
for(let j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j+1]) {
let temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
return array;
}복잡도
시간 복잡도 : 정렬이 하나도 안 되어 있는 경우 O(n^2), 정렬이 되어 있는 경우 O(n)
공간 복잡도 : 별도의 추가 공간을 사용하지 않고 주어진 배열 내에서 값들의 위치만 바꾸기 때문에 O(1)
4. 합병 정렬
분할 정복 알고리즘의 하나로 배열을 계속 쪼갠 뒤 최후에 하나로 합치는 방식이다.
분할
① 현재 배열을 반으로 쪼갠다.
② 배열의 크기가 0이거나 1일 때까지 반복한다.
합병
① 두 배열 A,B의 크기를 비교한다. 각 배열의 인덱스를 i,j로 한다.
② A[i]와 B[j]를 비교해 작은 값을 새 배열에 저장한다.
③ 저장 후 i 혹은 j값을 1 증가시키며 둘 중 하나가 배열의 끝에 도달하면 나머지 값을 전부 저장한다.
④ 새 배열을 원래 배열에 저장한다.
실제 코드 (JS)
function mergeSort(array) {
if (array.length < 2) return array;
let pivot = Math.floor(array.length / 2); // 반으로 쪼갤 기준
let left = array.slice(0, pivot); // 쪼갠 왼쪽
let right = array.slice(pivot, array.length); // 쪼갠 오른쪽
return merge(mergeSort(left), mergeSort(right)); // 재귀적으로 쪼개고 합친다.
}
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) { // 두 배열의 첫 원소를 비교하여
result.push(left.shift()); // 더 작은 수를 결과에 넣어줍니다.
} else {
result.push(right.shift()); // 오른쪽도 마찬가지
}
}
while (left.length) result.push(left.shift()); // 어느 한 배열이 더 많이 남았다면 나머지를 다 넣어줍니다.
while (right.length) result.push(right.shift()); // 오른쪽도 마찬가지
return result;
};복잡도
시간 복잡도 : 분할 과정은 매번 반씩 감소하므로 logn만큼 반복, 각 분할별로 합병을 진행하므로 O(nlogn)
공간 복잡도 : 별도로 하나의 배열을 필요하므로 O(n)
5. 퀵 정렬
다른 원소와 비교만으로 정렬을 수행하는 알고리즘으로 pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮긴다.
① pivot값을 설정한다.
② pivot을 제외한 배열에서 가장 왼쪽(left), 오른쪽 수(right)를 선택한다.
③ left는 pivot보다 작으면 다음으로 넘어가고 크면 가만히 있는다. right은 pivot보다 크면 다음으로 넘어가고 작으면 가만히 있는다.
left가 pivot보다 크고, right이 pivot보다 작으면 서로 바꿔준다.
④ pivot 기준 왼쪽, 오른쪽 배열에 대해 정렬을 반복한다.
실제 코드 (JS)
function partition(array, left, right, pivotIndex) { // 정렬하는 부분
let temp;
let pivot = array[pivotIndex];
while (left <= right) { // 왼쪽, 오른쪽 수를 규칙과 비교해 다음 수로 넘어간다.
while (array[left] < pivot)
left++;
while (array[right] > pivot)
right--;
if (left <= right) { // 왼쪽이 기준보다 크고, 오른쪽이 기준보다 작으면
temp = array[left];
array[left] = array[right];
array[right] = temp; // 서로 바꿔줌.
left++;
right--;
}
}
temp = array[left];
array[left] = array[pivotIndex];
array[pivotIndex] = temp; // 마지막으로 기준과 만난 수를 바꿈. 기준의 위치는 이제 i.
return left;
};
function quickSort(array, left, right) { // 재귀하는 부분
if (!left) left = 0;
if (!right) right = array.length - 1;
var pivotIndex = right; // 배열 가장 오른쪽의 수를 기준
pivotIndex = partition(array, left, right - 1, pivotIndex); // right - 1을 하는 이유는 기준(현재 right)을 제외하고 정렬하기 위함
if (left < pivotIndex - 1)
quickSort(array, left, pivotIndex - 1); // 기준 왼쪽 부분 재귀
if (pivotIndex + 1 < right)
quickSort(array, pivotIndex + 1, right); // 기준 오른쪽 부분 재귀
return array;
};복잡도
시간 복잡도 : 최선의 경우 O(nlogn), 최악의 경우(pivot이 최소 혹은 최대값인 경우) O(n^2)
공간 복잡도 : O(1)
배웠던 내용이지만 다시 공부하려니 이해가 안 되는 부분이 조금씩 있다. 두고두고 보면서 완전히 내 것으로 만들어야지
