Понимание сортировки

Хорошо, достаточно с причудливой математикой и символами, в основном это означает, что если у нас есть последовательность,  {3, 2, 1}выполняющая это через алгоритм сортировки, даст нам  {1, 2, 3}, не действительно ракетостроение, верно?

Простейший алгоритм сортировки, который я реализовал ранее, — это пузырьковая сортировка, и работает он так: работает цикл, который сравнивает каждый элемент в списке друг с другом до тех пор, пока весь список не будет отсортирован. В лучшем случае все отсортировано, и мы сделали «супер быстро», в худшем случае это займет очень много времени, по крайней мере, по сравнению с тем, что мы можем сделать, чтобы улучшить его. Вы помните подход «разделяй и властвуй», о котором мы говорили ранее? Где мы делим что-то на более мелкие части, чтобы решить большую загадку? Когда мы говорили об этом, мы говорили о возможности сверхскоростного поиска в телефонной книге, разделив ее пополам снова и снова.

Я собираюсь немного отойти от темы и поговорить о чем-то, что мне кажется довольно интересным. Это действительно имеет отношение к сортировке, вы поймете, почему позже. Имеется телефонная книга с 2 ^ 32 записями, которые, как мы предполагаем, отсортированы. Сколько попыток нам понадобится, чтобы найти 1 из этих записей? Мы говорили о сложности и раньше O(log n). Это означает, что вы можете просто сделать,  log(2^32) и вы получите 32! Это означает, что мы должны сделать 32 проверки, чтобы найти значение в отсортированной коллекции из 2 ^ 32 элементов. Кстати, так что нет никакой путаницы, когда я говорю о том, что  log() это на самом деле  log2(), следовательно, используя базу 2.

Так почему это интересно? Оказывается, что если мы напишем дерево повторений для этого метода, высота дерева будет равна,  log(n) и почему это интересно, ну, вам просто нужно читать, пока мы не рассмотрим сортировку слиянием.

Сортировка слиянием!

Возвращаясь к сортировке слиянием, этот алгоритм использует подход «разделяй и властвуй». Это происходит путем разделения входной последовательности на более мелкие части, пока не останется только один элемент. Учтите , что мы имеем следующую последовательность  {3, 6, 5, 1} при выполнении этого над разделяй и властвуй подходе первый проход даст нам две последовательности со следующими данными:  {3, 6} {5, 1}. Поскольку базовый вариант, остался только один элемент, еще не достигнут, мы продолжаем движение, и в конце мы получим каждый элемент в своих списках. Я собираюсь немного поразить вас, если вы напишите весь процесс на бумаге, вы увидите, что, как только разделение будет полностью выполнено, и вы окажетесь в положении, где у вас есть только 1 элемент в каждом списке, высота этого дерево на вашей бумаге будет  log(n) где n это количество элементов. Это означает, что если у вас есть последовательность из 8 чисел, у вас будет 3 шага, потому что  log(8) равен 3, а 2 ^ 3 равно 8.

Не имеет никакого смысла? Хорошо, посмотрите на эту иллюстрацию (простите мои навыки письма):

По крайней мере, я нахожу это довольно круто, и, глядя на это, я уверен, что это помогает понять, почему алгоритм имеет сложность во времени.

Когда вы находитесь на дне разделения, что вы делаете? Пока что мы не сделали ничего, что оправдывало бы название «слияние». Точно! Потому что следующий шаг сделает именно это. Он объединит два списка вместе, и это станет интересным, если это уже не было интересно.

Допустим, метод слияния принимает два параметра, которые мы оставили и справа. Мы можем предположить, что и левый, и правый список отсортированы, и теперь мы хотим объединить их вместе. Вы можете спросить себя, как мы можем предположить, что они отсортированы, когда мы ничего не сделали? Позвольте мне сказать вам, когда мы впервые достигаем слияния, сколько элементов у нас в каждом подмножестве? Если вы догадались 2, вы ошиблись, это 1. Так что если в каждом списке есть только один элемент, они рассматриваются как отсортированные. Теперь, когда мы объединяем наши первые два элемента, мы убедимся, что список, который мы возвращаем из слияния, отсортирован.

Теперь может быть немного трудно обдумать это, не глядя на некоторый псевдокод, поэтому давайте сделаем это. Вот основная функция, которая дает нам обзор того, что происходит:

