숫자 목록 정렬 순서 (정렬 없음)

Question

고유 한 정수 배열 (예 : val[i])이 임의의 순서로 있고 다른 배열 (ord[i])에 정렬하려는 인덱스를 채우고 싶습니다. 정수. 즉 val[ord[i]]은 정렬 순서대로 증가하여 i입니다.

지금 당장은 0, ..., N으로 ord을 채 웁니다. 값 배열을 기준으로 정렬합니다. 그러나 이후로 더 효율적으로 처리 할 수 ​​있는지 궁금합니다. ord은 (으)로 채워지지 않습니다. . 이것은 호기심에서 벗어난 질문입니다. 목록을 미리 채우고 정렬하는 데 드는 추가 오버 헤드에 대해서는별로 신경 쓰지 않습니다 (작고 삽입 정렬 사용). 이것은 명백한 대답으로 어리석은 질문 일지 모르지만 온라인에서 아무 것도 찾을 수 없습니다.

Answer 1

시간 복잡성과 관련하여 정렬보다 빠른 방법이있을 수 없습니다. 검색 결과가있는 경우이를 사용하여 더 빨리 정렬 할 수 있습니다. 색인을 생성 한 다음 원본 배열을 정렬 순서대로 정렬하는 데 사용합니다. 이 재정렬은 선형 시간이 걸릴 것이므로 전체적으로 더 빠른 정렬 알고리즘을 사용하여 모순을 만듭니다.

Answer 2

삽입 정렬은 iirc 꽤 낮습니다. 따라서 작은 목록 (거의 정렬 된 목록에도 해당)에서 작동합니다. 그러나 목록이 작아서 더 나쁜 최악의 경우의 복잡성이 더 좋지는 않습니까? in-place merge 나 quick sort는 법안에 잘 부합하는 것처럼 보일 것입니다. (빠른 정렬은 어쨌든 최적화로서 매우 작은 목록을위한 또 다른 정렬로 전환 될 수 있습니다). > 무한 나는 이것을 알고