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

Обычно, когда большинство людей начинают готовиться к интервью, они начинают рассматривать различные алгоритмы сортировки и пытаются запомнить шаги. Цель этой статьи — создать у вас впечатление о быстрой сортировке, чтобы этот алгоритм стал способом решения связанной проблемы, а не просто вопросом для собеседования. Мы сосредоточимся на подходе, который использует быстрая сортировка, и на том, как его можно использовать для решения других задач.

Итак, в чем основная идея быстрой сортировки? Если мне дан массив из 5 элементов [3,1,4,5,2], быстрая сортировка выберет 1 элемент pivot и поместит все элементы меньше его на одну сторону, а все элементы больше на другой. В этом случае, если мы выберем 2 в качестве стержня.

Первым шагом будет [1,2,4,5,3]. Здесь все элементы больше 2 находятся справа, а элементы меньше 2 слева. Этот процесс называется разметкой.

В быстрой сортировке есть две ключевые идеи: Сведение и Разбиение на разделы.

Разметка

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

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

Представьте, что у нас есть массив [1,2,3,4,5], чтобы сделать границу в массиве, нам нужна переменная bound, которая будет отслеживать индекс элемента, который меньше, чем стержень. Так что мы можем разместить пивот рядом с ним, а все остальные элементы могут следовать за ним.

Результирующая структура должна иметь вид [e1,e2,e3,(связанный/осевой), e4,e5,e6…..], где e1,e2,e3 ‹ стержень ‹ e4,e5,e6.

Мы продолжаем итерации, сравнивая и расширяя границы

верно ли 1‹5?bound++, index++; верно ли 2‹5?bound++, index++; верно ли 3‹5?bound++, index++, и мы дойдем до конца. И граница правильная. 5 — самый большой элемент, а все элементы, меньшие этого, находятся слева. Ничего не поделаешь. Но что происходит, когда массив выглядит следующим образом: [1,2,3,7,4,5]. Попробуем повторить тот же процесс.

верно ли 1‹5?bound++, index++; верно ли 2‹5?bound++, index++; верно ли 3‹5?bound++, index++;

верно ли 7‹5? НЕТ!! Мы не можем увеличивать границу, поскольку граница представляет собой конец элементов, меньших точки поворота. Итак, что нам теперь делать? Как и в реальной жизни, мы продолжим итерацию и пока пропустим увеличение границы, так что, если в будущем мы обнаружим какой-либо другой элемент, меньший, чем точка поворота, мы поменяем местами 7 с этим элементом и увеличить границу на 1. Так что меньший элемент приходит сюда, а этот больший элемент выбрасывается.

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

Итак, снова верно ли 7‹5? НЕТ, поэтому границы index++ остаются прежними. 4‹5 верно? Да, поэтому поменяйте местами 7 и 4, bounds++, index++.

После завершения итерации у нас будут границы, указывающие на раздел. Затем мы просто поменяем местами опорную точку и массив[bound]. Таким образом, точка поворота окажется в правильном положении, а массив будет разбит на разделы.

public int partition(int[] array) {
    int pivot = array[array.length-1];
    int bound = 0; // tracks the boundary
    for(int index = 0 ; index<array.length-1 ; index++) {
        if(array[index] < pivot) {
            swap(array,bound,index); // If bound == index, we can skips swaps also. Not doing it for simplicity.
            bound++;
        }
    }
    swap(array,bound,array.length-1);
    return bound;
}

Вышеприведенный фрагмент с разбиением массива[ 0, длина -1] один раз относился к последнему элементу как к опорному. При быстрой сортировке логически разделите весь массив на несколько небольших подмассивов и повторите это разбиение. Каждый раз, когда выполняется разбиение, точка поворота оказывается в правильном положении. Как же тогда разделить массив? мы делаем это, отмечая младший и старший индексы для данного массива.
[(1,2,3), (4,5)] — мы можем разделить это на 2 массива, имея lowIndex = 0, highIndex = 2 :: lowIndex = 3 , высокий индекс = 4.

Мы должны изменить приведенный выше фрагмент, чтобы он принимал низкие и высокие значения, а не использовал 0 и len-1 в качестве границ. Чтобы мы могли передавать младшие и высокие значения, которые будут представлять срез или подмассив в массиве, на котором должна выполняться логика.

