정렬 알고리즘: 퀵 정렬 (Quicksort) 해설

no_mkd

일.퀵 정렬 알고리즘의 장점, 왜 '퀵' 정렬이라고 부르는가?

Quicksort 는 병합 정렬 알고리즘의 최적화로, 병합 정렬의 장점을 계승하고 동일하게 분할 정복 사상을 적용했습니다.

소위 분할 정복 사상이란 어떤 문제에 대해 '분할하여 정복한다'는 것으로, 분할 정복 사상으로 문제를 해결하려면 두 단계가 필요합니다:

1. 어떻게 '분할'하는가? (어떻게 문제의 규모를 축소하는가)
2. 어떻게 '정복'하는가? (어떻게 하위 문제를 해결하는가)

퀵 정렬의 전신은 병합이지만, 병합에는 무시할 수 없는 단점이 있었기 때문에 퀵 정렬이 탄생했습니다. 병합의 가장 큰 문제는 추가적인 저장 공간이 필요하며, 병합 과정이 불확실하여 각 요소의 시퀀스 내 최종 위치를 예측할 수 없다는 것입니다. 이 점에 대해 퀵 정렬은 새로운 사고방식을 제안했습니다: 더 많은 시간을 '분할'에 사용하고, 더 적은 시간을 '정복'에 사용한다. 이로써 추가적인 저장 공간 문제를 해결하고 알고리즘 효율성을 향상시켰습니다.

퀵 정렬이 '퀵' 정렬이라고 불리는 이유는 평균 시간상 가장 빠르기 때문입니다. 주된 이유는 하드웨어 측면이며, 각 라운드의 퀵 정렬에서는 '피벗'(즉, 경계점으로서의 값) 을 지정해야 하며, 한 라운드에서 관련된 모든 비교는 이 '피벗'과 비교됩니다. 따라서 이 '피벗'을 레지스터에 넣을 수 있으며, 이렇게 하면 효율이 자연스럽게 크게 향상됩니다. 이 외에도 퀵 정렬의 고효율은 분할 정복 사상과도 떼어놓을 수 없습니다.

이.알고리즘 사상

퀵 정렬의 사상에 따르면, 알려진 시퀀스를 정렬하는 데는 다음과 같은 단계가 있습니다:

1. '피벗' 지정

   주의, '지정'이며 명확한 제약 조건이 없습니다. 즉, 이 피벗은 임의의 요소로, 일반적으로 두 가지 피벗을 선택합니다: 현재 시퀀스의 첫 번째 요소, 또는 무작위 선택

   두 방식에는 각각 장단점이 있습니다. 전자는 간단하지만 알고리즘 효율성에 영향을 줄 수 있습니다

   퀵 정렬에서 피벗의 최종 위치가 중간 위치에 가까울수록 효율이 좋습니다. 읽기에는 조금 이상하게 느껴질 수 있지만, 피벗은 값 (구체적인 요소) 이지 글자 그대로의 위치가 아님에 주의하십시오. 피벗이 최종 시퀀스 내 위치가 앞이나 뒤에 있을 경우 알고리즘 효율이 높지 않습니다 ('최악의 경우'와 유사합니다)

   따라서 후자는 어느 정도 최악의 경우 발생 횟수를 줄이지만, 무작위 선택에는 추가적인 시간이 필요합니다

   따라서 구체적인 응용에서는 일반적으로 첫 번째 방식으로 '피벗'을 지정합니다. 즉, 현재 시퀀스의 첫 번째 요소를 직접 '피벗'으로 합니다

2. 한 라운드의 퀵 정렬 수행

   퀵 정렬에서 한 라운드 조작의 최종 목적은 '피벗'을 그것이 가야 할 곳에 두는 것입니다. 예를 들어, 알려진 시퀀스{7, -1, 5, 23, 100, 101}의 경우, 첫 번째 라운드 퀵 정렬의 결과는{_, _, 7, _, _, _}입니다

   첫 번째 요소 (피벗) 이 그것이 가야 할 곳에 갔음을 알 수 있습니다 (최종 결과 시퀀스에서 7 은 바로 중간 위치에 있습니다, 맞죠)

