퀵정렬 알고리즘 구현(+ 정렬종류, 자바스크립트)

 

 

21.01.08(+21.01.25)(+21.01.27)

 

먼저 정렬 방식을 택해야 한다. 이번 기회에 정렬의 종류를 정리하려 한다.

selection, buble, insertion, quick, heap, merge, etc.

위에 언급된 정렬 중 풀이는 quick sort를 이용해 풀 것이다.

selection : 가장 작은 수를 이용해 정렬한다.

buble : 자신의 좌측 값이 자신보다 크면 교환하여 정렬한다. (큰 수부터 정렬되는 것이 특징)

insertion : 자신보다 더 작은 수를 찾을 때 까지 왼쪽으로 이동 후 작은 수를 찾으면 set된다.

quick : 피벗 값을 기준으로 작은수와 큰수를 나눈다. 피벗은 중간값으로 정한다. 만약 배열이 이미 정렬된 값들이고, 값을 첫번째 또는 마지막 값으로 정한다면, 시간복잡도가 O^2n이 되기 때문이다. 재귀함수를 통해 구현된다.

heap : 우선순위 큐를 이용한 정렬이다. 동일 값에 대한 기준이 따로 있지 않으면 동일값 처리가 불가능하다.

merge : 1~2개가 될 때 까지 분할한다. 다시 병합할 때는 정렬 후 병합한다.

 

selection sort와 quick sort를 제외하고는 모두 안정성 있는 알고리즘이다. 

 

이 문제를 자바스크립트를 이용해서 해결하려 한다.

만약 몇 개의 정수가 입력되는지 첫 번쨰 줄에 주어지지 않았다면 ArrayList를 이용해 동적 배열을 사용했을 것이다.(c언어는 malloc사용) 동적배열에 대해서는 따로 정리할 것이다.

물론 파이썬이라면 고민하지 않아도 append함수로 구현이 가능하다.

 

----------------------자바스크립트로 구현---------------------------

자바스크립트로 구현하는 것은 두 가지 방법이 있다.

left와 right배열을 따로 만들어 재귀함수를 이용해 quicksort를 하는 것.

left와 right를 각각 분할되는 배열의 크기를 알기 위한 인덱스 값으로 지정하는 것.

 

나는 인자를 list 하나만 받는 quicksort를 구현하고 싶어 첫번째 방법을 이용해 구현했다.

두 번째 방법은 list의 left값과 right값을 함께 인자로 받아야 한다.

 

코딩에서 몇 가지 오류와 핵심이 있다.

1. 비교 대상

    나는 Person객체에 age를 random으로 입력받아 저장했다. 그리고 그 Person객체를 10개 만들어

    personList에 저장했다. 그러나 코딩을 하면서 그 사실을 기억하지 못하고 quicksort에서 pivot과

    인자들을 비교할때 list[index].age가 아닌 list[index]를 list[pivot]과 비교했다.

    이 경우 age가 아닌 Person object와의 비교가 되기 때문에 실행오류가 나게 된다.

2. concat 함수의 사용

    나는 list에 직접적으로 concat을 사용하는 것 까지는 생각해냈으나, quicksort의 return값으로

    list를 받아 바로 concat를 사용할 생각을 못했다. 원래의 배열을 다른 두 개의 배열(left, right)

    에 담아야하기 때문에 concat함수가 무조건적으로 필요했지만 list를 concat한 후 재귀함수를 호출하면

    결국 두 번째 방법을 쓰는 것이나 다름없어 애를 먹였다. 인터넷의 도움을 받았지만, 생각지 못한

    것이었기 때문에 사고의 확장에 도움이 되었다.

3. 같은 값 처리

    문제에는 없지만, 개인 과제를 했을 때 놓쳤던 부분이라 기재해놓겠다.

    퀵소트를 실행을 했을 때 부분적으로 성공했다. 실패하는 이유는 동일값 처리를 해주지 않아서였다.

    비교식에 등호를 더해주어 동일값은 right로 가도록하였다.

 

어쨌든 완벽히 내 힘으로 처리한 것은 아니지만 구현에 성공했다.

기존의 c언어와 java에 익숙해져 있어서 자바스크립트로의 유연한 구현이 아직은 잘 되지 않는 것 같다.

마지막으로 코드를 올리며 퀵정렬문제는 여기서 마치도록 하겠다.

 

quicksort 구현 in 동아리 스터디