Циклическая сортировка

Циклическая сортировка

Example of cycle sort sorting a list of random numbers. Пример циклической сортировки списка случайных чисел.
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	Θ( н 2 )
Лучшая производительность	Θ( н 2 )
Средняя производительность	Θ( н 2 )
Наихудшая пространственная сложность	Θ( n ) общее, Θ( 1 ) вспомогательное
Оптимальный	Нет

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

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

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

Алгоритм

Чтобы проиллюстрировать идею циклической сортировки, рассмотрим список с отдельными элементами. Учитывая элемент $x$, мы можем найти индекс, по которому это произойдет в отсортированном списке , просто подсчитав количество элементов во всем списке, меньших, чем $x$. Сейчас

1. Если элемент уже находится в правильном положении, ничего не делайте.
2. Если это не так, мы запишем его на предполагаемое место. В этой позиции обитает другой элемент $y$, который нам затем нужно переместить в правильное положение. Этот процесс перемещения элементов в правильное положение продолжается до тех пор, пока элемент не будет перемещен в исходное положение. $x$. Это завершает цикл.

Цикл перемещения списка «bdeac» при перемещении первой буквы b в правильное положение:

Повторение этого процесса для каждого элемента сортирует список с помощью одной операции записи тогда и только тогда, когда элемент еще не находится в правильном положении. Вычисление правильных позиций занимает $O(n)$ время для каждого отдельного элемента, что приводит к использованию алгоритма квадратичного времени, а количество операций записи сводится к минимуму.

Выполнение

Чтобы создать работающую реализацию на основе приведенного выше плана, необходимо решить две проблемы:

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

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

Питон

def cycle_sort(array) -> int:
    """Sort an array in place and return the number of writes."""
    writes = 0

    # Loop through the array to find cycles to rotate.
    # Note that the last item will already be sorted after the first n-1 cycles.
    for cycle_start in range(0, len(array) - 1):
        item = array[cycle_start]

        # Find where to put the item.
        pos = cycle_start
        for i in range(cycle_start + 1, len(array)):
            if array[i] < item:
                pos += 1

        # If the item is already there, this is not a cycle.
        if pos == cycle_start:
            continue

        # Otherwise, put the item there or right after any duplicates.
        while item == array[pos]:
            pos += 1

        array[pos], item = item, array[pos]
        writes += 1

        # Rotate the rest of the cycle.
        while pos != cycle_start:
            # Find where to put the item.
            pos = cycle_start
            for i in range(cycle_start + 1, len(array)):
                if array[i] < item:
                    pos += 1

            # Put the item there or right after any duplicates.
            while item == array[pos]:
                pos += 1
            array[pos], item = item, array[pos]
            writes += 1

    return writes

Следующая реализация, написанная на C++, просто выполняет циклическую сортировку массива.

template <typename type_array>
void cycle_sort(type_array *Array, int array_size)
{
	for (int cycle_start = 0; cycle_start < array_size - 1; cycle_start++)
	{
		type_array item = Array[cycle_start];

		int pos = cycle_start;
		for (int i = cycle_start + 1; i < array_size; i++)
			if (Array[i] < item)
				pos += 1;
		if (pos == cycle_start)
			continue;
		while (item == Array[pos])
			pos += 1;

		std::swap(Array[pos], item);

		while (pos != cycle_start)
		{
			pos = cycle_start;
			for (int i = cycle_start + 1; i < array_size; i++)
				if (Array[i] < item)
					pos += 1;
			while (item == Array[pos])
				pos += 1;

			std::swap(Array[pos], item);
		}
	}
}

Оптимизация для конкретной ситуации

Когда массив содержит только дубликаты относительно небольшого количества элементов, с постоянным временем идеальная хеш-функция может значительно ускорить поиск места размещения элемента. ¹ , переключая сортировку с Θ( n ² ) времени до Θ( n + k ) времени, где k — общее количество хэшей. В конечном итоге массив сортируется в порядке хешей, поэтому важно выбрать хэш-функцию, которая обеспечит правильный порядок.

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

Внешние ссылки

^ «Циклическая сортировка: метод линейной сортировки», The Computer Journal (1990) 33 (4): 365-367.

• Первоисточник неограниченного варианта
• Cyclesort — любопытный маленький алгоритм сортировки