왜 링크 된 목록의 빠른 정렬은 배열 1보다 훨씬 느립니다?

Question

링크 된 목록 및 배열에 대한 빠른 정렬 알고리즘 구현을 요구하는 알고리즘 문제가있었습니다.
나는 두 부분을 다했는데 알고리즘은 작동하지만 내 빠른 정렬 링크 목록 구현에 버그가있는 것 같습니다.

내 빠른 정렬 링크 목록 구현입니다.

public static void SortLinkedList(DataList items, DataList.Node low, DataList.Node high) 
    { 
     if(low != null && low !=high) 
     { 
      DataList.Node p = _PartitionLinkedList(items, low, high); 
      SortLinkedList(items, low, p); 
      SortLinkedList(items, p.Next(), null); 
     } 


    } 

    private static DataList.Node _PartitionLinkedList(DataList items, DataList.Node low, DataList.Node high) 
    { 
     DataList.Node pivot = low; 
     DataList.Node i = low; 
     for (DataList.Node j = i.Next(); j != high; j=j.Next()) 
     { 
      if (j.Value().CompareTo(pivot.Value()) <= 0) 
      { 

       items.Swap(i.Next(),j); 
       i = i.Next(); 

      } 
     } 
     items.Swap(pivot, i); 
     return i; 
    } 

여기

public static void SortData(DataArray items, int low, int high) 
    { 
     if (low < high) 
     { 
      int pi = _PartitionData(items, low, high); 
      SortData(items, low, pi - 1); 
      SortData(items, pi + 1, high); 
     } 

    } 
static int _PartitionData(DataArray arr, int low, int high) 
    { 
     double pivot = arr[high]; 
     int i = (low - 1); 
     for (int j = low; j <= high - 1; j++) 
     { 
      if (arr[j].CompareTo(pivot)<=0) 
      { 
       i++; 
       arr.Swap(i,j); 
      } 
     } 
     arr.Swap(i + 1, high); 
     return i + 1; 
    } 

여기 빠른 정렬 배열과 연결리스트의 성능입니다 빠른 정렬 배열의 구현을합니다. (left n, right time)
Picture
qs linked list에서 알 수 있듯이 6400 개의 요소를 정렬하는 데 10 분이 걸렸습니다. 그 정상적인 것 같아 ..

또한 데이터 구조 때문에 내가 생각하기 때문에 내가 선택한 정렬 및 성능에 대한 동일한 구조를 사용했기 때문에 링크 된 목록과 배열에 대한 유사했다.

GitHub repo 일부 코드를 제공하는 것을 잊어 버린 경우를 대비하여. Repo

Answer 1

10 분은 6400 요소의 경우 매우 길다. 일반적으로 하나가 아니라 2 ~ 3 가지의 끔찍한 실수가 필요합니다.

불행히도 나는 단지 하나의 끔찍한 실수 만 보았습니다. SortLinkedList(items, p.Next(), null);에 대한 두 번째 재귀 호출은 목록의 끝까지갑니다. 너는 그것이 high에 멈추는 것을 의미했다.

10 분이 걸릴 수도 있지만 약간은 드뭅니다.

위의 버그를 수정 한 후에도 정렬이 잘못되었습니다. 출력을 테스트해야합니다.

Answer 2

나는 당신의 연결 목록, 특히 스왑 방법을 살펴볼 것입니다. 연결된 목록의 구현을 보지 않으면 문제 영역이 있다고 생각합니다.

왜 연결 목록을 사용하고 있습니까? 그들은 quicksort n^2lg (n) 정렬을 만드는 o (n) 검색을 가지고 있습니다.

다른 방법은 연결된 목록의 모든 항목을 목록에 추가하고, 목록을 정렬하고, 연결된 목록을 다시 만드는 것입니다. List.Sort()는 빠른 정렬을 사용합니다.

public static void SortLinkedList(DataList items) 
{ 
    list<object> actualList = new list<object>(); 

    for (DataList.Node j = i.Next(); j != null; j=j.Next()) 
    { 
     list.add(j.Value()); 
    } 

    actualList.Sort(); 

    items.Clear(); 
    for (int i = 0; i < actualList.Count;i++) 
    { 
     items.Add(actualList[i]); 
    } 
} 

Answer 3

링크 된 목록의 빠른 정렬은 일반적으로 배열의 빠른 정렬과 약간 다릅니다. 첫 번째 노드의 데이터 값을 피벗 값으로 사용하십시오. 그런 다음 코드는 세 개의 목록을 만듭니다. 하나는 < 피벗, 하나는 값 == 피벗, 하나는 값> 피벗입니다. 그런 다음 < 피벗 및> 피벗 목록에 대한 재귀 호출을 수행합니다. 재귀 호출이 이들을 반환하면 3 개의 목록이 정렬되므로 코드는 3 개의 목록 만 연결하면됩니다.

목록의 연결 속도를 높이려면 마지막 노드에 대한 포인터를 추적하십시오. 이를 단순화하려면 순환 목록을 사용하고 목록에 액세스하는 주요 방법으로 마지막 노드에 대한 포인터를 사용하십시오. 이렇게하면 (조인) 목록을 더 간단하게 추가 할 수 있습니다 (스캔하지 않음). 함수 안에 들어가면 last-> next를 사용하여 목록의 첫 번째 노드에 대한 포인터를 가져옵니다.

최악의 경우 데이터 패턴 중 2 개가 이미 정렬 된 데이터이거나 이미 역순으로 정렬 된 데이터입니다. 마지막 노드에 대한 포인터가있는 순환 목록 방법을 사용하면 마지막 노드와 첫 번째 노드의 평균을 도움이 될 수있는 2의 중앙값으로 사용할 수 있습니다 (노드 == 피벗의 목록이 비어있게 될 수 있습니다).

최악의 경우의 시간 복잡도는 O (n^2)입니다. 최악의 스택 사용은 O (n)입니다. 목록 < 목록 및 목록> 피벗 중 작은 것에서 재귀를 사용하면 스택 사용량을 줄일 수 있습니다. 돌아온 후, 이제 정렬 된 작은 목록은 목록 == 피벗과 연결되어 네 번째 목록에 저장됩니다. 그런 다음 정렬 프로세스가 나머지 정렬되지 않은 목록을 반복 한 다음 저장된 목록과 병합 (또는 결합)합니다.

bottom up merge sort을 포함한 모든 방법을 사용하여 연결된 목록을 정렬하면 연결된 목록을 배열로 이동하고 배열을 정렬 한 다음 정렬 된 배열에서 연결된 목록을 만드는 것보다 속도가 느려집니다. 그러나 내가 설명하는 빠른 정렬 방법은 연결된 목록이있는 배열 지향 알고리즘을 사용하는 것보다 훨씬 빠릅니다.