정렬이란 나열된 정보들을 어떠한 규칙에 따라 정리해서 나열하는것을 정렬이라고 합니다.
기본적으로 쉬운 규칙은 오름차순과 내림차순에 의한 정렬입니다.
저는 여기서 오름차순을 규칙으로하는 6가지 정렬의 원리를 이해하고 자바스크립트로 구현해보려합니다.
1. 선택정렬
선택정렬이란?
- 선택정렬은 최소값 또는 최대값을 찾아 제일 앞 또는 제일 뒤로 보내주어 하나씩 정렬하는 방식입니다.
- 입력된 배열의 자리변환만 이루어지기 때문에 제자리 정렬 알고리즘에 해당됩니다.
- n번의 최소값을 찾는 로직이 있어야 하고, 최소값을 찾는 로직은 다시 모든 것을 검색해야되므로 약 n번의 검색이 있어야합니다. 따라서 시간복잡도는 n^2가 됩니다.
위의 사진은 선택정렬을 보기쉽게 그려놓은 것입니다. 자바스크립트에서의 선택정렬 코드
const selectSort=(array)=>{ let arr = [].concat(array); for(let i = 0 ; i < arr.length ; i++){ let min = arr[i]; let minIdx = i; for(let j = i+1; j<arr.length ; j++){ if(arr[j]<min){ min = arr[j]; minIdx = j; } } if(i!==minIdx){ arr[minIdx] = arr[i]; arr[i] = min; } } return arr; }
2. 삽입정렬
삽입정렬이란?
- 사람이 일반적으로 정렬하는 방법이랑 가장 유사한 방법
- 하나씩 추가된다는 가정하에 앞에 주어진 것들에 비교하여 자리를 결정하는 방법
삽입정렬의 예제
자바스크립트에서의 삽입정렬 코드
const insertSort =(array)=>{
let arr = [];
let tempArr = [];
for(let i = 0 ; i < array.length ; i++){
if(arr.length===0 || arr[arr.length-1]<array[i]){
arr.push(array[i]);
}else{
while(arr[arr.length-1]>array[i]){
tempArr.push(arr[arr.length-1]);
arr.pop();
}
arr.push(array[i]);
while(tempArr.length!==0){
arr.push(tempArr[tempArr.length-1]);
tempArr.pop();
}
}
}
return arr;
}- Arr 을 스택으로 이용하여 pop과 push를 통해서 새로 들어오는 숫자의 자리를 결정
- 빠져 나온 숫자를 저장하기위해 tempArr을 이용
삽입정렬의 장단점
- 장점
- 하나씩 정렬되기때문에 가장 안정적인 정렬방법입니다.
- 선택정렬보다는 시간복잡도가 살짝 좋습니다.
- 단점
- 하노이의 탑처럼 전부다 빼고 다시 넣어야되는경우가 생길수 있음.
- 최소횟수는 이미 정렬되었으면 n번이고 역으로 정렬이 되었다면 n^2까지 올라갑니다.
3. 버블정렬
버블정렬이란?
- 앞과 뒤를 비교하여 두개의 크기를 비교하여 가장 큰값 or 마지막 값을 먼저 정렬하는 방법
버블정렬의 예제
자바스크립트에서의 버블정렬 코드
const bubbleSort = (array) =>{
let arr = [].concat(array);
for(let count = 0 ; count < arr.length ; count++){
for(let i = 1 ; i < arr.length-count ; i++){
let temp;
if(arr[i-1]>arr[i]){
temp = arr[i-1];
arr[i-1] = arr[i];
arr[i] = temp;
}
}
}
return arr;
}버블정렬의 특징
- 장점
- 버블정렬은 최악과 최상이 모두 횟수가 동일합니다.
- 구현 방법이 쉽습니다
- 단점
- 버블정렬은 가장 시간이 오래걸리는 정렬입니다.
- 입력경우가 이미 정렬이 되어있는경우에도 시간이 똑같이 필요합니다.
4. 병합정렬(merge sort)
병합정렬이란
- 폰 노이만이 제안한 방법으로 안정 절렬에 속하며 분할정복 알고리즘의 하나입니다.
- 각각 작은 2개의 문제 여기서는 제일 작은 단위로 바꾸어 문제를 해결하고 그다음 난이도 의 문제순서로 진행되는 방법입니다.
위의 사진 형태로 진행되는 방법으로 분할 정복 병합 과정이 이루어집니다.자바스크립트에서의 병합정렬
const mergeSort = (array) =>{ let arr = new Array(array.length); for(let i = 0 ; i < array.length ; i++){// initialize arr[i] = [].concat([array[i]]); } const log2 = Math.ceil(Math.log2(array.length)); for (let i = 0 ; i < Math.ceil(log2) ; i++){ const pow = Math.pow(2, i) for(let n = 0; n<Math.ceil(array.length/(2*pow));n++){ let firstArr = arr[pow*(2*n)]; let secondArr = arr[pow*(2*n+1)]; let tempArr = []; console.log(pow*(2*n),firstArr); console.log(pow*(2*n+1),secondArr); while(firstArr.length!==0||(secondArr !== undefined &&secondArr.length!==0)){ if(secondArr === undefined || secondArr.length===0 || secondArr[0]>firstArr[0]){ tempArr.push(firstArr[0]); firstArr.shift(); }else{ tempArr.push(secondArr[0]); secondArr.shift(); } console.log(firstArr,secondArr,tempArr); } console.log(tempArr) arr[pow*(2*n)] = [].concat(tempArr); arr[pow*(2*n+1)]= []; } } return arr[0]; }
// /*
// 2406851739
// 2 4 0 6 8 5 1 7 3 9
// 24 [] 06 [] 58 [] 17 [] 39 []
// 0246 [] [] [] 1578 [] [] [] 39 []
// 01245678 [] [] [] [] [] [] [] 39 []
// 0123456789 [] [] [] [] [] [] [] [] []
// */
- 위의 코드에서 병합정렬은 위의 순서로 이루어집니다.
- 이미 합쳐져 length가 0인배열은 열어보지 않습니다.(분기문 처리대신 pow메소드로 대체)
- undefined된 배열과도 비교를 한다는게 저 코드의 단점입니다.
병합정렬의 특징
- 장점
- 시간 복잡도가 log2n으로 낮은 축에 속합니다.
- 단점
- 구현이 복잡하고 재귀함수를 사용하는 방법이 일반적입니다.
6. 퀵정렬
퀵정렬이란?
-
분할 정렬 알고리즘으로 매우 빠른 수행속도를 정렬합니다.
-
퀵 정렬은 배열 내의 원소중 무작위로 하나를 골라 기준을 삼은뒤 기준보다 큰집합과 작은 집합으로 나눕니다.
-
이후 각각의 집합에서 또 무작위로 원소를 골라 정렬하는 작업을 반복합니다.
-
무작위로 고른 pivot이라는 원소가 한쪽에 쏠려있을 경우가 많아 비균등하게 분할하는 방법입니다.
퀵정렬의 자바스크립트 코드
const quickSort = (array) =>{
let arr = [].concat(array);
const compare = (array) =>{
let arr = [].concat(array);
const midNum = arr[Math.floor(arr.length/2)-1];
if(arr.length>=2){
let big,small;
let tempbig = [];
let tempsmall = [];
for(let i = 0 ; i < arr.length; i++){
if(i===Math.floor(arr.length/2)-1){
continue;
}else if(arr[i]<=midNum){
tempsmall.push(arr[i]);
}else{
tempbig.push(arr[i]);
}
}
big = compare(tempbig);
small = compare(tempsmall);
small.push(midNum);
return small.concat(big);
}else{
return arr;
}
}
return compare(arr);
}-
위의 코드에서 랜덤으로 선택한 원소(pivot)은 배열의 가운데에 있는 값을 선택하여 정렬했습니다.
-
큰값과 작은값들을 다시 배열로 모아 그 배열을 재귀함수로 호출하는 방식을 사용하였습니다.
퀵정렬의 특징
-
퀵정렬의 장점
- 시간 복잡도가 nlog2n으로 가장 짧습니다.
-
단점
- 최악의 경우 pivot이 불균등하게 분할될경우 수행시간이 길어질 위험이 있습니다.
- 최악의 경우에는 n^2까지도 나올수 있습니다.기수정렬 (Radix sort)
기수정렬이란?
-
낮은 자리수부터 정렬해 나가는 방식으로 자리수가 고정되어있으니 안정성이 있습니다.
예제
-
위의 방법대로 1의 자리수 부터 자리수를 차근차근 정리해 가는 방법으로 최대 값의 자리수까지 정렬하면 정렬이 되어있는방법입니다.
자바스크립트에서의 기수정렬
const radixSort= (array) =>{ let arr = [].concat(array); let max; let digitArr = new Array(10); for(let i = 0; i < digitArr.length ; i++){// initialize digitArr[i] = []; } for(let i = 0 ; i < arr.length ; i++){ if(i===0 || max < arr[i]){ max = arr[i]; } } let maxLog = Math.log10(max)+1;// 자리수 판별 for (let digit = 1 ; digit <= maxLog ; digit++){ let digit10 = Math.pow(10,digit); let tempArr = []; for(let i = 0 ; i < arr.length ;i++){ if(digit === 1){ digitArr[arr[i]%digit10].push(arr[i]); }else{ tempDigit = Math.floor((arr[i]%digit10)*10/digit10); digitArr[tempDigit].push(arr[i]); } } for(let i = 0 ; i < digitArr.length ; i++){ while(digitArr[i].length!==0){ tempArr.push(digitArr[i][0]); digitArr[i].shift(); } } arr = [].concat(tempArr); } -
log를 이용하여 자리수를 구하는 로직을 추가하여 빠르게 할수있도록 구현
-
계속적으로 digitArr을 0~9까지로 생각하고 push shift하는 방식을 사용
기수 정렬의 특징
-
시간 복잡도는 가장큰 숫자의 자리수X 9 X a 만큼이 됩니다. 수식으로는 9log10 n이 되어 가장 낮은 방법으로 볼수 있습니다.
-
단점은 자리수가 몰려있는경우 n번이상이 될수도 있으니 불안정하게 됩니다.
마지막! 구현
위의 함수들을 html에 구현해봤습니다.
const arr = [0,2,8,1,3,5,9,6,4,7]; let sort =[]; sort.push(insertSort(arr)); sort.push(bubbleSort(arr)); sort.push(mergeSort(arr)); sort.push(heapSort(arr)); sort.push(quickSort(arr)); sort.push(radixSort(arr)); const box = document.querySelector(".box") box.innerHTML = "순서대로 선택, 삽입, 버블 ,머지, 힙, 퀵, 라딕스 정렬<br/>" for(let i = 0 ; i<sort.length ; i++){ box.innerHTML+=sort[i].join(""); box.innerHTML+="<br/>"; }
결과는!!
우려했던것과 다르게 잘나왔습니다.
혹시 궁금하신거나 틀렸다 이런점이 있다면 댓글로 남겨주세요.
Frontend 를 목표로합니다.