[1,2,3, 4,5] — мы можем разделить это на 2 массива, имея lowIndex = 0, highIndex = 2 :: lowIndex = 3 , highIndex = 4. Мы должны изменить приведенный выше фрагмент, чтобы принять low и high вместо использования 0 и len-1 в качестве границ.

// Modified partitioning logic
public int partition(int[] array,int low, int high) {
    int pivot = array[high];
    int i = low;  // Keeps track of index at which we add an element less        than pivot.
    for(int j = low ; j<high ; j++) {
        if(array[j] < pivot) {
            swap(array,i,j);
            i++;
        }
    }
    swap(array,i,high);
    return i; // returns the index at which partition happened or correct pivot position.

}

Разделение - это то, что делает тяжелую работу в сортировке. Фактическая сортировка - это просто повторяющееся разбиение.

Выводы:

Согласно вики, «алгоритм на месте — это алгоритм, который преобразует входные данные, используя структуру данных с небольшим постоянным объемом дополнительного пространства для хранения».

Мы делим весь массив с помощью индексов и работаем с одним и тем же массивом и не используем никакого дополнительного пространства для сортировки, поэтому быстрая сортировка — это сортировка НА МЕСТЕ. Сортировка на месте не использует никаких дополнительных структур данных для завершения сортировки.

Алгоритм сортировки называется стабильным, если два объекта с одинаковыми ключами появляются в отсортированном выводе в том же порядке, в каком они появляются во входном массиве. для сортировки.

Обмен не включает относительное положение элементов перед обменом. Что важно для сохранения начального порядка элементов, которые равны. В случае примитивов это не важно, потому что у них нет своей идентичности. Например, [1,1,1,1], если мы расположим 1 в любом порядке, все будет одинаковым, но [Целое число (1), Целое число (1), Целое число (1)], все они являются отдельными тождествами, и это важно сохранить порядок этих элементов в структуре сортировки постов. Итак, быстрая сортировка НЕ СТАБИЛЬНА.

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

Быстрая концепция. Чтение из основной памяти является дорогостоящим (длительным, но недорогим с экономической точки зрения) по сравнению с кэшем (который является дорогостоящим с экономической точки зрения, но очень быстрым). Оперативная память разбита на блоки, эти блоки считываются шиной данных как единое целое. Они читают все в этом блоке и заносят его в кеш. Теперь, когда ваш массив читается как непрерывный, скорее всего, весь массив помещается в кеш, поэтому чтения из основного m/m избегаются.

Мы видели, что быстрая сортировка имеет меньшие требования к m/m, но, тем не менее, мы обнаружим, что большая часть реальной сортировки выполняется с использованием сортировки слиянием или некоторой модифицированной версии сортировки слиянием. Почему?

  1. Средняя производительность O(N log N) снижается до O(N²) для патологических входных данных. Но сортировка слиянием имеет O (NlogN) как наихудший случай.
  2. Быстрая сортировка работает нестабильно. Мы не всегда работаем с примитивными целыми числами в реальных случаях использования. Например, у меня есть страница электронной почты, которую необходимо отсортировать по дате, и в этом отсортированном по дате списке я должен отображать электронные письма в алфавитном порядке, отсортированные по идентификатору почты отправителя. Использование быстрой сортировки здесь может не сохранить исходный порядок, созданный после сортировки по дате. Даже в JDK, если мы видим исходный код, Arrays.sort() использует быструю сортировку для примитивов и модифицированную сортировку слиянием для объектов.
  3. Быструю сортировку можно сделать стабильной, учитывая идентификаторы объектов, но для этого потребуется дополнительное пространство O (n) вместе с памятью стека рекурсивных вызовов. В этом случае можно использовать сортировку слиянием, поскольку она по умолчанию стабильна и проще, чем стабильная быстрая сортировка.

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

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

Упрощенный анализ временной и пространственной сложности:

Когда мы делаем разбиение, это линейная операция, так как мы должны выполнять итерацию до конца фрагмента массива, поэтому порядок O (n) простой. Но сколько раз мы должны это делать? Ответ — это количество раз, когда мы делим массив на половины, что соответствует порядку log2n. Итак, говоря простым языком, порядок в среднем равен O(N log N).

Мы рассмотрим поворот и то, как он влияет на производительность во время выполнения, в другой статье. Если вам нравится то, что вы читаете, пожалуйста, нажмите аплодисменты! 50 это предел.

Ваше здоровье!