Единственное, что может показаться немного странным, — это «вещь», которую мы говорим передать,  MergeSort когда мы называем это рекурсивно. Я просто определяю два подмножества массива, который передается методу, первый займет первую половину, второй — вторую. Это означает, что левый и правый будут иметь правильную сторону массива. Двоеточие определяет, где начать принимать элементы.

Глядя на этот код и просматривая последовательность, которую мы хотим отсортировать (давайте возьмем одну из картинки),  {8,7, 6, 5, 4, 3, 2, 1} мы знаем, что при первом достижении  Merge слева будет коллекция с одним элементом,  {8} а справа будет коллекция с одним элементом  {7}. Когда функция слияния выполняется с двумя независимо отсортированными списками, она возвращает отсортированное подмножество, а затем, когда все это будет сделано, мы получим отсортированную версию нашего списка.

Он начинает становиться немного интереснее, когда мы возвращаемся к тому, что список почти слит, когда на последнем уровне и окончательном слиянии у нас будут два следующих значения слева и справа:

Слияние теперь начнет обрабатывать это, когда это был всего 1 элемент в каждом, сравнение в слиянии было простым, мы могли бы сделать это с помощью всего одного оператора if. Теперь все становится немного сложнее. Глядя на это, мы понимаем, что хотим переместить всю правую часть перед левой. Нам все еще нужно убедиться, что каждый элемент находится в правильном положении. Итак, нам нужно указать на текущий левый и текущий правый индексы, которые мы сравниваем, потому что может случиться так, что нам нужно взять два значения справа, прежде чем мы коснемся левого. Обратите внимание на то, что я говорю «возьми здесь», один из недостатков сортировки слиянием — это то, что она занимает больше памяти, она не на месте и фактически, в соответствии с курсом MIT, который я связывал есть статья, которая проанализировала сортировку слиянием на месте и пришла к выводу, что она будет работать намного хуже, чем эта реализация.

Все это означает , что у нас есть две переменные, будем называть их  i и  j и каждый раз , когда мы находим меньший объект мы двигаемся , что в списке результатов. В нашем случае это означает, что мы сначала переместим все из правого списка в наш новый список, прежде чем мы переместим что-либо из левого.

Посмотрите на эту разбивку в  псевдокоде  того, что происходит, и это может иметь больше смысла:

i = 0
j = 0

result = []

if left[i] < right[j]   // 5 < 1
    result.add(left[i])
    i ++
else
    result.add(right[i]) // Adds 1 to the result
    j ++

// j is now 1
// i is still 0
if left[i] < right[j]   // 5 < 2
    result.add(left[i])
    i ++
else
    result.add(right[i]) // Adds 2 to the result
    j ++

// j is now 2
// i is still 0
if left[i] < right[j]   // 5 < 3
    result.add(left[i])
    i ++
else
    result.add(right[i]) // Adds 3 to the result
    j ++

// .... All items from right are added to the result

result.add(left[i:])

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

Начнем с того, что мой взгляд на реализацию, о  MergeSort которой вы, возможно, уже поняли, довольно прост:

int[] MergeSort(int[] input)
{
    if(input.Length <= 1) return input;
    
    var left  = MergeSort(input.Take(input.Length / 2).ToArray());
    var right = MergeSort(input.Skip(input.Length / 2).ToArray());
    
    return Merge(left, right);
}

Можете ли вы придумать способ оптимизировать это здесь? Мы действительно бьем память здесь, что не очень хорошо. Это создаст маленькую копию (или большую в зависимости от размера массива) при каждом вводе слева и справа. В идеале вы хотите отслеживать текущую позицию слева и справа вместо того, чтобы фактически разрезать и скопировать массив, который использует намного больше памяти и ресурсов. Помните, что мы говорим об этом концептуально, и мы пытаемся найти лучший способ реализации вещей, так мы становимся лучше.

Скажу вам, я оставлю вас оптимизировать эту часть здесь, вам нужно будет также изменить часть слияния, чтобы она работала. Если вы можете написать элегантное решение и дать хорошее объяснение в поле для комментариев ниже, вы можете выиграть цифровую копию моей книги.

Теперь давайте перепрыгнем и посмотрим, как будет выглядеть слияние с точки зрения реализации. Мы уже говорили о том, что происходит за кулисами здесь. В соответствии с нашим псевдокодом, который мы видели чуть раньше, мы настраиваем временный список, который мы собираемся заполнить отсортированными значениями, или, скорее, слить по порядку! Мы также видели, что нам понадобятся две переменные, чтобы отслеживать, где мы находимся в сортировке, поэтому заглушка метода будет выглядеть примерно так, мы заполняем пробелы в секунду:

