1. 삽입 정렬 ( insertion sort )
배열 1번 인덱스부터 시작
1. 현재 배열값을 변수( current )에 저장
2. 이전 배열값의 인덱스값 변수( prev )에 저장
3. 현재값과 이전값을 비교해서 이전값이 더 크면 현재값배열에 이전값 넣음 ( 더 작은 값을 앞쪽으로 )
4. 3번을 배열의 맨 앞 or 이전값이 더 작을 때 까지 반복
5. 1 ~ 4를 배열의 모든 요소들에 모두 실행
[3, 1, 4, 2]
최초에1과3을 비교해서 더 작은 숫자를 앞으로 이동[1, 3, 4, 2]
이후에2와4을 비교해서 더 작은 숫자를 앞으로 이동[1, 3, 2, 4]
이후에2와3을 비교해서 더 작은 숫자를 앞으로 이동[1, 2, 3, 4]
// 삽입 정렬
const insertionSort = array => {
for (let i = 1; i < array.length; i++) { // 5
let prev = i - 1; // 1
let current = array[i]; // 2
while (prev >= 0 && current < array[prev]) { // 4
array[prev + 1] = array[prev]; // 3
prev--;
}
array[prev + 1] = current;
}
return array;
};2. 거품 정렬 ( bubble sort )
-
n: 배열의 마지막 값 -
비교: 두 값을 비교한 후 이전값이 더 작으면 서로 교환 -
실행 순서
1.0,1비교 =>1,2비교 =>2,3비교 ...n-1,n비교
2.0,1비교 =>1,2비교 =>2,3비교 ...n-2,n-1비교
3.0,1비교 =>1,2비교 =>2,3비교 ...n-3,n-2비교
... ( 반복 )
n.0,1비교 => 끝
위와 같은 형태로 비교하고 교체하고를 반복하면
1번 실행시 배열의 마지막에 배열중 가장 큰 숫자가 들어감
2번 실행시 배열의 마지막에 배열중 두번째로 큰 숫자가 들어감
... 위 과정을 계속 반복하면 배열이 오름차순으로 정렬됨
// 거품 정렬
const bubbleSort = array => {
for (let i = 0; i < array.length; i++) {
for (let j = 1; j < array.length - i; j++) {
if (array[j] < array[j - 1]) {
const temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
return array;
};3. 병합 정렬 ( merge sort )
병합 정렬은 전체를 한 조각으로 나누고, 다시 조각을 맞출 때 정렬하면서 맞추는 방식이다.
- 예시
[5,3,1,4,2]라는 배열을 병합 정렬했을 때
1.[5, 3, 1]와[4, 2]로 분리
2.[5, 3]과[1]그리고[4]와[2]로 분리
3.[5]과[3]으로 분리
4.[5]과[3]을 합치는데 순서에 맞게 정렬하면서 합침 =>[3, 5]
5.[3, 5]과[1]를 순서에 맞게 합침 =>[1, 3, 5]
그리고[4]와[2]를 순서에 맞게 합침 =>[2, 4]
6.[1, 3, 5]와[2, 4]를 순서에 맞게 합침 =>[1, 2, 3, 4, 5]=> 끝
조금의 디테일이 더 필요한 부분이 있지만 이론상으로는 위와 같은 방식으로 정렬함
// 병합 정렬 - 1 // 두 개로 나눠진 배열 조각을 정렬해서 합쳐서 실제 배열의 값을 변경시켜줌
const merge = (array, left, right) => {
// 중간값을 구함
let mid = Math.floor((left + right) / 2);
// 정렬을 위한 임시 배열 ( 정렬후에 실제 배열에 넣음 )
let tempArray = [];
// 정렬을 위한 임시 배열에 사용할 인덱스
let tempIndex = left;
// 좌측 인덱스
let L = left;
// 우측 인덱스
let R = mid + 1;
// 우측 인덱스나 좌측 인덱스가 영역 밖을 넘어갈 때까지 반복
while (L <= mid && R <= right) {
// 절반으로 나눠진 배열들 중에서 더 작은 놈을 임시 배열에 넣음 ( 두개로 나눠진 배열들을 오름차순으로 정렬함 )
tempArray[tempIndex++] = array[L] <= array[R] ? array[L++] : array[R++];
}
// 이미 정렬된 배열이므로 한쪽이 다 끝났다면 다른 한쪽은 정렬된 값이라서 그대로 넣어주기만 하면 됨
// 두개로 나눠진 배열 중에서 좌측이 먼저 끝났다면 우측에 남은 배열을 순서대로 임시 배열에 넣음
if (L > mid) {
for (let i = R; i <= right; i++) {
tempArray[tempIndex++] = array[i];
}
}
// 두개로 나눠진 배열 중에서 우측이 먼저 끝났다면 좌측에 남은 배열을 순서대로 임시 배열에 넣음
else {
for (let i = L; i <= mid; i++) {
tempArray[tempIndex++] = array[i];
}
}
// 정렬된 임시 배열의 값을 실제 배열에 넣어줌
for (let i = left; i <= right; i++) {
array[i] = tempArray[i];
}
};
// 병합 정렬 - 2 // 재귀적으로 호출해서 (((전체 / 2) / 2) / 2 ...)를 한 조각이 남을 때 까지 반복함
const mergeSort = (array, left, right) => {
// 배열이 한 조각으로 나눠졌다면 더 이상의 반복은 종료
if (left === right) return;
// 배열을 절반으로 나누기 때문에 배열 길이의 중간값을 구함
let mid = Math.floor((left + right) / 2);
// 좌측 ~ 절반 계산
mergeSort(array, left, mid);
// 절반+1 ~ 우측 계산
mergeSort(array, mid + 1, right);
// 여기서부터 나눴던 조각을 정렬하면서 합침
merge(array, left, right);
};4. 힙 정렬 ( Heap Sort )
- 선행해야 할 지식
1. 힙
2. 완전이진트리
3. 최소힙, 최대힙
// 배열의 두 개의 값 교체
const swap = (array, x, y) => {
let temp = array[x];
array[x] = array[y];
array[y] = temp;
};
// 최초에 힙으로 변경
const heapify = (array, currentIndex) => {
if (currentIndex <= 1) return;
// 배열을 최대힙으로 변경시킴
let index = Math.floor(currentIndex / 2);
while (index >= 0) {
maxHeapify(array, index, currentIndex);
index--;
}
};
// 배열을 최소힙으로 변경시켜줌
const minHeapify = (array, index, length) => {
// 현재 노드를 부모노드로 기준점을 잡고 좌측자식노드, 우측자식노드를 구함 ( 인덱스가 0부터 시작이므로 "*2+1", "*2+2" 를 적용하는 것임 )
let parent = index;
let left = index * 2 + 1;
let right = index * 2 + 2;
// 아래 두 개의 if문을 통해서 부모, 좌측자식, 우측자식 3개를 비교해서 가장 작은놈을 parent인덱스에 기록함
// 좌측자식노드가 부모노드보다 작다면 그 인덱스를 기록함
if (left < length && array[left] > array[parent]) {
parent = left;
}
// 우측자식노드가 부모노드보다 작다면 그 인덱스를 기록함
if (right < length && array[right] > array[parent]) {
parent = right;
}
// 만약 자식노드들 중에서 부모노드보다 작은게 존재했다면
// 부모노드와 자식노드를 바꾸고 다시 바꾼놈을 최소힙함수 실행
if (parent !== index) {
swap(array, index, parent);
minHeapify(array, parent, length);
}
};
// 힙 정렬 시작
const heapSort = array => {
// 반복할 때 마다 마지막에 가장 작은 값이 들어감... 따라서 마지막요소는 다음 반복부터 제외시킴
for (let i = array.length - 1; i >= 0; i--) {
// heapify()를 한 번 실행하면 array[0]에 가장 작은값이 들어있음
heapify(array, i);
// 배열의 제일 마지막에 가장 작은 값을 넣음
if (array[0] > array[i]) {
swap(array, i, 0);
}
}
};5. 퀵 정렬 ( quick sort )
- 1
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 배열의 두 개의 값 교체
const swap = (array, x, y) => {
let temp = array[x];
array[x] = array[y];
array[y] = temp;
};
// 피벗으로 좌측, 우측으로 나눔
const partition = (array, left, right) => {
// 기준점, 좌측시작지점, 우측시작지점 지정
let pivot = array[left];
let low = left;
let high = right + 1;
do {
// 좌측부터 시작해서 기준점보다 큰 값 발견되면 탈출
do {
low++; // 좌측으로 한 칸 이동
} while (low <= right && array[low] < pivot);
// 우측부터 시작해서 기준점보다 작은 값 발견되면 탈출
do {
high--; // 우측으로 한 칸 이동
} while (high >= left && array[high] > pivot);
// 이부분은 한쪽으로만 계속 이동했을 경우를 위한 것
if (low < high) {
swap(array, low, high);
}
} while (low < high);
// 기준점의 위치를 잡음 ( 여기 이후로는 기준점기준으로 좌측은 작고 우측은 큼 )
swap(array, left, high);
// 새로운 기준점이 된 인덱스를 반환
return high;
};
// partition()을 나누면서 재귀적으로 반복함
const quickSort = (array, left, right) => {
if (left < right) {
let pivot = partition(array, left, right);
quickSort(array, left, pivot - 1);
quickSort(array, pivot + 1, right);
}
};
const input = [];
rl.on("line", line => {
input.push(+line);
if (input.length >= 2 && input[0] === input.length - 1) rl.close();
}).on("close", () => {
input.shift();
const array = input;
//정답 기록
let answer = "";
quickSort(array, 0, array.length - 1);
array.forEach(v => (answer += `${v}\n`));
console.log(answer);
process.exit();
});- 2
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 배열의 두 개의 값 교체
const swap = (array, x, y) => {
let temp = array[x];
array[x] = array[y];
array[y] = temp;
};
// 퀵정렬
const quickSort = (array, left, right) => {
// 피벗, 좌측과 우측에서 이동할 인덱스 지정
const pivot = array[left]; // 피벗은 범위내부의 아무거나 지정해도 상관없음
let leftIndex = left;
let rightIndex = right;
// 이동인덱스들이 서로 만나거나 교차할 때 까지 반복
while (leftIndex <= rightIndex) {
// 좌측 -> 우측 이동하는 동안 피벗보다 큰 값을 발견하면 반복종료
while (array[leftIndex] < pivot) leftIndex++;
// 우측 -> 좌측 이동하는 동안 피벗보다 작은 값을 발견하면 반복종료
while (array[rightIndex] > pivot) rightIndex--;
// 이동인덱스들이 같거나 교차하지않았다면 서로 교환
if (leftIndex <= rightIndex) {
swap(array, leftIndex, rightIndex);
leftIndex++;
rightIndex--;
}
}
// 정렬이 된 남은 배열 두개를 나눠서 다시 퀵정렬 시작을 재귀호출
if (left < rightIndex) quickSort(array, left, rightIndex);
if (right > leftIndex) quickSort(array, leftIndex, right);
};
const input = [];
rl.on("line", line => {
input.push(+line);
if (input.length >= 2 && input[0] === input.length - 1) rl.close();
}).on("close", () => {
input.shift();
const array = input;
//정답 기록
let answer = "";
quickSort(array, 0, array.length - 1);
array.forEach(v => (answer += `${v}\n`));
console.log(answer);
process.exit();
});6. 카운팅 정렬
const input = [5, 2, 3, 1, 4, 2, 3, 5, 1, 7];
const maxNumber = Math.max(...input);
const array = Array(maxNumber).fill(0);
input.forEach(v => array[v - 1]++);
let answer = "";
array.forEach((v, index) => {
for (let i = 0; i < v; i++) {
answer += `${index + 1}\n`;
}
});
console.log(answer);0. 마무리
이 정렬 알고리즘들은 원리를 이해하는데도 힘든데 원리를 이해하고 난 후 그 이해한 원리를 코드로 변환시키고 적용시키는 데는 더 많은 시간이 필요한 것 같음
여기에 정리하는 정렬 알고리즘들은 지금은 물론 원리는 이해했지만 안 보고 코드를 작성하라고 하면 못할 것 같음
주기적으로 공부해야 할 것 같음 ( 특히 힙, 병합 정렬 )
아니 그리고 추가로 백준 - 2751번은 병합 정렬은 메모리초과, 힙 정렬은 시간초과인데 내가 코드를 잘못짠건지 추후에 다시 시도해보겠음
...