연결 목록을 정렬하는 가장 빠른 알고리즘은 무엇입니까?

연결 목록을 정렬하는 가장 빠른 알고리즘은 무엇입니까?

---

O (n log n)이 링크드리스트가 할 수있는 최선인지 궁금합니다.

---

실행 시간 에 O (N log N)보다 더 잘할 수 없다고 예상하는 것이 합리적 입니다.

그러나 흥미로운 부분은 제자리 에서 안정적으로 정렬 할 수 있는지 , 최악의 경우 동작 등 을 조사하는 것 입니다.

Putty로 유명한 Simon Tatham 이 병합 정렬을 사용하여 연결 목록 을 정렬하는 방법을 설명합니다 . 그는 다음과 같이 결론을 내립니다.

모든 자존심 정렬 알고리즘과 마찬가지로 실행 시간은 O (N log N)입니다. 이것은 Mergesort이기 때문에 최악의 실행 시간은 여전히 ​​O (N log N); 병리학 적 사례가 없습니다.

보조 스토리지 요구 사항은 작고 일정합니다 (예 : 정렬 루틴 내의 몇 가지 변수). 배열에서 연결된 목록의 본질적으로 다른 동작 덕분에이 Mergesort 구현은 일반적으로 알고리즘과 관련된 O (N) 보조 기억 장치 비용을 방지합니다.

또한 단일 및 이중 연결 목록 모두에서 작동하는 C 구현의 예가 있습니다.

@ Jørgen Fogh가 아래에서 언급했듯이 big-O 표기법은 메모리 지역성, 적은 수의 항목 등으로 인해 하나의 알고리즘이 더 나은 성능을 발휘할 수있는 몇 가지 상수 요소를 숨길 수 있습니다.

---

여러 요인에 따라 목록을 배열에 복사 한 다음 Quicksort 를 사용하는 것이 실제로 더 빠를 수 있습니다 .

이것이 더 빠를 수있는 이유는 배열이 연결된 목록보다 캐시 성능이 훨씬 더 우수하기 때문입니다. 목록의 노드가 메모리에 분산되어있는 경우 모든 곳에서 캐시 미스가 생성 될 수 있습니다. 그런 다음 어레이가 크면 어쨌든 캐시 누락이 발생합니다.

병합 정렬이 더 잘 병렬화되므로 원하는 경우 더 나은 선택이 될 수 있습니다. 연결 목록에서 직접 수행하면 훨씬 빠릅니다.

두 알고리즘 모두 O (n * log n)에서 실행되기 때문에 정보에 입각 한 결정을 내리려면 실행하려는 시스템에서 두 알고리즘을 모두 프로파일 링해야합니다.

--- 편집하다

나는 내 가설을 테스트하기로 결정 clock()하고 연결된 int 목록을 정렬하는 데 걸린 시간을 측정하는 C 프로그램을 작성했습니다 . 각 노드가 할당 된 malloc()연결 목록과 노드가 배열에서 선형으로 배치 된 연결 목록으로 시도 했으므로 캐시 성능이 더 좋을 것입니다. 나는 이것을 내장 qsort와 비교했는데, 여기에는 조각난 목록에서 배열로 모든 것을 복사하고 결과를 다시 복사하는 것이 포함되었습니다. 각 알고리즘은 동일한 10 개의 데이터 세트에서 실행되었으며 결과는 평균화되었습니다.

결과는 다음과 같습니다.

N = 1000 :

병합 정렬이있는 조각난 목록 : 0.000000 초

qsort가있는 어레이 : 0.000000 초

병합 정렬이 포함 된 패킹 된 목록 : 0.000000 초

N = 100000 :

병합 정렬이있는 조각난 목록 : 0.039000 초

qsort가있는 어레이 : 0.025000 초

병합 정렬이 포함 된 패킹 된 목록 : 0.009000 초

N = 1000000 :

병합 정렬이있는 조각난 목록 : 1.162000 초

qsort가있는 어레이 : 0.420000 초

병합 정렬이 포함 된 패킹 된 목록 : 0.112000 초

N = 100000000 :

병합 정렬이있는 조각난 목록 : 364.797000 초

qsort가있는 어레이 : 61.166000 초

병합 정렬이있는 압축 목록 : 16.525000 초

결론:

