Статьи

Алгоритм недели: сортировка по радиксу

Ноябрь 23, 2018

Алгоритмы всегда зависят от ввода. Мы видели, что алгоритмы сортировки общего назначения, такие как сортировка вставками, сортировка по пузырькам и быстрая сортировка, могут быть очень эффективными в одних случаях и неэффективными в других. В самом деле, вставка и пузырьковая сортировка считаются медленными, с наилучшей сложностью O (n 2 ), но они весьма эффективны, когда входные данные достаточно отсортированы. Таким образом, когда у вас есть отсортированный массив и вы добавляете некоторые «новые» значения в массив, вы можете довольно эффективно сортировать его с помощью вставки. С другой стороны, быстрая сортировка считается одним из лучших алгоритмов сортировки общего назначения, но, хотя это отличный алгоритм, когда данные рандомизируются, он практически такой же медленный, как пузырьковая сортировка, когда входные данные почти или полностью отсортированы.

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

Поскольку входные данные очень важны для эффективности алгоритма, мы можем спросить, существуют ли какие-либо алгоритмы сортировки, которые быстрее, чем O (n.log (n)), что представляет собой сложность среднего случая для сортировки слиянием и быстрой сортировки. И ответ — да, есть более быстрые алгоритмы линейной сложности, которые могут сортировать данные быстрее, чем быстрая сортировка, сортировка слиянием и сортировка по типу heapsort. Но есть некоторые ограничения!

Все звучит замечательно, но мы не можем сортировать какие-либо конкретные данные с линейной сложностью, поэтому вопрос в том, каким правилам должен следовать ввод данных, чтобы они были отсортированы по линейному времени?

Такой алгоритм, который способен сортировать данные за линейное время O (n), является радикальной сортировкой, а область ввода ограничена — он должен состоять только из целых чисел.

обзор

Допустим, у нас есть массив целых чисел, который не отсортирован. Поскольку он состоит только из целых чисел и поскольку ключи массива являются целыми числами в языках программирования, мы можем реализовать основную сортировку.

Сначала для каждого значения входного массива мы помещаем значение «1» в ключевое место временного массива, как объяснено на следующей диаграмме.

Если во входном массиве есть повторяющиеся значения, мы увеличиваем соответствующее значение во временном массиве. После «инициализации» временного массива за один проход (с линейной сложностью) мы можем отсортировать входные данные.

Реализация

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

$list = array(4, 3, 5, 9, 7, 2, 4, 1, 6, 5);
 
function radix_sort($input)
{
    $temp = $output = array();
	$len = count($input);
 
    for ($i = 0; $i < $len; $i++) {
		$temp[$input[$i]] = ($temp[$input[$i]] > 0) 
			? ++$temp[$input[$i]]
			: 1;
    }
 
    ksort($temp);
 
    foreach ($temp as $key => $val) {
		if ($val == 1) {
			$output[] = $key; 
		} else {
			while ($val--) {
				$output[] = $key;
			}
        }
    }
 
    return $output;
}
 
// 1, 2, 3, 4, 4, 5, 5, 6, 7, 9
print_r(radix_sort($list));

Проблема в том, что PHP нужен ksort — что совершенно глупо, поскольку мы пытаемся отсортировать массив, используя «другой» метод сортировки, но чтобы преодолеть это, вы должны заранее знать интервал значений и инициализировать временный массив с 0, как в приведенном ниже примере.

define(MIN, 1);
define(MAX, 9);
$list = array(4, 3, 5, 9, 7, 2, 4, 1, 6, 5);
 
function radix_sort(&$input)
{
    $temp = array();
	$len = count($input);
 
	// initialize with 0s
    $temp = array_fill(MIN, MAX-MIN+1, 0);
 
    foreach ($input as $key => $val) {
    	$temp[$val]++;
    }
 
    $input = array();
    foreach ($temp as $key => $val) {
	if ($val == 1) {
		$input[] = $key;
	} else {
		while ($val--) {
			$input[] = $key;
		}
	}
    }
}
 
// 4, 3, 5, 9, 7, 2, 4, 1, 6, 5
var_dump($list);
 
radix_sort(&$list);
 
// 1, 2, 3, 4, 5, 5, 6, 7, 8, 9
var_dump($list);

Здесь входные данные изменяются в процессе сортировки и используются в результате.

сложность

Сложность радикальной сортировки линейна, что в терминах омега означает O (n). Это большое преимущество в производительности по сравнению с O (n.log (n)) или даже хуже с O (n 2 ), как мы можем видеть на следующем графике.

Зачем использовать Radix Sort

1. Это быстро

Radix sort очень быстр по сравнению с другими алгоритмами сортировки, как мы видели на диаграмме выше. Этот алгоритм очень полезен на практике, потому что на практике мы часто сортируем наборы целых чисел.

2. Это легко понять и реализовать

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

Почему НЕ используется радикальная сортировка

1. Работает только с целыми числами

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

2. Требуется дополнительное место

Radix sort требует дополнительного места — по крайней мере, столько же, сколько ввод

Заключительные слова

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

38
Share: