.NET의`Array.Sort ()`메서드에서 사용하는 정렬 알고리즘이 안정적인 알고리즘입니까?

.NET의`Array.Sort ()`메서드에서 사용하는 정렬 알고리즘이 안정적인 알고리즘입니까?

---

.NET의 Array.Sort()방법에서 사용하는 정렬 알고리즘 이 안정적인 알고리즘입니까?

---

에서 MSDN :

이 구현은 불안정한 정렬을 수행합니다. 즉, 두 요소가 같으면 순서가 유지되지 않을 수 있습니다. 반대로 안정적인 정렬은 동일한 요소의 순서를 유지합니다.

정렬은 내성적 정렬을 사용합니다. (.NET Framework 버전 4.0 및 이전 버전의 Quicksort).

안정적인 정렬이 필요한 경우 Enumerable.OrderBy 를 사용할 수 있습니다 .

---

Rasmus Faber의 답변에 추가 ...

Enumerable.OrderBy 및 Enumerable.ThenBy 를 통한 LINQ의 정렬은 안정적인 정렬 구현으로, Array.Sort 대신 사용할 수 있습니다 . 에서 MSDN에서 이상 Enumerable.OrderBy 문서 :

이 방법은 안정적인 정렬을 수행합니다. 즉, 두 요소의 키가 같으면 요소의 순서가 유지됩니다. 반대로 불안정한 정렬은 동일한 키를 가진 요소의 순서를 유지하지 않습니다.

또한의 그것과 같은 불안정한 정렬 구현 Array.Sort은 타이 브레이커 역할을하는 추가 키로 소스 시퀀스 또는 배열의 요소 위치를 사용하여 안정화 할 수 있습니다. 다음은 단일 차원 배열의 일반 확장 메서드 Array.Sort로서 안정적인 정렬로 전환 되는 이러한 구현 중 하나입니다 .

using System;
using System.Collections.Generic;

public static class ArrayExtensions {

    public static void StableSort<T>(this T[] values, Comparison<T> comparison) {
        var keys = new KeyValuePair<int, T>[values.Length];
        for (var i = 0; i < values.Length; i++)
            keys[i] = new KeyValuePair<int, T>(i, values[i]);
        Array.Sort(keys, values, new StabilizingComparer<T>(comparison));
    }

    private sealed class StabilizingComparer<T> : IComparer<KeyValuePair<int, T>> 
    {
        private readonly Comparison<T> _comparison;

        public StabilizingComparer(Comparison<T> comparison) {
            _comparison = comparison;
        }

        public int Compare(KeyValuePair<int, T> x, 
                           KeyValuePair<int, T> y) {
            var result = _comparison(x.Value, y.Value);
            return result != 0 ? result : x.Key.CompareTo(y.Key);
        }
    }
}

아래는 StableSort위에서 사용한 샘플 프로그램입니다 .

static class Program 
{
    static void Main() 
    {
        var unsorted = new[] {
            new Person { BirthYear = 1948, Name = "Cat Stevens" },
            new Person { BirthYear = 1955, Name = "Kevin Costner" },
            new Person { BirthYear = 1952, Name = "Vladimir Putin" },
            new Person { BirthYear = 1955, Name = "Bill Gates" },
            new Person { BirthYear = 1948, Name = "Kathy Bates" },
            new Person { BirthYear = 1956, Name = "David Copperfield" },
            new Person { BirthYear = 1948, Name = "Jean Reno" },
        };

        Array.ForEach(unsorted, Console.WriteLine);

        Console.WriteLine();
        var unstable = (Person[]) unsorted.Clone();
        Array.Sort(unstable, (x, y) => x.BirthYear.CompareTo(y.BirthYear));
        Array.ForEach(unstable, Console.WriteLine);

        Console.WriteLine();
        var stable = (Person[]) unsorted.Clone();
        stable.StableSort((x, y) => x.BirthYear.CompareTo(y.BirthYear));
        Array.ForEach(stable, Console.WriteLine);
    }
}

sealed class Person 
{
    public int BirthYear { get; set; }
    public string Name { get; set; }

    public override string ToString() {
        return string.Format(
            "{{ BirthYear = {0}, Name = {1} }}", 
            BirthYear, Name);
    }
}

다음은 위 샘플 프로그램의 출력입니다 (Windows Vista SP1 및 .NET Framework 3.5 SP1이 설치된 컴퓨터에서 실행 됨).

{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1956, Name = David Copperfield }
{ BirthYear = 1948, Name = Jean Reno }

{ BirthYear = 1948, Name = Jean Reno }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1956, Name = David Copperfield }

{ BirthYear = 1948, Name = Cat Stevens }
{ BirthYear = 1948, Name = Kathy Bates }
{ BirthYear = 1948, Name = Jean Reno }
{ BirthYear = 1952, Name = Vladimir Putin }
{ BirthYear = 1955, Name = Kevin Costner }
{ BirthYear = 1955, Name = Bill Gates }
{ BirthYear = 1956, Name = David Copperfield }

---

다른 답변에서 언급했듯이 Array.Sort는 안정적이지 않습니다. 그러나 LINQ OrderBy 메서드 (및 OrderByDescending 등) 는 안정적이므로 매우 유용 할 수 있습니다.

---

아니요, 아닙니다 .

This method uses the QuickSort algorithm. This implementation performs an unstable sort

---

UPDATE: This code not stabilizing Array.Sort (ensure that the elements are always sorted in the same order):

public static class ComparisonExtensions
{
    public static Comparison<T> WithGetHashCode<T>(this Comparison<T> current)
    {
        return (x, y) =>
        {
            var result = current(x, y);
            if (result == 0)
                return x.GetHashCode() - y.GetHashCode();
            return result;
        };
    }
}

Use:

Comparison<Person> comparison = (x, y) => x.BirthYear.CompareTo(y.BirthYear);
Array.Sort(unstable, comparison.WithGetHashCode());

참고URL : https://stackoverflow.com/questions/148074/is-the-sorting-algorithm-used-by-nets-array-sort-method-a-stable-algorithm