정렬공부하기 전,, 내가 푼 정체모를 식
빈배열에다가 젤 작은수부터 차곡차곡 쌓는형태로, 재귀를 이용해 풀었는데 이것은 무슨 정렬일꽈 , , 걍 숙영정렬 만들면 안됨? ㅋㅎㅋㅎ
let result = []
let recursive = (num) => {
if(num === 0){
return result;
}
let minNum = Math.min(...arr);
result.push(minNum);
arr.splice(arr.indexOf(minNum),1)
recursive(num-1)
}
recursive(arr.length)여튼 뻘소리 집어치우고 정렬의 제일 기본인 선택 / 버블 / 삽입 정렬에대해 리뷰해보겠당.
🧩 선택정렬
선택정렬 (select sort) 방식이란 맨처음 인덱스를 기준으로, 그 다음 인덱스들 중에서 제일 작은 수와 비교하여 swap 하는 형식이다.
예를들어,
[13,5,11,7,23,15] 라는 배열이 있다고 치자.
맨처음 비교대상은 13(i)과 5(j)이후의 나머지 배열들과의 비교인데,
5 이후의 배열들 중 제일 작은수는 5이다. 그 5와 맨처음배열 13을 비교했을떄 13보다 5가 더 작으므로 서로 swap 을 해준다.
[5,13,11,7,23,15]
그 다음, i 번째는 13이 되고 j번째수들은 11이하의 수가 된다.
11이하의 수들 중에서 가장 작은 수는 7이 되며, i인 13과 비교했을때 더 작으므로 swap 해준다.
[5,7,11,13,23,15]
그 다음, i번째인 11과 13 이후의 제일 작은수와 비교해준다.
여기서 13이 제일 작은 수이므로 11(i)번째와 비교했을때 13이 더 크니까 내비둔다.
그리고 13번째는 i 번째가 되고, 23(j) 이후의 수 중 15가 제일 작으니까 i번째인 13과 15를 비교했을때 13 이 더 작으므로 내비둔다.
마지막으로 23이 i 번째가 되고, 달랑 하나남은 15와 비교했을때 15가 더 작으므로 서로 swap 해준다.
[5,7,11,13,15,23]
선택정렬의 원리는 이러하다.
그럼 이것을 코드로 작성해보도록 하겠다.
선택정렬 풀이
//arr = [13,5,11,7,23,15]
for(let i = 0; i<arr.length; i++){
let idx = i;
for(let j = i+1; j<arr.length; j++){
if(arr[idx] > arr[j]){
idx = j; //0=>1
}
[arr[i],arr[idx]] = [arr[idx],arr[i]]
}
}
//[5, 7, 11, 13, 15, 23]🧩 버블 정렬
버블정렬의 원리는 선택정렬과 매우 흡사하다.
다만, 선택정렬은 맨 첫번째 수와 그 이후의 수들 중 제일 작은수 와 비교해서 앞에서부터 채워 나갔다면,
버블정렬은 i번째와 바로 그 다음인 i+1 번째와 비교해서 swap 하는 방식이다.
예를들어
[13,5,11,7,23,15] 라는 수를 버블정렬 해본다면
[13,5,11,7,23,15]
13과 5를 비교했을때 13이 더 크므로 서로 swap 한다.
[5,13,11,7,23,15]
13과 11을 비교했을때 13이 더 크므로 서로 swap 한다.
[5,11,13,7,23,15]
13과 7을 비교했을때 13이 더 크므로 서로 swap 한다.
...
이런식으로 끝까지 비교하면
[5,11,7,13,15,23]
제일 큰 수인 23이 맨 뒤로 온것을 볼 수 있다.
다시 처음으로 돌아가서, 맨뒤숫자를 제외한 나머지를 또 비교, 반복하는것이 버블정렬의 원리이다.
이런식으로 계속 비교를 하다보면 상당히 많은 시간이 걸려 실무에선 거의 쓰지않는 방식이지만 종종 코딩테스트에 나온다고 하니 익혀보도록 한다.
버블정렬 풀이
for(let i= 0; i<arr.length-1;i++){
for(let j= 0; j<arr.length-i-1;j++){
if(arr[j] > arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]];
}
}
}arr.length-1 을 한 이유는 어차피 j번째와 j+1 번째를 비교해야 하기 때문이다.
한번 j번째를 돌았을때 이미 맨 마지막에는 제일 큰 수가 들어가 있기 떄문에 비교할 필요가 없어져서 arr.length-i번째 -1 을 한다.
선택정렬에서 j= i+1 한것과 반대라고 생각하면 된다.
그렇게 한바퀴 다돌고 처음부터 맨마지막에서 i만큼 뺸 배열인덱스까지 다시 구하는것을 반복하는 것이다.
🧩 삽입정렬
삽입정렬의 시작은 첫번째 인덱스부터 시작한다.
첫번째 인덱스와 바로앞의 수를 비교하여 서로 위치를 swap 하는 방식이다.
즉, 바로앞의 인덱스와 비교하는 버블정렬과 반대로 바로 이전의 인덱스와 비교하는 방식이다.
[11,7,5,6,10,9] 를 예로 들자면,
첫번째 인덱스인 7부터 시작해야한다.
그래야 그 전 요소와 비교를 할 수 있기 때문!!
[7,11,5,6,10,9]
7과 11을 비교해서 swap!
[7,5,11,6,10,9]
그 다음 인덱스로 넘어가서 5와 11을 비교한 다음 swap!
... 이렇게 쭉쭉 끝까지 넘어가서 반복해주면 된다.
삽입정렬 풀이
for(let i = 1; i<arr.length; i++){
for(let j = 1; j<arr.length; j++){
if(arr[j-1] > arr[j]){
[arr[j-1],arr[j]] = [arr[j],arr[j-1]]
}
}
}
return arr;
이것보다 더 정확한 식으로, (내가푼거 아님, 참고한거임) 인자에 콜백함수를 받아 작성하는 법이 있는데 이 방식이 좀 더 정확도가 높은것 같다.
내코드는 테스트케이스 돌려봤을때 advanced 부분 하나가 통과가 안됨^^
const insertionSort = function (arr, callback = (n) => n ) {
let sorted = [arr[0]];
for (let i = 1; i < arr.length; i++) {
if (callback(arr[i]) >= callback(sorted[i - 1])) {
sorted.push(arr[i]);
} else {
for (let j = 0; j < i; j++) {
if (callback(arr[i]) <= callback(sorted[j])) {
const left = sorted.slice(0, j);
const right = sorted.slice(j);
sorted = left.concat(arr[i], right);
break;
}
}
}
}
return sorted;
}뭐이리 복잡하노 ,, ㅠ-ㅠ
선택/버블/삽입정렬은 평균 또는 최악의 경우에 n^2 의 시간복잡도를 가진다. 하지만 그중에서 삽입정렬은 최적의 상태에서 n 의 시간복잡도를 가지고 있어 선택/버블보다 약간 나은정도? 라고 할 수 있다.
실제로 더 나은 시간복잡도를 가진 정렬방법들이 있기 때문에 실제로 많이 쓰이는 방법은 아니다.
