정렬이란 나열된 정보들을 어떠한 규칙에 따라 정리해서 나열하는것을 정렬이라고 합니다.
기본적으로 쉬운 규칙은 오름차순과 내림차순에 의한 정렬입니다.
저는 여기서 오름차순을 규칙으로하는 6가지 정렬의 원리를 이해하고 자바스크립트로 구현해보려합니다.
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;
}
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;
}
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;
}
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 [] [] [] [] [] [] [] [] []
// */
분할 정렬 알고리즘으로 매우 빠른 수행속도를 정렬합니다.
퀵 정렬은 배열 내의 원소중 무작위로 하나를 골라 기준을 삼은뒤 기준보다 큰집합과 작은 집합으로 나눕니다.
이후 각각의 집합에서 또 무작위로 원소를 골라 정렬하는 작업을 반복합니다.
무작위로 고른 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)은 배열의 가운데에 있는 값을 선택하여 정렬했습니다.
큰값과 작은값들을 다시 배열로 모아 그 배열을 재귀함수로 호출하는 방식을 사용하였습니다.
퀵정렬의 장점
단점
- 최악의 경우 pivot이 불균등하게 분할될경우 수행시간이 길어질 위험이 있습니다.
- 최악의 경우에는 n^2까지도 나올수 있습니다.
낮은 자리수부터 정렬해 나가는 방식으로 자리수가 고정되어있으니 안정성이 있습니다.
위의 방법대로 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/>";
}
결과는!!
우려했던것과 다르게 잘나왔습니다.
혹시 궁금하신거나 틀렸다 이런점이 있다면 댓글로 남겨주세요.