3. 하위 시퀀스에 대해 퀵 정렬 수행

   2 단계는 7 의 최종 위치를 확정했을 뿐만 아니라 원래 시퀀스를 자연스럽게 두 개의 하위 시퀀스{_, _}와{_, _, _}로 분할했습니다. 여기서 '_'로 구체적인 수치를 대체했습니다. 2 단계의 결과가 구체적으로 무엇인지는 실제로 한 라운드의 퀵 정렬을 수행하지 않는 한 알 수 없기 때문입니다. 물론 여기서는 필요하지 않으며, 아래에 구체적인 예에 대한 자세한 설명이 있습니다

   자연스럽게 하위 시퀀스에 대해 동일한 조작을 수행한 후 하위 시퀀스의 하위 시퀀스에 대해 동일한 조작을 수행합니다... 재귀

   모든 하위 시퀀스의 길이가 1 이 될 때 정렬 종료

삼.구체적인 예

현재 시퀀스{9, 0, 8, 10, -5, 2, 13, 7}가 있습니다. 퀵 정렬 알고리즘으로 정렬합니다

먼저, 몇 가지 특수한 기호를 선언하여 설명하기 쉽게 합니다

• 숫자 뒤에 붙는 대문자는 포인터를 나타냅니다. 예를 들어 2.5P 는 포인터 P 가 요소 2.5 의 위치를 가리키는 것을 나타냅니다
• @는 쓰레기 숫자를 나타냅니다. 즉, 현재 위치가 무엇이든 상관없으므로 여기에 얽매일 필요는 없습니다. 뒤에 구체적인 설명이 있습니다
• _는 해당 위치의 요소가 이전 행과 같음을 나타냅니다 (_ 는 불변을 나타냅니다)

P.S.진정으로 이해하려면 지금 당장 종이와 펜을 준비하십시오. 눈으로만 보는 것은 절대 충분하지 않습니다

이제 본격적으로 한 라운드의 퀵 정렬 프로세스 해석을 시작합니다

설명:

1. 첫 번째 행은 초기 상태입니다. 퀵 정렬에는 두 개의 포인터 L 과 H(低位 Low, 高位 High 를 나타냄), 하나의 임시 변수 temp 가 필요합니다

   초기 시低位 포인터 L 은 첫 번째 요소 9 를 가리키고, 高位 포인터 H 는 마지막 요소 7 을 가리키며, temp= 첫 번째 요소 9(temp 가 소위 '피벗'입니다)

2. 다음 조작을 수행: (왜인지는 나중에 설명)

   *H 와 temp 를 비교*하여, *H 가 크면 H 를 앞으로 이동하여 비교 계속. *H 가 작으면 *L = *H, *H = @(H 가 가리키는 값이 쓰레기 숫자가 됨), L 을 뒤로 이동

   7 < 9 이므로 L 이 가리키는 9 를 7 로 바꾸고, H 가 가리키는 7 을 쓰레기 숫자로 바꾸고, L 포인터를 뒤로 이동하여 두 번째 행의 결과를 얻습니다

3. 다음 조작을 수행: (왜인지는 나중에 설명)

   *L 과 temp 를 비교*하여, *L 이 작으면 L 을 뒤로 이동하여 비교 계속. *L 이 크면 *H = *L, *L = @(L 이 가리키는 값이 쓰레기 숫자가 됨), H 를 앞으로 이동

   0 < 9 이므로 L 을 뒤로 이동하여 세 번째 행의 결과를 얻습니다

