빠른 정렬 알고리즘 : 다른 답변 계속 계속

Question

이번 주 화요일에 예정된 테스트를 위해 다양한 정렬 및 검색 알고리즘을 연구하려고합니다. 빠른 정렬 알고리즘을 사용할 때까지 모든 것이 잘 진행되었습니다. 나는 책이나 다른 자료가 없었기 때문에 온라인에 가서 SparkNote을 읽기 시작했습니다. 나는이 텍스트를 이해할 줄 알았는데, 나는 심지어 온라인에서 찾은 PowerPoint의 빠른 정렬 알고리즘 부분을 읽었다.

그러나 SparkNote는 알고리즘의 단계별 프로세스 페이지에 예제를 제공했지만 처음에는 목록을 정렬하는 단계를 보여주지 않았습니다. 주어진 목록은 [5 9 3 8 6 4 2 1 7 0]입니다. SparkNotes에 따르면 왼쪽에 피벗 (5)보다 작은 값과 오른쪽 피벗보다 큰 값이있는 정렬 된 목록은 [0 3 4 2 1 5 8 6 7 9]입니다. 그러나, 내가 직접 조치를 취하려고하면, 나는 계속 [ 4 0 3 1 2 5 6 8 7 9 ]을 얻는다. 내가했다

절차는이었다

5 9 3 8 6 4 2 1 7 0 // The initial list. Pivot = 5 
5 0 3 8 6 4 2 1 7 9 // Switched 0 and 9. 
5 0 3 1 6 4 2 1 7 9 // Switched 8 and 1 
5 0 3 1 2 4 6 8 7 9 // Switched 6 and 2 
4 0 3 1 2 5 6 8 7 9 // Switched 4 and 5 because the lines that point to the 
        // greater and smaller numbers crossed. 

어디에 내 실수는? 또한 5 이하의 숫자가 왼쪽에 있고 5보다 큰 숫자가 오른쪽에있는 것을 볼 수 있습니다. 그렇다면 내 실수가 정렬에 실제로 영향을 줍니까?

Answer 1

SparkNotes에 설명 된 알고리즘은 처음에 배열의 오른쪽에 위치에 피벗 요소를 배치합니다. 사용 된 알고리즘은 피벗을 왼쪽으로 위치로 배치/보관했습니다. 파티셔닝 후 준비가 다른 것도 당연합니다. 그들은

5 9 3 8 6 4 2 1 7 0 

시작을 의미

피봇으로 5를 선택하고 가장 오른쪽 위치에 배치

0 9 3 8 6 4 2 1 7 5 

및 (5 및 0 교환) 그들이 대한 분할을 수행 만 그 후 나머지 요소.

5을 맨 왼쪽 위치에 두었습니다 (분명히 SparkNotes에서 2 단계를 수행하는 것을 잊어 버린 것 같습니다). 결국 두 변형 모두 작동합니다. 즉 '실수'가 없습니다. 귀하의 경우 배열은 올바르게 파티션이 배열 된 상태에서 완벽하게 유효합니다.

Answer 2

당신은 sparknotes 사이트에 제시된 정확한 알고리즘을 따르지 않았습니다. 두 번째 단계에서는 피벗을 마지막 요소로 바꿔야합니다.

어떤 경우에도 피벗 앞의 모든 요소가 피벗 및 그 뒤의 요소보다 작도록 시퀀스를 분할하는 한 정확하게 분할을 수행하는 알고리즘과는 무관합니다 더 크거나 같음. 결과로 나오는 파티션을 재귀 적으로 정렬 할 때 결국 정렬 된 시퀀스로 끝날 것입니다.

정확도가 아닌 정확성, 동등한 요소를 처리하는 방법 및 피벗을 선택하는 방법뿐만 아니라 결국 다른 알고리즘으로 전환 할 순서 길이에 따라 다릅니다.

Answer 3

HereQuick-sort 알고리즘의 시각적 구현을 ​​볼 수 있습니다.

그리고 어쩌면 당신도 유용 할 것입니다 : 당신이 헝가리어 민속 무용을 싫어하면

• Merge-sort
• Shell-sort
• Bubble-sort

링크로 이동하지 마십시오. :)