Рубрики

Стабильная быстрая сортировка

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

Input : (1, 5), (3, 2) (1, 2) (5, 4) (6, 4)
We need to sort key-value pairs in the increasing order of keys of first digit
There are two possible solution for the two pairs where the key is same i.e. (1, 5) and (1, 2) as shown below:
OUTPUT1: (1, 5), (1, 2), (3, 2), (5, 4), (6, 4)
OUTPUT2: (1, 2), (1, 5), (3, 2), (5, 4), (6, 4)
A stable algorithm produces first output. You can see that (1, 5) comes before (1, 2) in the sorted order, which was the original order i.e. in the given input, (1, 5) comes before (1, 2).

Second output can only be produced by an unstable algorithm. You can see that in the second output, the (1, 2) comes before (1, 5) which was not the case in the original input.

Некоторые алгоритмы сортировки по своей природе стабильны, такие как сортировка вставками, сортировка слиянием, сортировка по пузырям и т. Д. А некоторые алгоритмы сортировки не являются такими, как сортировка по кучи , быстрая сортировка и т. Д.
Быстрая сортировка является нестабильным алгоритмом, потому что мы выполняем обмен элементов в соответствии с положением поворота (без учета их исходного положения).

Как сделать QuickSort стабильным?

Быстрая сортировка может быть стабильной, но обычно она не реализована таким образом. Чтобы сделать его стабильным, требуется либо хранение в порядке N (как в простой реализации), либо немного дополнительной логики для версии на месте.
В приведенной ниже реализации мы используем дополнительное пространство. Идея состоит в том, чтобы сделать два отдельных списка:
1) Первый список содержит элементы меньше, чем пивот.
2) Второй список содержит элементы больше, чем пивот.

# Python код для реализации стабильной быстрой сортировки.
# Код использует средний элемент в качестве точки разворота.

def quickSort(ar):

       

    # Базовый вариант

    if len(ar) <= 1:

        return ar

  

    # Давайте выберем средний элемент стержня

    else:

        mid = len(ar)//2

        pivot = ar[mid]

  

        # ключевой элемент используется для разбиения массива

        # на 2 половинки в соответствии с их значениями

        smaller,greater = [],[]

   

        # Поместите большие элементы в больший список,

        # меньшие элементы в меньшем списке. Также,

        # сравнить позиции, чтобы решить, где поставить.

        for indx, val in enumerate(ar):

            if indx != mid:

                if val < pivot:

                    smaller.append(val)

                elif val > pivot:

                    greater.append(val)

  

                # Если значение одинаково, то учитывая

                # позиция для определения списка.

                else:

                    if indx < mid:

                        smaller.append(val)

                    else:

                        greater.append(val)

        return quickSort(smaller)+[pivot]+quickSort(greater)

      
# Код драйвера для проверки выше

ar = [10, 7, 8, 9, 1, 5

sortedAr = quickSort(ar) 

print(sortedAr)

Выход:

[1, 5, 7, 8, 9, 10]

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

Рекомендуемые посты:

Стабильная быстрая сортировка

0.00 (0%) 0 votes