웹 취약점 공격 방법인 XSS, CSRF에 대하여 간단하게 알아보기
2021-03-04
자바스크립트로 알아보는 알고리즘 #3 정렬 알고리즘-1
2019-03-03
Explanation
오늘은 정렬 알고리즘에 대해 적어보려고 합니다.
인터넷에 보면 알기 쉽게 만들어 놓은 보기 좋은 움직이는 이미지들이 있는데, 함부로 가져다 쓰면 안될 거 같아서 이미지는 없습니다..
아래 링크의 글에 이미지가 참 이해하기 쉽고 좋은 거 같아요.
https://medium.com/@fiv3star/%EC%A0%95%EB%A0%AC%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-sorting-algorithm-%EC%A0%95%EB%A6%AC-8ca307269dc7
버블 정렬은 가장 쉬운 정렬 알고리즘이라고 해요, 하지만 쉬운 만큼 시간 복잡도가 높아서 실제로는 잘 사용되지 않습니다. 시간 복잡도는 O(n2) 입니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
function bubbleSort(arr) { const len = arr.length; for(let i=0; i<len-1; i++) { for(let j=0; j<len-i-1; j++) { if(arr[j] > arr[j+1]) { const cache = arr[j]; arr[j] = arr[j+1]; arr[j+1] = cache; } } } return arr; } |
선택 정렬은 버블 정렬과 비슷하게 한번씩 전체를 돌며 가장 작은 값을 찾아서 맨 앞의 값과 교환하는 방법인데요. 역시 시간 복잡도가 O(n2)라서 잘 사용되지는 않는다고 합니다. 그래도 버블 정렬의 불필요한 배열의 이동을 줄여서 버블 정렬보다는 빠릅니다.
아래 예제 코드는 배열의 가장 큰 값을 찾아서 마지막에 값과 교환하는 방식으로 구현했어요. 별 차이 없겠죠??
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
function selectionSort(arr) { const len = arr.length; for(let i=0; i<len; i++) { let maxIdx = len-i-1; for(let j=0; j<len-i; j++) { if(arr[j] > arr[maxIdx]) maxIdx = j; } if(maxIdx !== i) { const cache = arr[maxIdx]; arr[maxIdx] = arr[len-i-1]; arr[len-i-1] = cache; } } return arr; } |
산입 정렬은 현재 값을 캐시하고 그 이전값들을 순회하며 대상의 값이 현재 값보다 크다면 한칸씩 배열위 위치를 이동하고 현재값이 위치할 곳에 도착하면 그곳에 위치시킵니다. (글로 적으니 더 어렵게 느껴지네요.. 위 링크의 이미지를 보시는게 좋을 거 같아요.)
삽입 정렬도 역시 두번의 반복문을 돌기 때문에 시간 복잡도는 O(n2)입니다.
하지만 삽입 정렬은 이미 정렬이 되어 있는 상태에서 새로운 값이 추가되어 정렬할 때는 한번만 돌며 위치시켜주면 되기 때문에 그때의 시간 복잡도는 O(n)이 됩니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function insertionSort(arr) { const len = arr.length; for(let i=1; i<len; i++) { const cache = arr[i]; let j; for(j=i-1; j>=0; j--) { if(cache < arr[j]) { arr[j+1] = arr[j]; } else { break; } } arr[j + 1] = cache; } return arr; } |
이번엔 합병 정렬인데, 여기서부턴 좀 복잡해요.. 배열을 반으로 나누고 그리고 또 반으로 나누고 그리고 또 반으로.. 그래서 배열에 요소가 1개가 될때까지 나눕니다. 그리고 그렇게 나누어진 배열을 각각 정렬에 위치시키면서 합치는 구조입니다.(역시.. 글이 더 어렵네요..)
제가 이해를 위해 참고한 링크를 추가합니다.
1. https://hsp1116.tistory.com/33
2. https://www.zerocho.com/category/Algorithm/post/57ee1fc107c0b40015045cb4
3. http://www.daleseo.com/sort-merge/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
function mergeSort(arr) { if (arr.length < 2) return arr; const pivot = Math.floor(arr.length / 2); const left = arr.slice(0, pivot); const right = arr.slice(pivot, arr.length); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { const result = []; while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; }; |
이 코드는 ‘zerocho’님이 블로깅하신 코드에요.(위 참고링크 2번)
재귀를 활용한 것도 그리고 콜 스택도 생각할 수 있는, 정말.. 여러가지로 유익한 코드인거 같아요!
합병 정렬은, 분할 하는 과정에서 n/2, n/4, n/8.. 이렇게 logn만큼 반복하게 되고 O(logn), 합병 과정에서 왼쪽 배열 오른쪽 배열 이렇게 n1과 n2가 합쳐지는 n1 + n2 라서 O(n). 그리고 분할별로 합병하기 때문에 총 시간 복잡도는 O(nlogn)이 됩니다.
이번에는 퀵 정렬에 대해 알아봅니다. 퀵 정렬은 배열의 하나의 값을 정해서 그 값보다 큰값은 오른쪽에, 작은 값은 외쪽에 위치시키고 이를 반복하여 정렬합니다. 일반적으로 많이 사용되는 방법인거 같아요. 예를 들면 v8엔진에서(크롬) 자바스크립트의 .sort() 가 바로 이 퀵 정렬로 구현되어 있답니다. 최악의 경우 시간 복잡도는 O(n2)가 되는대요, 그런데 그럴 확률이 정말 작아서 예외적으로 O(nlogn)으로 이야기 한다고 합니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function quickSort(arr) { const len = arr.length; if(len === 0) return []; let left = []; let right = []; let pivot = arr[0]; for(let i=1; i<len; i++) { if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat(pivot, quickSort(right)); } |
그래도 합병 정렬 보단 심플한 코드죠? pivot 이라는 배열안의 임의값(여기에서 첫번째 값)을 고르고 반복문을 돌아서 해당 값보다 크면 오른쪽 작으면 왼쪽에 위치시키고 그 오른쪽 값과 왼쪽 값을 다시 임의의 값으로 나눠서 위치시키고.. 이렇게 반복한 후 다시 하나의 배열로 합쳐집니다(concat)
위 방법이 아닌 다른 방법도 있는데요, 위 방법은 간단하지만, 재귀할때마다 새로운 배열을 두개씩 만들기 때문에 메모리 사용 측면에서 비효율적인 면이 있어요, 그래서 또 다른 방법으로 아래와 같은 코드도 있답니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
function quickSort(arr) { return sort(arr, 0, arr.length - 1); } function sort(arr, left, right) { if (arr.length > 1) { const index = partition(arr, left, right); if (left < index - 1) sort(arr, left, index - 1); if (index < right) sort(arr, index, right); } return arr; } function partition(arr, left, right) { const pivot = arr[Math.floor((right + left) / 2)]; while (left <= right) { while (arr[left] < pivot) left++; while (arr[right] > pivot) right--; if (left <= right) { swap(arr, left, right); left++; right--; } } return left; } function swap(arr, idx, nIdx) { const cache = arr[idx]; arr[idx] = arr[nIdx]; arr[nIdx] = cache; } |
코드가 좀 길죠… 하지만 한줄씩 따라가며 생각하다보면 어렵지 않게 이해할 수 있어요. 위 sort 함수가 배열의 시작 인덱스와 끝 인덱스를 가지고 시작되면 partition 함수에서 인자로 받은 인덱스의 중간값을 기준으로 자신보다 큰 왼쪽 값과 자신보다 작은 오른쪽 값의 인덱스를 구해서 서로에 위치를 바꿔주고 그게 끝나면 마지막으로 변경한 왼쪽 인덱스를 기준으로 둘로 나누어 다시 sort 함수를 호출하고 이를 반복하여 정렬을 구합니다.
코드를 써놓고 다시 보니까.. 좀 최적화가 덜 된거 같아요. 저 코드는 불필요한 재귀를 하게 되네요. 아래 참고 링크 1번-3번의 방법이 더 좋은 거 같아요.
참고하기 좋은 링크
1. https://terms.naver.com/entry.nhn?docId=3579548&cid=59086&categoryId=59093
2. http://www.daleseo.com/sort-quick/
3. https://www.zerocho.com/category/Algorithm/post/57f72d415141fc5fe4f4ca8b
4. https://brunch.co.kr/@k2u4yt/3#comments
끝
