Описание взято из книги "Алгоритмы Построение и Анализ" Т Кормен, Ч Лейзерсон, Р. Ривест, К. Штайн :
Быстрая сортировка, подобно сортировке слиянием, основана на парадигме "разделяй и властвуй", представленной в разделе 2.3.1. Ниже описан процесс сортировки подмассива А[p..r], состоящий, как и все алгоритмы с использованием декомпозиции, из трех этапов.
Разделение.
Массив А[p..r] разбивается (путем переупорядочения его элементов) на два (возможно, пустых) подмассива A[p..q-1] и A[q..r]. Каждый элемент подмассива A[p..q-1] не превышает элемент A[q], а каждый элемент подмассива A[q+1..r] не меньше элемента A[q]. Индекс q вычисляется в ходе процедуры разбиения.
Покорение.
Подмассивы A[p..q-1] и A[q+l..r] сортируются путем рекурсивного вызова процедуры быстрой сортировки.
Комбинирование.
Поскольку подмассивы сортируются наместе, для их объединения не нужны никакие действия: весь массив А[p..r] оказывается отсортирован.
Массив сортируется рекурсивно вызывая функцию quicksort с параметрами : ссылка на массив, левый индекс, с которого надо начинать сортировку и правый индекс, до которого включительно сортировать.
Далее проверяется, если необходимо отсортировать только одно число — то выходим из данной функции, а если необходимо отсортировать всего два числа, то проверяется , что левое должно быть меньше , чем правое, иначе они меняются местами.
В остальных случаях средний элемент, выбирается за опорный и движемся слева и справа индексами к нему оставляя слева нетронутыми элементы массива, которые меньше опорного, а справа которые больше опорного.
Когда встречаются элементы слева и справа не удовлетворяющие данному условию идет проверка на то, что оба индекса не дошли до опорного элемента, и если это так, то они меняются местами. Если индекс справа дошел до опорного, а левый указывает на элемент, который НЕ меньше опорного , то этот элемент перемещается вправо от опорного. Еcли индекс слева дошел до опорного, а правый индекс указывает на элемент, который НЕ больше опорного , то этот элемент перемещается влево от опорного.
Далее когда оба индекса указывают на опорный элемент функция рекурсивно вызывается для "подмассива" стоящего слева от опорного и "подмассива" стоящего справа от опорного. Функция будет повторяться пока части слева и справа не станут равны одному элементу.
Исходный текст приложен в файле quicksort.pl
Входные данные содержатся в файле input.txt в текущем каталоге. В первой строке файла содержится число N. Во второй строке - набор чисел, отделенных символом «,» (запятая). Также в разделителе может использоваться любое количество пробелов. В случае если во второй строке содержится более N чисел, следует брать для сортировки первые N чисел.
0≤N≤10000
Пример входных данных лежит в файле input.txt.
В результате своей работы программа должна создать файл в текущем каталоге с именем output.txt. В файле должны быть перечислены N отсортированных по возрастанию чисел, каждое число на новой строке.
#!/usr/bin/perl -w #################### #Shpatserman Maria #28.05.2009 #Quick Sort Algoritm #################### use strict; use warnings; ###Функция сортирует подмасcив с L_index по H_index### sub quicksort { ###Чтение входных данных ссылки на массив,### ###начального индекса, конечного индекса соответственно## my ($array, $L_index, $H_index) = @_; ###Если для сортировки передан только один элемент или менее выходим### if (($H_index - $L_index) <=0) { return;} ###Если передано 2 элемента то проверяем кто меньший и при необходимости ## ###меняем порядок и выходим из функции### elsif (($H_index - $L_index)== 1) { if ($array->[$H_index] < $array->[$L_index]) { ($array->[$H_index], $array->[$L_index]) = ($array->[$L_index], $array->[$H_index]); return; } } ###За опорный берем средний элемент### ###Сохраняем индекс среднего элемента### my $pivot_index =int(($H_index+$L_index)/2); my $pivot = $array->[$pivot_index]; my $i = $L_index; my $j = $H_index; ###Начинаем двигаться от краев к опорному элементу слева и справа### do { ###Слева пропускаем элементы меньшие, чем опорный### while ($array->[$i] < $pivot) { $i++; } ###Справа пропускаем элементы большие, чем опорный### while ($array->[$j] > $pivot) { $j--; } ###Нашли элементы , которые не удовлетворяют этим требованиями### if ($i < $j ) { ###Если оба индекса не указывают на опорный,### ###то меняем их местами и сдвигаемся на шаг к опорному### if (($i != $pivot_index) && ($j != $pivot_index)) { ($array->[$i], $array->[$j]) = ($array->[$j], $array->[$i]); $i++; $j--; } ###Если левый индекс указывает на опорный, а правый на элемент,### ###который НЕ больше, чем опорный, то### ###вставляем этот элемент в левую часть, а справа удаляем### elsif ($i == $pivot_index) { splice (@$array, $L_index, 0, $array->[$j]); splice (@$array, $j+1, 1); $pivot_index++; $i++; } ###Если правый индекс указывает на опорный, а левый на элемент,### ###который НЕ меньше, чем опорный, то### ###вставляем этот элемент в правую часть, а слева удаляем### elsif ($j == $pivot_index) { splice (@$array, $H_index+1, 0, $array->[$i]); splice (@$array, $i, 1); $pivot_index--; $j--; } } } while ($i < $j);###Делаем пока не достигнем опорного индекса### ###После достижения опорного индекса### ###Если в левой части более одного элемента, то вызываем ### ###функцию сортировки для левой части### if ($L_index < ($pivot_index - 1)) { quicksort($array, $L_index, $pivot_index-1); } ###Если в правой части более одного элемента, то вызываем ### ###функцию сортировки для правой части### if ($H_index > ($pivot_index +1)) { quicksort($array, $pivot_index+1, $H_index); } }
###Заполнение массива из N чисел из файла### sub read_array { ###Чтение входных данных функции : ссылки на массив и имени файла ### ###соответственно### my ($array, $file_name) = @_; open (INPUT_FILE, "$file_name") || die "Could not open $file_name file\n"; ###Первая строка в файле — число элементов N в массиве### my $Lenght = <INPUT_FILE>; chomp($Lenght); ###Вторая строка содержит непосредственно целые числа для сортировки### my $line = <INPUT_FILE>; chomp($line); my $i=0; ###Заполняем массив для сортировки из N чисел### while (($line =~ /(\d+)/g )&&($i<$Lenght)) { $array->[$i]=$1; $i++; } close INPUT_FILE; } ###Отсортированный массив целых N чисел записываем в выходной файл### sub print_file { ###Чтение входных данных функции: ссылки на массив, имени выходного файла и ### ###индекса последнего N-го элемента соответственно### my ($array, $file_name, $H_index) = @_; open (OUTPUT_FILE, ">$file_name") || die "Could not open $file_name file\n"; ###Записываем в файл N чисел , каждое на новой строке### for(my $i=0;$i<=$H_index;$i++){ print OUTPUT_FILE "$array->[$i]\n"; } close OUTPUT_FILE; } ###Переменная — массив для сортировки### my @data_array ; ###Заполнение массива из файла### read_array(\@data_array, "input.txt"); ###Сортировка массива от первого до последнего элемента включительно### quicksort(\@data_array,0 , $#data_array); ###Запись отсортированного массива в файл### print_file(\@data_array, "output.txt", $#data_array);
Исходный текст программы: quicksort.pl.
Пример входных данный: input.txt.