아메리칸 플래그 정렬 최적화

Question

아메리칸 버킷 정렬을 구현하려고합니다. Wiki는 "먼저 각 저장소에 들어갈 개체의 수를 계산하고 두 번째로 각 개체를 해당 양동이에 배치합니다."라고 말합니다.

두 번째 단계에서 올바른 버켓에 개체를 놓을 때 보조 배열을 사용해야합니까? 선형 시간에 배열 요소를 교환하여이 작업을 수행 할 수 있습니까?

Answer 1

http://en.wikipedia.org/wiki/American_flag_sort으로 가정하면 기사에서 맨 위에 표시되므로이 위치에서 실행할 수 있습니다 (안정적인 정렬은 아니지만). 주요 아이디어는 처음 읽지 않은 첫 번째 항목에 대한 포인터 (처음에는 0)와 하나의 항목을 포함하는 임시 변수를 갖는 것입니다.

첫 번째 단계에서는 포인터를보고 항목을 선택합니다. 이제 색인을 사용하여 색인을 작성할 수 있습니다. 장소가 원래 읽은 위치가 아니라면 다른 항목을 덮어 쓰려고하기 때문에 가져온 항목을 덮어 쓸 항목으로 바꿔서 이제는 다른 임시 항목을 들고 있습니다. 어디로 가야하고 계속해야하는지.

결국 읽은 위치에 무언가를 넣었으므로 읽기 포인터를 증가시키고 정렬 된 항목을 이미 작성한 영역을 건너 뛰고 다른 항목을 선택하고 모든 것이 정렬 될 때까지 계속할 수 있습니다.