정렬 알고리즘

IT 공부/알고리즘, 디자인패턴

정렬 알고리즘

woohot 2023. 4. 10. 17:45

처음 알고리즘을 배울때 배웠던 내용이 정렬이었다.

정렬 종류도 많고 헛갈리 때가 있어 정리 하려한다.

1. 삽입 정렬 , 시간 : O(n^2) , 공간 : O(n)

삽입 정렬이란?

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

function insertSort(list){
let key,j ;
for(const i in list){
key = list[i];
j = i-1;
while( j >= 0 && key < list[j] ){
swap(list,j,j+1);
j--;
}
list[j+1] = key;
}
return list;
}

function swap(list,a,b){
let temp = list[a];
list[a] = list[b];
list[b] = temp;
}

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

삽입 정렬 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬

ko.wikipedia.org

2. 선택 정렬 , 시간 : O(n^2) , 공간 : O(n)

선택 정렬이란?

제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

주어진 리스트 중에 최소값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

let list = [4,2,7,9,12,3];

function swap(list,a,b){
let temp = list[a];
list[a] = list[b];
list[b] = temp;
}

const minSelectionSort = (list) => { // 최소 선택 정렬 , 오름차순
console.log('minSelectionSort start');
for(let i =0 ; i< list.length; i++){
let tmp = i;
for(let j=i+1; j<list.length ; j++){
console.log(list[i],list[j])
if(list[tmp] >= list[j]) {
tmp=j
}
}
swap(list, i,tmp)
}
return list;
}

const maxSelectionSort = (list) => { //최대 선택 정렬 , 내림차순
console.log('minSelectionSort start')
for(let i =list.length -1 ; i>=0 ; i--){
let tmp = i;
for(let j=i-1; j>=0 ; j--){
console.log(list[i],list[j])
if(list[tmp] < list[j]) {
tmp=j
}
}
swap(list, i,tmp)
}
return list;
}

console.log('min : ',minSelectionSort(list));
console.log('max : ',maxSelectionSort(list));

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

선택 정렬 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위

ko.wikipedia.org

3. 버블 정렬 , 시간 : O(n^2) , 공간 : O(n)

버블 정렬이란?

정렬 알고리즘 중 하나이다. 시간 복잡도가 O(n^2)

로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.

function swap(list,a,b){
let temp = list[a];
list[a] = list[b];
list[b] = temp;
}

const bubbleSort = (list) => {
for(let i = 0; i < list.length ; i++){
for(let j=1; j<list.length ; j++){
if(list[j-1] > list[j]){
swap(list, j,j-1)
}
}
}
return list;
}

console.log('bubble' , bubbleSort(list));

https://ko.wikipedia.org/wiki/%EB%B2%84%EB%B8%94_%EC%A0%95%EB%A0%AC

버블 정렬 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 버블 정렬 또는 거품 정렬(-整列, 영어: bubble sort 버블 소트[*], sinking sort 싱킹 소트[*])은 정렬 알고리즘 중 하나이다. 시간 복잡도가 O ( n 2 ) {\displaystyle O(n^{2})}

ko.wikipedia.org

4. 합병 정렬 , 시간 : O(nlog n) , 공간 : O(2n)

병합 정렬(영어: merge sort 머지 소트[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.

구현 방법에는

톱 다운 구현, 바텀 업 구현 ,외부 병합 정렬 있다.

const merge = (left, right) => {
const sortedArr = [];
while (left.length && right.length) { //left[0]이 더작을 경우 같을때는 누가 먼저 들어가도 상관X
if (left[0] <= right[0]) {
sortedArr.push(left.shift());
} else {
sortedArr.push(right.shift());
}
}
//left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
//비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여준다.
return [...sortedArr, ...left, ...right];
}

const mergeSort = (arr) => {
if (arr.length === 1) return arr;
const boundary = Math.ceil(arr.length / 2); //slice로 해주기 때문에 원본 arr은 손상 없다.
const left = arr.slice(0, boundary);
const right = arr.slice(boundary);
//요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
//차근차근 merge(정렬해서 합치기)해주면 된다.
return merge(mergeSort(left), mergeSort(right));
}

const arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);
console.log(arr); //[7, 4, 3, 2, 1, 6, 5]
console.log(sortedArray); //[1, 2, 3, 4,5, 6, 7]

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며,

ko.wikipedia.org

5. 퀵 정렬 , 시간 : O(nlog n) 최악의경우 , O(n^2) , 공간 :

다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 분할 정복 전략을 사용한다

구현 방법에는 in place , !(not) in place 방법이 있는데 , in place 방법이 메모리 사용량이 적다.

중복되는 데이터는 순차적으로 pivot에 넣어 , 정렬 전 중복 데이터의 순서가 바뀌지 않는 stable한 정렬을 구현

Not In Place

const quickSort = (array) => {
if(array.length < 2){
return array;
}
const pivot = [array[0]];
const left = [];
const right = []; // console.log('pivot : ' ,pivot );
for(let i = 1; i< array.length ; i++){
if( array[i] < pivot ){
left.push(array[i]);
}else if(array[i] > pivot){
right.push(array[i]);
}else{
pivot.push(array[i]);
}
}
console.log(`left : ${left} , pivot : ${pivot} , right : ${right}`);
return quickSort(left).concat(pivot, quickSort(right));
}

메모리 공간이 절약된다 .왼쪽과 오른쪽 값을 교환하는 과정에서 중복값의 위치가 바뀔 수 있으므로 unstable한 정렬 방법

const inPlaceQuick = (array, left=0, right=array.length -1 ) => {
if(left >= right){
return ;
}
const divide = (array , left, right, pivot) => {
console.log(`array: ${array}, left: ${array[left]}, pivot: ${pivot}, right: ${array[right]}`);
while(left <= right){
while(array[left] < pivot){
left++;
}
while(array[right] > pivot){
right--;
}
if(left <= right){
let swap = array[left];
array[left] = array[right];
array[right] = swap;
left++;
right--;
}
}
return left;
}
const mid = Math.floor((left+right)/2);
const pivot = array[mid];
const partition = divide(array, left, right, pivot);
inPlaceQuick(array , left , partition -1 );
inPlaceQuick(array , partition , right );
return array;
}

const sorted = inPlaceQuick([5,3,7,1,9]);
console.log(sorted);

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데

ko.wikipedia.org

힙 정렬 시간 : O(n^2) 최악의경우 , O(n^2) , 공간 : O(1)

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다.

const heapSort = (arr) => {
let tmp;
for(let i = arr.length-1 ; i>= 0 ; i--){
arr = heapMaker(arr,i);
if(arr[0] > arr[i]){
tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
}
}
return arr;
}

const heapMaker = (arr, lastidx) => {
let idx = parseInt(lastidx/2)-1;
while(idx >= 0 ){
const left = arr[idx*2+1];
const right = arr[idx*2+2];
if( left >= right && arr[idx] < left){
tmp = arr[idx];
arr[idx*2 + 1] = tmp;
arr[idx] = left;
}else if( right > left && arr[idx] < right ){
tmp = arr[idx];
arr[idx*2 +2] = tmp;
arr[idx] = right;
}
idx--;
}
return arr;
}