공부하면서 문제를 풀어 본 버블정렬, 삽입정렬, 합병정렬을 제외한 다른 정렬들에 대해서 정리해보고자 한다.
정렬의 경우, 알고리즘에서 자주 나오는 개념이며 이후에도 활용하기 좋은 개념이다.
Selection Sort(선택정렬)
선택정렬은 이름 그대로, 배열을 순회하면서 가장 작은 수를 찾아 선택하여, 배열의 맨 앞부터 순회해서 기준 수가 더 작은 경우 그 순회하는 숫자와 자리를 바꿔준다.
선택정렬에 대한 추가 설명(참고 블로그)
해당 정렬은 버블정렬만큼이나 직관적으로 이해하기 쉽지만, 비효율적인 정렬방법이다.
하지만 버블정렬이나 선택정렬같은 경우, 요소의 수가 적을 때는 오히려 더 효율적이다.
- 배열을 순회하며, 작은 수 찾고
- 두번째 순회에서 해당 인덱스의 값과 그 가장 작은수의 위치를 바꿔줘야 한다.
(가령 첫번째 순회의 경우, 첫번째 인덱스 값과 그 배열의 가장 작은 수의 위치를 바꿔주면 된다.)
따라서 시간복잡도는 n^2이 될 것이다.
const selectionSort = function(array) {
for (let i = 0; i < array.length - 1; i++) {
// 처음부터 훑되, 가장 마지막 인덱스 돌기전에는 자연스레 오름차순으로 정렬
//되어있을 테니까 길이의 -1 직전 까지 순회한다.
for (let j = i + 1; j < array.length; j++) {
// 최솟값의 위치를 찾음
//i+1 부터 시작하는 이유는 내가 현재 위치한 수의 이전까지는 이미 정렬되어있거나
//자기 자신이므로 크기를 비교할 필요가 없다.
// 가장 작은 수를 찾기 위한 순회 이므로, 이 경우에는 배열 끝까지 다 돌아야 한다.
if (array[i] > array[j]) {
//현재 위치한 인덱스의 수보다(지금은 첫번째 인덱스) 순회도는 인덱스의 수가 작으면
let temp = array[j]; // 최솟값을 저장
array[j] = array[i];
array[i] = temp; // 최솟값을 제일 앞으로 보내기
}
}
}
return array;
};Shell 정렬(셸정렬)
삽입정렬을 보완한 알고리즘이다.
블로그에 있는 삽입정렬에 대한 설명
삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동하게 되는데,
만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면
많은 이동을 해야만 제자리로 갈 수 있다. 즉 효율성이 떨어진다.
- 주어진 배열 중에서, 특정 기준으로 배열을 부분리스트로 나눈다.
(여기서 gap이라고 한다.)
-> 가령 10개의 요소를 가진 배열이 있다면, 여기서 gap은 10/2(정렬할 값의 수/2) 이다.
-> 주어진 배열에서 5개 요소씩 나누어 부분 배열을 만든다. 만약에 5개 안된다면 남은 수 끼리로라도
(요소가 하나인 부분리스트는 그냥 둔다.)
(gap은 홀수가 좋다. 따라서 짝수가 나오면 +1을 한다.)
-> 그리고 나눈 부분리스트의 각 인덱스끼리 크기를 비교 후, 작은 수와 큰 수를 한 쪽으로 몰아 준다. - 이렇게 점차 gap을 2씩 줄이면서 정렬을 진행한다.
셸정렬은 gap을 잘못 설정할 경우, 시간복잡도가 n^2가 나온다.
function shellSort(arr) {
let gap = Math.floor(arr.length / 2);
//여기서 gap은 무조건 홀수여야 한다.
while (gap > 0) {
if(gap%2 ===0){
gap += 1
}
for (let i = 0; i < arr.length - gap; i++) {
//gap을 기준으로 나눈 부분 리스트들을 순회하는 거라서 종료는 길이에서 gap까지
let currentIndex = i;
let gapShiftedIndex = i + gap;
while(currentIndex >=0){
//해당 반복문을 넣어주고 아래에, 인덱스 교체 작업을 해주는 이유는,
//전체 배열이 gap으로 완전히 나누어 떨어지지 않는 경우에도 작업을 해주기 위해서이다.
//부분 리스트의 수가 두개가 아니라 여러개인 경우,
//첫번째와 두번째 부분리스트를 비교하고, 두번째와 세번째 부분리스트를 비교하기 위함이다.
if (arr[gapShiftedIndex] <= arr[currentIndex]) {
const temp = arr[currentIndex];
arr[currentIndex] = arr[gapShiftedIndex];
arr[gapShiftedIndex] = temp;
}
gapShiftedIndex = currentIndex
currentIndex -=gap
}
}
gap = Math.floor(gap / 2);
}
return arr;
}quick Sort(퀵정렬)
매우 빠른 속도의 정렬 방법이다. 합병정렬과 비슷하게 주어진 배열을 분리하고 크기 비교를 하지만,
균등하게 쪼개지 않고 랜덤하게 하나의 요소를 선택해서 그것을 기준으로 비균등하게 쪼갠다.
주어진 배열에서 랜덤하게 한 수를 뽑고(이를 pivot(피벗)이라 부른다.),
이 수를 기준으로 작은 수는 왼쪽에 큰수는 오른쪽에 둔다.
그리고 이러한 정렬을 재귀로 계속 돌리면서 피벗을 뽑고, 그 기준으로 부분리스트를 나누어 정렬하는 것을 반복한다.
퀵정렬에 대한 추가 설명(참고 블로그)
그렇다면 실제 알고리즘을 푸는 과정은 어떻게 될까?
- 피벗을 선택한다.(랜덤하게지만, 보통 가장 맨 처음 수 혹은 맨 끝수를 피벗으로 두고 시작.)
- 피벗을 제외한 요소들을 순회하는데, 왼쪽부터 점차 인덱스가 커지며 수를 점검하면서,
동시에 배열 끝에서부터 역으로 수를 점검한다. - 왼쪽에서 점차 커지며 점검하는 경우에, 피벗보다 작으면 그대로 두고/ 반대로 오른쪽에서 역으로 점검하는 경우에, 피벗보다 크면 그대로 둔다.
- 이 때 왼쪽의 수가 피벗보다 크고, 오른쪽 수가 피벗보다 작은 경우가 나오면 그 두수의 자리를 교체해준다.
- 그렇게 양쪽에서 점검해주다가, 같은 인덱스로 만난 경우에, 그 인덱스의 수와 피벗의 위치를 바꿔준다. 이때 그 인덱스 수가 피벗보다 작은경우에 피벗은 그 수의 오른쪽에, 큰 경우에는 왼쪽에 위치한다.
const partition = function(array, left, right, pivotIndex) { // 정렬하는 부분
var temp;
var pivot = array[pivotIndex];
while (left <= right) {
// 왼쪽 인덱스와 오른쪽 인덱스가 같을때까지, 즉 만날때까지 서로 순회를 돈다
while (array[left] < pivot)
//왼쪽에 위치한 수가 피벗보다 작은 경우에만 왼쪽 인덱스를 하나씩 증가하며 순회
left++;
while (array[right] > pivot)
//오른쪽에 위치한 수가 피벗보다 큰 경우에만 오른쪽 인덱스를 하나씩 감소하며 순회
right--;
if (left <= right) {
// 왼쪽이 기준보다 크고, 오른쪽이 기준보다 작으면
//위의 while문에서 벗어날 것이다. 이때 여전히 왼쪽 인덱스가 오른쪽 인덱스보다 작을때,
//왼쪽이 기분보다 크고, 오른쪽이 작다는 의미가 되므로 자리를 바꿔준다.
temp = array[left];
array[left] = array[right];
array[right] = temp; // 서로 바꿔줍니다.
left++;
right--;
}
}
temp = array[left];
array[left] = array[pivotIndex];
array[pivotIndex] = temp;
// 마지막으로 기준과 만난 수를 바꿔줍니다. 기준의 위치는 이제 left입니다.
return left;
};
const quickSort = function(array, left, right) { // 재귀하는 부분
if (!left) left = 0;
//처음시작하는 경우 왼쪽 오른쪽으로 나누지 않았으니, 임의로 왼쪽인덱스는 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;
};퀵정렬의 경우, 위의 코드를 보면 알다시피, 반복문이 두번 돌아간다.
따라서 최악의 경우, 시간 복잡도는 n^2이나, 빠르게 돌면 NlogN의 시간복잡도를 가진다.