4. 8 < 9 이므로 위와 동일
5. 10 > 9 이므로 H 가 가리키는 쓰레기 숫자@를 10 으로 바꾸고, L 이 가리키는 10 을 쓰레기 숫자로 바꾸고, H 포인터를 앞으로 이동하여 5 번째 행의 결과를 얻습니다
6. 13 > 9 이므로 H 포인터를 앞으로 이동하여 6 번째 행의 결과를 얻습니다
7. 2 < 9 이므로 L 이 가리키는 쓰레기 숫자@를 2 로 바꾸고, H 가 가리키는 2 를 쓰레기 숫자로 바꾸고, L 포인터를 뒤로 이동하여 7 번째 행의 결과를 얻습니다
8. -5 < 9 이므로 L 포인터를 뒤로 이동하여 8 번째 행의 결과를 얻습니다
9. 다음 조작을 수행: (왜인지는 나중에 설명)

   L = H 이면 *L = *H = temp, 한 라운드의 퀵 정렬 종료

   L 포인터와 H 포인터가 겹쳤으므로 L 이 가리키는 쓰레기 숫자@를 temp 의 값 9 로 바꾸고, 한 라운드 종료

   이로써 피벗 9 의 최종 위치를 확정했습니다. 주어진 시퀀스도 자연스럽게 두 개의 하위 시퀀스{7, 0, 8, 2, -5}와{13, 10}로 분할되었습니다. 하위 시퀀스에 대해 동일한 조작을 수행하면 최종적으로 정렬된 시퀀스를 얻을 수 있습니다

다음으로 위에서 언급한 세 그룹의 조작을 설명합니다

간단히 말해, 위의 세 그룹의 조작은 temp 의 최종 위치를 찾기 위한 것으로, 각 단계에서 L 앞은 모두 temp 보다 작고, H 뒤는 모두 temp 보다 크다는 것을 보장합니다. 따라서 H 와 L 이 겹치는 위치의 요소는 temp 의 값이 될 수밖에 없습니다

위에서 언급한 세 그룹의 조작은 다음과 같은 몇 가지 규칙으로 간략화할 수 있습니다. 기억하기 쉽습니다:

1. L 이 가리키는 값이 작으면 L 이동, 그렇지 않으면 값 대입 후 포인터 이동
2. H 가 가리키는 값이 크면 H 이동, 그렇지 않으면 위와 동일
3. HL 이 겹치면 temp 대입
4. H, L 은 교대로 temp 와 비교. 규칙은 한 번 대입 후 한 라운드 종료 (따라서 처음에는 L 과 temp 비교부터 시작해도 됨. 다음 라운드는 H 와 temp 비교, 그 다음 라운드는...)

P.S.어떻게 이동하는지는低位 포인터는 高位로만 이동할 수 있으며, 그 반대도 마찬가지입니다. 값 대입 후 어느 포인터를 이동하는지는 물론 다른 포인터 (현재 포인터가 아닌) 입니다

사.요약

정렬 알고리즘의 응용은 구체적인 환경과 결합하여 고려해야 합니다. 예를 들어 주어진 시퀀스가 부분적으로 정렬되어 있다면 당연히 이진 삽입 알고리즘이 가장 빠릅니다...

퀵 정렬도 최선은 아닙니다. 그 '빠름'은 종합적인 고려를 기반으로 구축된 것이며, 구체적인 상황에서는 반드��� 그렇지 않을 수 있습니다

퀵 정렬도 만능은 아닙니다. 예를 들어 주어진 시퀀스 규모가 작을 경우 선택 정렬이 퀵 정렬보다 훨씬 낫습니다

또한 일반적인 정렬 알고리즘에는 다음과 같은 것이 있습니다:

1. 버킷 정렬/박스 정렬 (Bucketsort)
2. 기수 정렬 (Radixsort)
3. 삽입 정렬 (Insertsort)
4. 선택 정렬 (Selectsort)
5. 병합 정렬 (Mergesort)
6. 퀵 정렬 (Quicksort)
7. 힙 정렬 (Heapsort)