적어도 내 컴퓨터에서는 배열로 복사하는 것이 캐시 성능을 향상시키는 데 그만한 가치가 있습니다. 실생활에서 완전히 묶인 연결 목록이 거의 없기 때문입니다. 내 컴퓨터에는 2.8GHz Phenom II가 있지만 0.6GHz RAM 만 있으므로 캐시가 매우 중요합니다.

---

비교 정렬 (즉, 비교 요소를 기반으로하는 정렬)은보다 빠를 수 없습니다 n log n. 기본 데이터 구조가 무엇인지는 중요하지 않습니다. Wikipedia를 참조하십시오 .

목록에 동일한 요소가 많이 있음 (카운팅 정렬 등)을 활용하는 다른 종류의 정렬 또는 목록에서 예상되는 요소 분포가 더 빠릅니다. 특히 잘 작동하는 항목은 생각할 수 없습니다. 연결 목록에.

---

여러 번 언급했듯이 일반 데이터에 대한 비교 기반 정렬의 하한은 O (n log n)입니다. 이러한 인수를 간단히 다시 요약하기 위해 n! 목록을 정렬 할 수있는 다양한 방법. n이있는 모든 종류의 비교 트리! (O (n ^ n)에 있음) 가능한 최종 정렬은 높이로 최소한 log (n!)이 필요합니다. 이것은 O (log (n ^ n)) 하한을 제공합니다. 즉, O (n lg n).

따라서 연결된 목록의 일반 데이터의 경우 두 개체를 비교할 수있는 모든 데이터에 대해 작동 할 수있는 최상의 정렬은 O (n log n)입니다. 그러나 작업 할 영역이 더 제한적이라면 소요 시간을 개선 할 수 있습니다 (적어도 n에 비례). 예를 들어, 어떤 값보다 크지 않은 정수로 작업하는 경우 Counting Sort 또는 Radix Sort를 사용할 수 있습니다. 이들은 n에 비례하여 복잡성을 줄이기 위해 정렬하는 특정 객체를 사용하기 때문입니다. 하지만주의해야 할 점은 고려하지 않을 수있는 복잡성에 몇 가지 다른 사항을 추가합니다 (예를 들어 Counting Sort 및 Radix 정렬은 모두 정렬하는 숫자의 크기를 기반으로하는 요소를 추가합니다. O (n + k ) 여기서 k는 Counting Sort에서 가장 큰 숫자의 크기입니다).

또한 완벽한 해시 (또는 적어도 모든 값을 다르게 매핑하는 해시)를 가진 객체가있는 경우 해당 해시 함수에 대해 계수 또는 기수 정렬을 사용해 볼 수 있습니다.

---

이것은이 주제에 대한 멋진 작은 논문입니다. 그의 경험적 결론은 Treesort가 최고이며 Quicksort와 Mergesort가 그 뒤를 잇습니다. 퇴적물 분류, 기포 분류, 선택 분류가 매우 나쁘게 수행됩니다.

Ching-Kuang Shene의 링크드리스트 정렬 알고리즘 비교 연구

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981

---

기수 정렬 특히는 한 디지트의 각각의 가능한 값에 대응하는 헤드 포인터 테이블을 쉽게 만들 수 있으므로, 링크 된리스트에 적합하다.

---

병합 정렬에는 O (1) 액세스가 필요하지 않으며 O (n ln n)입니다. 일반 데이터를 정렬하는 알려진 알고리즘이 O (n ln n)보다 낫습니다.

The special data algorithms such as radix sort ( limits size of data ) or histogram sort ( counts discrete data ) could sort a linked list with a lower growth function, as long as you use a different structure with O(1) access as temporary storage.

Another class of special data is a comparison sort of an almost sorted list with k elements out of order. This can be sorted in O ( kn ) operations.

Copying the list to an array and back would be O(N), so any sorting algorithm can be used if space is not an issue.

For example, given a linked list containing uint_8, this code will sort it in O(N) time using a histogram sort:

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>

typedef struct _list list_t;
struct _list {
    uint8_t value;
    list_t  *next;
};


list_t* sort_list ( list_t* list )
{
    list_t* heads[257] = {0};
    list_t* tails[257] = {0};

    // O(N) loop
    for ( list_t* it = list; it != 0; it = it -> next ) {
        list_t* next = it -> next;

        if ( heads[ it -> value ] == 0 ) {
            heads[ it -> value ] = it;
        } else {
            tails[ it -> value ] -> next = it;
        }

        tails[ it -> value ] = it;
    }

    list_t* result = 0;

    // constant time loop
    for ( size_t i = 255; i-- > 0; ) {
        if ( tails[i] ) {
            tails[i] -> next = result;
            result = heads[i];
        }
    }

    return result;
}

