.net 4.5 정렬의 비교 수

Question

4.5의 정렬 알고리즘이 4.0에서 변경되었음을 알고 있지만 내성적 인 정렬 구현에 문제가 있다고 생각됩니다. 역순 정렬 목록의 경우에 누군가가 "정렬 된"대소 문자 (예 : 4.0)와 동일한 수의 비교를 기대할 때 불규칙하게 동작하는 것처럼 보입니다. 그 수는 이상하게도 매우 큽니다.

.NET 4 64

랜덤 25,514,058는 20,525,265 정렬 64

랜덤 22,112,103 20,525,285

.NET 4.5 반전 16,935,357을 정렬 31,148,728 반전!

내가 (4.0 및 4.5을 사용하여 컴파일) 비교의 수를 얻기 위해 사용되는 코드는 다음과 같습니다

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace sortTest { 
class Program { 
    class CmpCount : IComparer<int> { 
     private int _count; 
     /// <summary> 
     /// 
     /// </summary> 
     public int Count { 
      get { 
       return _count; 
      } 
     } 



     public int Compare(int x, int y) { 
      _count++; 
      return x.CompareTo(y); 
     } 
    } 
    static void Main(string[] args) { 
     Random rnd = new Random(1234); 
     List<int> list = new List<int>(); 
     for (int i = 0; i < 1000000; i++) { 
      list.Add(rnd.Next()); 
     } 
     CmpCount cmp = new CmpCount(); 
     list.Sort(cmp); 
     int random = cmp.Count; 

     cmp = new CmpCount(); 
     list.Sort(cmp); 
     int sorted = cmp.Count; 

     cmp = new CmpCount(); 
     list.Reverse(); 
     list.Sort(cmp); 
     int reversed = cmp.Count; 

     Console.WriteLine("random {0}, sorted {1}, reversed {2}",random,sorted,reversed); 
    } 
} 
} 

편집 : 나는 소스 코드를 디버깅하고 힙 정렬이 호출되지 않습니다 것으로 보인다. 아마도 특수한 입력이 필요하기 때문에 트리거 할 수 있습니다. 실제로 위의 경우에 4.5 정렬은 실제로 퀵 소트를 수행하고 있습니다.

소스를 빠르게 살펴보면 4.5 quicksort가 더 정교하고 4.5가 가난한 것으로 나타납니다.

정확하게 이해하면 4.5가 이미 정렬 된 목록을 맹목적으로 선호하는 것 같습니다. 아마도 역순으로 정렬 된 목록의 문제 일 것입니다.

Answer 1

.NET의 introsort 구현은 Quicksort를 시작함으로써 시작됩니다. 재귀 깊이가 특정 지점을 초과하면 퀵 정렬이 중지되고 힙 정렬로 시작됩니다.

알고리즘이 부분 정렬을 수행하고 전체 정렬을 수행하기 위해 다시 시작하므로 많은 비교 횟수를 예상하는 것이 무리가 아닙니다.

또한 .NET 퀵실트가 항목을 선택하여 파티션을 분할하는 방법을 알 수 없습니다. 3의 중앙값을 사용하는 것 같습니다. 그러나 임의의 3을 선택합니까? 첫째, 중간, 마지막? 동일한 배열의 두 종류에 대해 분할이 다를 수 있습니다 (따라서 비교 수가 다를 수 있음).

어쨌든 Intortort는 완벽하다고 주장하지 않습니다. 알고리즘이 잠재적 인 최악의 경우를 감지하고 힙 정렬을 사용하는 것이 quicksort를 사용하는 것이 더 빠를지라도 꽤 가능성이 있습니다. Introsort는 최악의 행동을 피하지만 때로는 비 최적의 행동을 나타낼 수 있습니다.

또한 정렬중인 배열이 동일하다는 보장은 없습니다. Random 클래스 구현이 .NET 4와 .NET 4.5간에 변경되지 않았습니까? Random(1234)이 4.0에서와 다른 4.5 시퀀스를 생성 할 수 있습니다. 그렇다면 같은 배열에서 일종의 비교를하지 않을 것입니다.