Bentley-McIlroy 3-way partitioning

Tags:

Quicksort is Optimal

duplicate key가 많은 경우의 해결 방법. 파티셔닝 할 때, 좌우 끝에서 가운데로 온다. 이 때, 양쪽끝에 pivot 과 같은 값을 몰아놨다가 가운데까지 오면 양쪽끝에 놔두었던 equal value를 가운데로 모은다.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *