항목을 삽입하거나 정렬 된 목록에 추가 한 후 목록을 정렬하는 것이 더 빠릅니까?

항목을 삽입하거나 정렬 된 목록에 추가 한 후 목록을 정렬하는 것이 더 빠릅니까?

---

정렬 된 목록 (예 : 빠른 정렬)이있는 경우 추가 할 값이 많으면 정렬을 일시 중단하고 끝에 추가 한 다음 정렬하거나 이진 절단을 사용하여 항목을 올바르게 배치하는 것이 좋습니다. 추가합니다. 항목이 무작위인지 아니면 이미 순서가 많거나 적은 경우 차이가 있습니까?

---

목록을 처음부터 효과적으로 작성하는 데 충분한 항목을 추가하면 나중에 목록을 정렬하여 더 나은 성능을 얻을 수 있습니다.

항목이 대부분 순서가 맞으면 점진적 업데이트와 정기 정렬을 모두 조정하여이를 활용할 수 있지만 솔직히 말해서 문제의 가치가 없습니다. (예기치 않은 순서로 인해 알고리즘이 훨씬 오래 걸리지 않도록주의해야합니다 . qv naive quicksort)

증분 업데이트와 일반 목록 정렬은 모두 O (N log N)이지만 나중에 모든 항목을 정렬하는 더 나은 상수 요소를 얻을 수 있습니다 (여기서는 증분 업데이트가 O보다 빠르게 목록 항목에 액세스 할 수 있도록 보조 데이터 구조가 있다고 가정합니다. (엔)...). 일반적으로 증분 업데이트는 항상 완전한 순서를 유지해야하지만 일괄 정렬은 그렇지 않기 때문에 한 번에 모두 정렬하면 순서를 점진적으로 유지하는 것보다 훨씬 더 많은 디자인 자유가 있습니다.

다른 것이 없다면 고도로 최적화 된 대량 정렬을 사용할 수 있다는 점을 기억하십시오.

---

일반적으로 heap 을 사용하는 것이 훨씬 좋습니다 . 요컨대, 푸셔와 피커 사이의 주문 유지 비용을 나눕니다. 두 연산 모두 대부분의 다른 솔루션과 마찬가지로 O (n log n) 대신 O (log n)입니다.

---

묶음으로 추가하는 경우 병합 정렬을 사용할 수 있습니다. 추가 할 항목 목록을 정렬 한 다음 두 목록에서 복사하여 항목을 비교하여 다음에 복사 할 항목을 결정합니다. 대상 배열의 크기를 조정하고 끝에서 거꾸로 작업하는 경우 제자리에 복사 할 수도 있습니다.

이 솔루션의 효율성은 O (n + m) + O (m log m)입니다. 여기서 n은 원래 목록의 크기이고 m은 삽입되는 항목의 수입니다.

편집 : 이 답변은 사랑을받지 못하기 때문에 C ++ 샘플 코드로 구체화 할 것이라고 생각했습니다. 정렬 된 목록이 배열이 아닌 연결 목록에 유지된다고 가정합니다. 이렇게하면 알고리즘이 병합보다 삽입처럼 보이도록 변경되지만 원리는 동일합니다.

// Note that itemstoadd is modified as a side effect of this function
template<typename T>
void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd)
{
    std::sort(itemstoadd.begin(), itemstoadd.end());
    std::list<T>::iterator listposition = sortedlist.begin();
    std::vector<T>::iterator nextnewitem = itemstoadd.begin();
    while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end()))
    {
        if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition))
            sortedlist.insert(listposition, *nextnewitem++);
        else
            ++listposition;
    }
}

---

원칙적으로 목록을 정렬하는 것보다 트리를 만드는 것이 더 빠릅니다. 트리 삽입은 각 삽입에 대해 O (log (n))이며 전체 O (n log (n))로 이어집니다. O (n log (n))로 정렬 합니다.

이것이 자바에 TreeMap이있는 이유입니다 (List의 TreeSet, TreeList, ArrayList 및 LinkedList 구현 외에도).

• TreeSet은 객체 비교 순서로 사물을 유지합니다. 키는 Comparable 인터페이스에 의해 정의됩니다.

• LinkedList는 항목을 삽입 순서대로 유지합니다.

• ArrayList는 더 많은 메모리를 사용하고 일부 작업의 경우 더 빠릅니다.

• 마찬가지로 TreeMap은 키별로 정렬 할 필요가 없습니다. 지도는 삽입하는 동안 키 순서로 작성되며 항상 정렬 된 순서로 유지됩니다.

그러나 어떤 이유로 TreeSet의 Java 구현은 ArrayList 및 정렬을 사용하는 것보다 훨씬 느립니다.

[왜 극적으로 느려질 지 추측하기는 어렵지만 그렇습니다. 데이터를 한 번 통과하면 약간 더 빨라질 것입니다. 이런 종류의 것은 종종 알고리즘 분석을 능가하는 메모리 관리 비용입니다.]

---

나는 그것을 테스트 해보자! :)

나는 quicksort로 시도했지만, quicksort로 거의 정렬 배열을 정렬하는 것은 ... 글쎄, 좋은 생각이 아닙니다. 나는 수정 된 것을 시도하여 7 개의 요소를 잘라 내고 삽입 정렬을 사용했습니다. 그래도 끔찍한 성능. 병합 정렬로 전환했습니다. 정렬을 위해 상당히 많은 메모리가 필요할 수 있지만 (제자리에 있지 않음) 정렬 된 배열에서는 성능이 훨씬 더 좋고 임의의 배열에서는 거의 동일합니다 (초기 정렬은 둘 다 거의 같은 시간이 걸렸고 퀵 정렬은 약간 더 빠릅니다. ).

이것은 이미 한 가지를 보여줍니다. 질문에 대한 대답은 사용하는 정렬 알고리즘에 따라 크게 달라집니다. 거의 정렬 된 목록에서 성능이 저하 될 경우 올바른 위치에 삽입하는 것이 끝에 추가 한 다음 다시 정렬하는 것보다 훨씬 빠릅니다. 목록이 큰 경우 너무 많은 외부 메모리가 필요할 수 있으므로 병합 정렬은 옵션이 아닐 수 있습니다. BTW 나는 순진한 구현 (어레이 크기 자체만큼 많은 외부 저장소가 필요함)에 외부 저장소의 1/2 만 사용하는 사용자 지정 병합 정렬 구현을 사용했습니다.

병합 정렬이 옵션이없고 빠른 정렬이 확실한 옵션이 아닌 경우 가장 좋은 대안은 힙 정렬 일 것입니다.

내 결과는 다음과 같습니다. 단순히 끝에 새 요소를 추가 한 다음 배열을 다시 정렬하는 것이 올바른 위치에 삽입하는 것보다 몇 가지 더 빠릅니다. 그러나 초기 배열에는 10 mio 요소 (정렬 됨)가 있었고 또 다른 mio (정렬되지 않음)를 추가했습니다. 따라서 10 mio의 배열에 10 개의 요소를 추가하는 경우 올바르게 삽입하는 것이 모든 항목을 다시 정렬하는 것보다 훨씬 빠릅니다. 따라서 질문에 대한 대답은 초기 (정렬 된) 배열의 크기와 여기에 추가하려는 새 요소의 수에 따라 달라집니다.

---

목록이 a) 이미 정렬되어 있고 b) 본질적으로 동적이면 정렬 된 목록에 삽입하는 것이 항상 더 빨라야합니다 (올바른 위치 (O (n))를 찾고 삽입 (O (1))).

그러나 목록이 정적 인 경우 나머지 목록의 셔플이 발생해야합니다 (올바른 위치를 찾으려면 O (n)을, 아래로 슬라이드하려면 O (n)).

어느 쪽이든 정렬 된 목록 (또는 이진 검색 트리와 같은 것)에 삽입하는 것이 더 빠릅니다.

O (n) + O (n)은 항상 O (N log n)보다 빨라야합니다.

---

거의 같습니다. 정렬 된 목록에 항목을 삽입하는 것은 O (log N)이며, 목록의 모든 요소 N에 대해이 작업을 수행하면 (따라서 목록 작성) 빠른 정렬 (또는 병합 정렬)의 속도 인 O (N log N)가됩니다. 이 접근 방식에 더 가깝습니다).

대신 앞쪽에 삽입하면 O (1)이되지만 퀵 정렬을 수행하면 여전히 O (N log N)이됩니다.

I would go with the first approach, because it has the potential to be slightly faster. If the initial size of your list, N, is much greater than the number of elements to insert, X, then the insert approach is O(X log N). Sorting after inserting to the head of the list is O(N log N). If N=0 (IE: your list is initially empty), the speed of inserting in sorted order, or sorting afterwards are the same.

---

You should add them before and then use a radix sort this should be optimal

http://en.wikipedia.org/wiki/Radix_sort#Efficiency

---

If this is .NET and the items are integers, it's quicker to add them to a Dictionary (or if you're on .Net 3.0 or above use the HashSet if you don't mind losing duplicates)This gives you automagic sorting.

I think that strings would work the same way as well. The beauty is you get O(1) insertion and sorting this way.

---

(If the list you're talking about is like C# List<T>.) Adding some values to right positions into a sorted list with many values is going to require less operations. But if the number of values being added becomes large, it will require more.

I would suggest using not a list but some more suitable data structure in your case. Like a binary tree, for example. A sorted data structure with minimal insertion time.

---

Inserting an item into a sorted list takes O(n) time, not O(log n) time. You have to find the place to put it, taking O(log n) time. But then you have to shift over all the elements - taking O(n) time. So inserting while maintaining sorted-ness is O(n ^ 2), where as inserting them all and then sorting is O(n log n).

Depending on your sort implementation, you can get even better than O(n log n) if the number of inserts is much smaller than the list size. But if that is the case, it doesn't matter either way.

So do the insert all and sort solution if the number of inserts is large, otherwise it probably won't matter.

---

At a high level, it's a pretty simple problem, because you can think of sorting as just iterated searching. When you want to insert an element into an ordered array, list, or tree, you have to search for the point at which to insert it. Then you put it in, at hopefully low cost. So you could think of a sort algorithm as just taking a bunch of things and, one by one, searching for the proper position and inserting them. Thus, an insertion sort (O(n* n)) is an iterated linear search (O(n)). Tree, heap, merge, radix, and quick sort (O(n*log(n))) can be thought of as iterated binary search (O(log(n))). It is possible to have an O(n) sort, if the underlying search is O(1) as in an ordered hash table. (An example of this is sorting 52 cards by flinging them into 52 bins.)

So the answer to your question is, inserting things one at a time, versus saving them up and then sorting them should not make much difference, in a big-O sense. You could of course have constant factors to deal with, and those might be significant.

Of course, if n is small, like 10, the whole discussion is silly.

---

Inserting an item into a sorted list is O(log n), while sorting a list is O(n log N) Which would suggest that it's always better to sort first and then insert

But remeber big 'O' only concerns the scaling of the speed with number of items, it might be that for your application an insert in the middle is expensive (eg if it was a vector) and so appending and sorting afterward might be better.

참고URL : https://stackoverflow.com/questions/168891/is-it-faster-to-sort-a-list-after-inserting-items-or-adding-them-to-a-sorted-lis