Algorithm. 퀵정렬

Algorithm 퀵(Quick)정렬

퀵정렬입니다. 퀵정렬은 상당히 빠른 속도를 자랑합니다. 합병정렬과 같이 재귀함수를 통한 분할정복 기법이 사용됩니다.

퀵정렬은 먼저 기준이 되는 수를 정합니다.

기본적으로 배열의 가장 끝 수를 기준으로 합니다.(기준 수를 선택하는 것은 크게 중요하지 않습니다.)

[4,1,7,6,3,2,8,5]

이제 이 기준이되는 수와 비교하여 

기준 숫자(5)보다 작은 수들은 왼쪽으로, 기준숫자(5)보다 큰 수는 오른쪽으로 모을겁니다.

기준이 되는 자리를 제외하고 진행합니다.

• 기준 숫자보다 작은 수 찾기

   배열의 첫째 자리부터 기준과 비교합니다.

    [4,1,7,6,3,2,8,5]

   기준보다 작은 수는 그대로 두고,

   기준보다 큰 수를 찾을 때까지 배열의 위치를 증가시킵니다.

    [4,1,7,6,3,2,8,5]

   배열의 세번째 자리에서 기준보다 큰 수를 찾았습니다.

    [4,1,7,6,3,2,8,5]

• 기준 숫자보다 큰 수 찾기

   배열의 마지막 자리부터 기준과 비교합니다. (기준 숫자 자리 제외!)

    [4,1,7,6,3,2,8,5]

   기준보다 큰 수는 그대로 두고,

   기준보다 작은 수를 찾을 때까지 배열의 위치를 감소시킵니다.

    [4,1,7,6,3,2,8,5]

• 찾은 두 숫자 교환하기

   왼편에 기준보다 큰 숫자(7)와 오른편에 기준보다 작은 숫자(2)의 위치를 교환합니다.

    [4,1,7,6,3,2,8,5]   →    [4,1,2,6,3,7,8,5]

왼편과 오른편에 또 다시 해당 되는 숫자가 있다면 교환합니다.

    [4,1,7,6,3,2,8,5]   →    [4,1,2,3,6,7,8,5]

왼편의 배열 위치가 오른편의 배열 위치를 지나면 왼편 배열 위치의 숫자(5번째 위치한 숫자6)를 기준 숫자와 교환합니다.

 [4,1,2,3,5,7,8,6]

재귀 함수를 사용하여 기준보다 작았던 왼편의 배열을 다시 앞의 순서와 같이 실행합니다. 기준보다 큰 오른편의 배열도 똑같이 진행합니다.

※ 참조 사이트의 함수를 그대로 사용했습니다.

   다만 이해하기 어려웠던 부분에 새로운 설명을 적어 넣었습니다.

   기준이 되는 수의 위치(pivotIndex), 왼편과 오른편을 나눈 이후에 다시 시준이 되는 pivotIndex를 이해하기가 까다로웠습니다.

   이해가 안되는 부분에 로그를 찍어 보며 인덱스의 위치가 어떻게 변화하는지 배열은 어떻게 이동되는지 본다면 한결 이해하기 쉬울 것 같습니다.

참고사이트: www.zerocho.com/category/Algorithm