[TIL 18][Data Structure] Sort - 2
10615 단어 TILdata structureTIL
오늘은 병합정렬과 퀵정렬에 대해서 공부해보았다
유형
1. 병합정렬
- 하나의 배열을 두 개의 같은 크기로 나눈다음, 두 개의 정렬된것을 합쳐서 전체가 정렬된 모습으로 나타나는 방법
- 병합정렬은 분할, 정복, 결합의 단계가 있다.
- 분할: 대상이 되는 배열을 같은 크기의 2개의 배열로 나눈다.
- 정복: 나뉜 배열을 정렬한다. 나뉜 배열의 크기가 너무 크면 다시 분할한다.
- 결합: 정렬이 완료 된 배열들을 하나의 배열로 합친다.
병합정렬 과정
- 배열을 같은 크기로 계속 분할
- 2개의 리스트씩 서로 비교 후 정렬 후 병합
- 역순으로 합치면서 나뉜 리스트끼리 정렬 후 병합
- 최종적으로 2개의 리스트만 남으면 서로 정렬 후 병합
- 분할: 대상이 되는 배열을 같은 크기의 2개의 배열로 나눈다.
- 정복: 나뉜 배열을 정렬한다. 나뉜 배열의 크기가 너무 크면 다시 분할한다.
- 결합: 정렬이 완료 된 배열들을 하나의 배열로 합친다.
위 그림의 정렬 과정
- 분할 분할 분할~~
- n, n+1(n=0, 2, 4, 6)이 서로 비교하여 정렬 후 두개의 값을 가진 하나의 배열로 각각 병합한다.
- 다시 n, n+1(n=0, 2)이 서로 비교하여 정렬 후 네개의 값을 가진 하나의 배열로 각각 병합한다.
- 네개의 값을 가진 각각의 배열이 서로 값을 비교하여 정렬 후 병합한다.
code
function mergedSort(arr){
let length = arr.length;
let result = [];
if (length <=1){
return arr;
}
let middleNum = parseInt(length/2);
let groupOne = mergedSort(arr.slice(0, middleNum));
let groupTwo = mergedSort(arr.slice(middleNum, ));
while(groupOne.length !== 0 && groupTwo.length !== 0){
if (groupOne[0] < groupTwo[0]) {
result.push(groupOne.shift());
} else {
result.push(groupTwo.shift())'
}
}
while(groupOne.length !== 0){
result.push(groupOne.shift());
}
while(groupTwo.length !== 0){
result.push(groupTwo.shift());
}
return result;
}
2. 퀵정렬
- 퀵 정렬은 피벗이라는것이 있다. 배열안에 있는 값 하나를 선택해서 기준점으로 잡는것이다.
퀵정렬 과정
- 피벗을 하나 선택한다.
- 피벗보다 큰 값들은 오른쪽, 작은 값들은 왼쪽으로 옮긴다.
- 피벗을 제외한 왼쪽과 오른쪽 배열들을 각각 정렬한다.
- 배열의 크기가 0이나 1이 될때까지 반복한다.
code
function quickSort(arr) {
let length = arr.length;
if (length <= 1) {
return arr;
}
let pivot = [arr.shift()];
let groupOne = [];
let groupTwo = [];
for (const i in arr) {
if (arr[i] < pivot) {
groupOne.push(arr[i]);
} else {
groupTwo.push(arr[i])
}
}
return quickSort(groupOne).concat(pivot, quickSort(groupTwo))
}
Author And Source
이 문제에 관하여([TIL 18][Data Structure] Sort - 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@devpark_0x1c/TIL-18Data-Structure-Sort-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)