더 빠릅니다 : n 개의 요소를 정렬하거나 n 개의 요소를 올바른 위치에 하나씩 삽입 하시겠습니까?

Question

일반적으로 어떤 것이 더 좋을까요? 일부 컬렉션에 N 개의 요소를 삽입하고 정렬하거나 요소를 삽입하기 전에 올바른 위치를 찾아서 그 위치에 정확하게 삽입합니다 (N 번 반복).

Answer 1

데이터 구조와 사용중인 응용 프로그램에 따라 달라질 수 있습니다.

배열에을 삽입하려면 다음 요소를 모두 오른쪽으로 이동해야합니다 (결과적으로 O(n) 삽입).
Binary Search Tree 그러나 O(logn)에 삽입 할 수 있지만 보다 작 으면 어레이가 더 느려지고 따라서 느립니다. 한편

삽입 한 후 마지막 요소가 삽입 된 후 높은 latency 결과 정렬 [ O(nlogn) 정렬].
또한 매우 자주 쿼리하려고하지만 드물게 요소를 추가하는 경우 너무 자주 정렬하지 않으려 고합니다. 요소를 순서대로 유지하면 쉽게이 작업을 수행 할 수 있습니다.

Answer 2

입력을 전제로하지 않고 정렬하려면 nlog (n) 시간이 필요합니다. 요소를 삽입하려면 O (n) 시간이 걸립니다 (연결된 목록). 따라서 모든 삽입 후 정렬이 빠릅니다.

Answer 3

데이터 구조에 따라 다릅니다. 삽입하기 전에 올바른 위치를 찾으려면 데이터 구조에 이미 저장되어 있어야하는 방식으로 요소를 정렬해야합니다. 달성하고자하는 것에 대한 추가 정보를 제공 할 수 있습니까?

Answer 4

이는 더 나은

"일부 컬렉션의 N 요소를 삽입 한 후 정렬"

하나가 정렬 O(nlogn) 알고리즘을 사용할 수 있기 때문에. 어디로이

"삽입하기 전에 요소에 대한 올바른 위치를 찾아 정확히 그 장소에 (N 번 반복) 입니까?"

은 삽입 유형이며 최악의 경우는 O(n^2)입니다.

즉 삽입 정렬은 온라인 알고리즘입니다. 즉 정렬을 시작하기 위해 전체 데이터를 미리 알 필요가 없습니다. 병렬로 실행되는 다른 프로그램에 의해 생성되는 데이터를 고려하십시오. 여기서 삽입 정렬이 의미가 있습니다. 다른 접근 방식에서는 전체 데이터가 제 위치에 있어야합니다.