int[] Merge(int[] left, int[] right)
{
    var result = new List<int>();
    int j = 0;
    
        // Magic goes here
    
    return result.ToArray();
}

Мы собираемся заполнить список значениями по порядку, а это значит, что нам нужно найти их по левой и правой части. Мы начнем с указания на два места, по одному слоту в каждом массиве, который мы объединяем. Это означает, что мы будем отслеживать положение, в котором мы сейчас находимся, как в левой, так и в правой части. Теперь подумайте об этом так, мы собираемся предположить, что левый и правый отсортированы, поэтому нам не нужно беспокоиться о том, что они вышли из строя. Итак, что мы можем сделать, так это сразу пройтись по каждому элементу и сравнить его с тем, что находится в правильном массиве.

Что происходит, если текущий левый элемент меньше, чем правый? Ну, это означает, что нам нужно добавить это в массив результатов. Однако, если произойдет обратное, нам нужно сделать что-то большее. Учтите, что мы запускаем это в цикле, а  forточнее в -loop. В каждой итерации мы увеличиваем  iнаш указатель на текущий элемент в нашем левом массиве. С j другой стороны, локальная переменная  будет поддерживать указатель на то место, где мы находимся в правильном массиве. Таким образом, это означает, что если мы находим элемент в правом массиве, который меньше, чем слева, мы не хотим увеличивать его  i, потому что мы все еще хотим знать, меньше ли текущий левый элемент, чем следующий правый.

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

for(int i = 0; i < left.Length; i++)
{
    if(right.Length <= j || left[i] < right[j])
    {
        result.Add(left[i]);
    }
    else
    {
        result.Add(right[j]);
        j++;
        i--;
    }
}

As you see, when the right element is smaller, we maintain the value of the current index in the left array and just increment the one used to reference the element in the right array. Notice one more thing here, we are checking if there are still elements to analyse in the right portion, why are we doing this? Remember that all the elements in each array are sorted, so when there are no more elements in the right array, we can just move everything over from the left array to the result.

The same applies to when this process has finished, what happens if there are elements left in the right array? We are just going as long as we have elements in the right array. So in order for us to move the elements from the right array, if there are any, to the results array, we can do this:

for(; j < right.Length; j ++)
{
    result.Add(right[j]);
}
Let’s now look at the entire implementation of the merge method:

int[] Merge(int[] left, int[] right)
{
    var result = new List<int>();
    int j = 0;
    
    for(int i = 0; i < left.Length; i++)
    {
        if(right.Length <= j || left[i] < right[j])
        {
            result.Add(left[i]);
        }
        else
        {
            result.Add(right[j]);
            j++;
            i--;
        }
    }
    
    for(; j < right.Length; j ++)
    {
        result.Add(right[j]);
    }
    
    return result.ToArray();
}

At the end of the merge process and at the end of running our merge sorting, we’ve gone over a complete processes looking what we can see in this illustration:

Here’s a complete example that you can run and experiment with, try and compare the time it takes if you write something like Bubble Sort!

void Main() 
{
    var array = Enumerable.Range(0, 10000).OrderBy (e => Guid.NewGuid());
    
    var result = MergeSort(array.ToArray());
}

int[] MergeSort(int[] input)
{
    if(input.Length <= 1) return input;
    
    var left = MergeSort(input.Take(input.Length / 2).ToArray());
    var right = MergeSort(input.Skip(input.Length / 2).ToArray());
    
    return Merge(left, right);
}

int[] Merge(int[] left, int[] right)
{
    var result = new List<int>();
    int j = 0;
    
    for(int i = 0; i < left.Length; i++)
    {
        if(right.Length <= j || left[i] < right[j])
        {
            result.Add(left[i]);
        }
        else
        {
            result.Add(right[j]);
            j++;
            i--;
        }
    }
    
    for(; j < right.Length; j ++)
    {
        result.Add(right[j]);
    }
    
    return result.ToArray();
}

Merge sort runs in O(n log n), comparing this to something like bubble sort which is O(n^2) is pretty fun and a good exercise. However, don’t forget that merge sort uses extra memory and in the examples I have given above, I have not optimized the memory footprint, that’s up to you to play with! There are a lot of different and fun sorting algorithms including for instance quick sort and heap sort.

I hope you enjoyed this and have a better understanding of merge sort and sorting in general. Do you have a favorite sorting algorithm?

The post Understanding Sorting appeared first on Filip Ekberg’s blog.