list_t* make_list ( char* string )
{
    list_t head;

    for ( list_t* it = &head; *string; it = it -> next, ++string ) {
        it -> next = malloc ( sizeof ( list_t ) );
        it -> next -> value = ( uint8_t ) * string;
        it -> next -> next = 0;
    }

    return head.next;
}

void free_list ( list_t* list )
{
    for ( list_t* it = list; it != 0; ) {
        list_t* next = it -> next;
        free ( it );
        it = next;
    }
}

void print_list ( list_t* list )
{
    printf ( "[ " );

    if ( list ) {
        printf ( "%c", list -> value );

        for ( list_t* it = list -> next; it != 0; it = it -> next )
            printf ( ", %c", it -> value );
    }

    printf ( " ]\n" );
}


int main ( int nargs, char** args )
{
    list_t* list = make_list ( nargs > 1 ? args[1] : "wibble" );


    print_list ( list );

    list_t* sorted = sort_list ( list );


    print_list ( sorted );

    free_list ( list );
}

---

Not a direct answer to your question, but if you use a Skip List, it is already sorted and has O(log N) search time.

---

As I know, the best sorting algorithm is O(n*log n), whatever the container - it's been proved that sorting in the broad sense of the word (mergesort/quicksort etc style) can't go lower. Using a linked list will not give you a better run time.

The only one algorithm which runs in O(n) is a "hack" algorithm which relies on counting values rather than actually sorting.

---

Here's an implementation that traverses the list just once, collecting runs, then schedules the merges in the same way that mergesort does.

Complexity is O(n log m) where n is the number of items and m is the number of runs. Best case is O(n) (if the data is already sorted) and worst case is O(n log n) as expected.

It requires O(log m) temporary memory; the sort is done in-place on the lists.

(updated below. commenter one makes a good point that I should describe it here)

The gist of the algorithm is:

    while list not empty
        accumulate a run from the start of the list
        merge the run with a stack of merges that simulate mergesort's recursion
    merge all remaining items on the stack

Accumulating runs doesn't require much explanation, but it's good to take the opportunity to accumulate both ascending runs and descending runs (reversed). Here it prepends items smaller than the head of the run and appends items greater than or equal to the end of the run. (Note that prepending should use strict less-than to preserve sort stability.)

It's easiest to just paste the merging code here:

    int i = 0;
    for ( ; i < stack.size(); ++i) {
        if (!stack[i])
            break;
        run = merge(run, stack[i], comp);
        stack[i] = nullptr;
    }
    if (i < stack.size()) {
        stack[i] = run;
    } else {
        stack.push_back(run);
    }

Consider sorting the list (d a g i b e c f j h) (ignoring runs). The stack states proceed as follows:

    [ ]
    [ (d) ]
    [ () (a d) ]
    [ (g), (a d) ]
    [ () () (a d g i) ]
    [ (b) () (a d g i) ]
    [ () (b e) (a d g i) ]
    [ (c) (b e) (a d g i ) ]
    [ () () () (a b c d e f g i) ]
    [ (j) () () (a b c d e f g i) ]
    [ () (h j) () (a b c d e f g i) ]

Then, finally, merge all these lists.

Note that the number of items (runs) at stack[i] is either zero or 2^i and the stack size is bounded by 1+log2(nruns). Each element is merged once per stack level, hence O(n log m) comparisons. There's a passing similarity to Timsort here, though Timsort maintains its stack using something like a Fibonacci sequence where this uses powers of two.

Accumulating runs takes advantage of any already sorted data so that best case complexity is O(n) for an already sorted list (one run). Since we're accumulating both ascending and descending runs, runs will always be at least length 2. (This reduces the maximum stack depth by at least one, paying for the cost of finding the runs in the first place.) Worst case complexity is O(n log n), as expected, for data that is highly randomized.

(Um... Second update.)

Or just see wikipedia on bottom-up mergesort.

---

You can copy it into an array and then sort it.

• Copying into array O(n),

• sorting O(nlgn) (if you use a fast algorithm like merge sort ),

• copying back to linked list O(n) if necessary,

so it is gonna be O(nlgn).

note that if you do not know the number of elements in the linked list you won't know the size of array. If you are coding in java you can use an Arraylist for example.

---

Mergesort is the best you can do here.

참고URL : https://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list