[자료구조] 퀵정렬(quick sort), 합병정렬(merge sort)

이번에는 js로 퀵 정렬과 합병정렬을 짜보았습니다.

개인적으로 C로 짰을때는 배열의 인덱스라든지 배열의 크기라든지 구현하는데 불편했었는데, js로는 고민없이 생각대로 짜는게 쉬웠습니다. (맞습니다. 저 배열의 인덱스 그런게 참 복잡해서 잘 못하고 싫어합니다.)

우선 합병 정렬은 배열을 계속해서 두 그룹으로 분할하고, 분할이 완료되면 두 그룹을 합칠 때 순서대로 합치는 방식 입니다.

코드를 보면,

조금은 복잡하게 느껴질 수도 있겠네요.  두 함수가 있습니다. 하나는 하나의 배열을 두 그룹으로 분할하는 함수고,

또 하나는 두 배열을 정렬된 하나의 배열로 만드는 함수 입니다. 

두 그룹으로 나눌때, 짝수라면 정확히 반반 나뉘겠지만, 홀수 일 때는 다른 크기의 그룹으로 나뉩니다. 그 처리를 위해 Math의 반올림 함수를 사용했습니다.

합병할 때는 지금 보니 조금 복잡하지만,, 두 개의 그룹에서 하나씩 꺼내서 비교하여 작은 값을 먼저 넣고 한쪽 배열을 모두 넣었다면, 나머지 배열의 값들을 모두 집어 넣습니다.

이 합병 정렬을 재귀호출을 하기 때문에 콜스택이 깊어지는 경향이 있습니다. 그리고 생각하기도 bubble이나, select 정렬에 비해 조금 복잡합니다.

다음 살펴볼 정렬을 퀵 정렬 입니다.

코드를 보면,

합병 정렬과 유사하게 피벗을 기준으로 두 개의 그룹으로 나누는 partitionate와, 두 그룹과 피벗 값을 하나로 합치는 mege 함수가 있습니다.

코드가 합병 정렬보다 더 깔끔하게 짜여 진 것 같습니다... 이해는 쉽게 할 수 있을 것 같아서... 

for ... of 는 es6 문법으로  배열의 아이템을 도는 문법입니다.

다음 번엔 계수정렬(counting sort)로 찾아뵙겠습니다.