Почему вставка сортировки всегда опережает сортировку слиянием в этой реализации? - PullRequest
Новая
       28

Почему вставка сортировки всегда опережает сортировку слиянием в этой реализации?

4 голосов
/ 29 ноября 2011

Я не понимаю: почему моя реализация сортировки вставкой опережает сортировку слиянием каждый раз, для любого размера n? 

    public List<Int32> InsertionSort(List<Int32> elements, Boolean ascending = true)
    {
        for (Int32 j = 1; j < elements.Count; j++)
        {
            Int32 key = elements[j];
            Int32 i = j - 1;

            while (i >= 0 && (elements[i].CompareTo(key) > 0) == ascending)
                elements[i + 1] = elements[i--];

            elements[i + 1] = key;
        }

        return elements;
    }

    public List<Int32> MergeSort(List<Int32> elements, Boolean ascending = true)
    {
        Sort(elements, 0, elements.Count - 1);

        return elements;
    }

    private void MergeSort(List<Int32> elements, Int32 startIndex, Int32 count)
    {
        if(startIndex < count)
        {
            Int32 half = (startIndex + count).Divide(2, RoundMethod.Floor);
            Sort(elements, startIndex, half);
            Sort(elements, half + 1, count);
            Merge(elements, startIndex, half, count);
        }
    }

    public List<Int32> Merge(List<Int32> elements, Int32 lowerBound, Int32 half, Int32 upperBound)
    {
        Int32 i = 0;
        Int32 j = 0;

        Int32 lowerElementsCount = half - lowerBound + 1;
        Int32 upperElementsCount = upperBound - half;

        List<Int32> left = new List<Int32>();
        while (i < lowerElementsCount)
            left.Add(elements[lowerBound + i++]);

        List<Int32> right = new List<Int32>();
        while (j < upperElementsCount)
            right.Add(elements[half + j++ + 1]);

        left.Add(Int32.MaxValue);
        right.Add(Int32.MaxValue);

        i = 0;
        j = 0;

        for (int k = lowerBound; k <= upperBound; k++)
            if (left[i] <= right[j])
            {
                elements[k] = left[i];
                i++;
            }
            else
            {
                elements[k] = right[j];
                j++;
            }

        return elements;
    }

Вот мои результаты: 

SORTING 1 ELEMENTS
MERGE-SORT: TIME SPENT: 0ms (1513 ticks)
INSERTION-SORT: TIME SPENT: 0ms (1247 ticks)

SORTING 10 ELEMENTS
MERGE-SORT: TIME SPENT: 1ms (2710 ticks)
INSERTION-SORT: TIME SPENT: 0ms (3 ticks)

SORTING 100 ELEMENTS
MERGE-SORT: TIME SPENT: 0ms (273 ticks)
INSERTION-SORT: TIME SPENT: 0ms (11 ticks)

SORTING 1000 ELEMENTS
MERGE-SORT: TIME SPENT: 1ms (3142 ticks)
INSERTION-SORT: TIME SPENT: 0ms (72 ticks)

SORTING 10000 ELEMENTS
MERGE-SORT: TIME SPENT: 18ms (30491 ticks)
INSERTION-SORT: TIME SPENT: 0ms (882 ticks)

И код для тестирования: 

    static void Main(string[] args)
    {
        for (int i = 1; i < 100000; i*=10)
        {
            List<Int32> elements = GetFilledList(i, 0, Int32.MaxValue, false);
            Console.WriteLine("SORTING {0} ELEMENTS", elements.Count);

            Stopwatch sw = new Stopwatch();

            //MERGE SORT
            sw.Start();
            new MergeSort().Sort(elements);
            sw.Stop();
            Console.WriteLine("MERGE-SORT: TIME SPENT: {0}ms ({1} ticks)", sw.ElapsedMilliseconds, sw.ElapsedTicks);

            //INSERTION SORT
            sw.Restart();
            new InsertionSort().Sort(elements);
            sw.Stop();
            Console.WriteLine("INSERTION-SORT: TIME SPENT: {0}ms ({1} ticks)", sw.ElapsedMilliseconds, sw.ElapsedTicks);
            Console.WriteLine();   
        }

        Console.ReadKey();
    }

На случай, если кому-то интересно, я получил эти алгоритмы от Введение в алгоритмы, Томас Х. Кормен (Автор),Чарльз Лейзерсон (Автор), Рональд Л. Ривест (Автор), Клиффорд Стейн (Автор)

РЕДАКТИРОВАТЬ: 

    static List<Int32> GetFilledList(Int32 quantity, Int32 lowerBound, Int32 upperBound, Boolean mayRepeat = true)
    {
        List<Int32> numbers = new List<Int32>();

        Random r = new Random();
        for (int i = 0; i < quantity; i++)
        {
            Int32 numero = r.Next(lowerBound, upperBound); 

            while(!mayRepeat && numbers.Contains(numero))
                numero = r.Next(lowerBound, upperBound);

            numbers.Add(numero);
        }

        return numbers;
    }

Ответы [ 3 ]

11 голосов
/ 29 ноября 2011

потому что после сортировки слиянием объекты в элементах уже отсортированы. сделать еще 

elements = GetFilledList(i, 0, Int32.MaxValue, false);

до 

sw.Restart();
2 голосов
/ 29 ноября 2011

сортировка вставки должна быть быстрее сортировки слиянием для небольших входных данных;вот как работает O (N). 

f(n) = O(g(n)) if for all n, greater than n0, f(n) < C * g(n)

Алгоритмы, подобные хорошим сложностям, обычно имеют более высокие значения C, поэтому они не начинают на самом деле опережать «более медленные» алгоритмы, пока вы не получите большие входные данные.

Несмотря на то, что esskar, похоже, нашел основную проблему, с которой вы столкнулись, имейте в виду, что в будущем вам, вероятно, придется тестировать алгоритмы с гораздо более значительными входными данными, чтобы действительно увидеть лучший алгоритм.

2 голосов
/ 29 ноября 2011

Сортировка 10000 элементов недостаточно для эффективной оценки алгоритма. Иди больше.

Кроме того, случайный вход? Опубликуйте вашу реализацию GetFilledList

И вам нужно отменить сортировку elements перед выполнением сортировки вставкой (или просто повторно инициализировать elements).

Если вы измените порядок сортировки, что произойдет? Я предполагаю, что вы выполняете всю работу в mergesort, а затем сортировка вставок просто сортирует уже отсортированный список , который на самом деле очень хорош (O (n), при условии разумной реализации).

...