Анализ эффективности быстрой сортировки
В среднем число операций порядка N?log2N, остальные сортировки в среднем N2 операций.
Преимущество быстрой сортировки проявляется при больших N. Она сортирует массив с элементами в обратном порядке практически с такой же скоростью, как уже отсортированный массив.
Принцип быстрой сортировки
Причина неэффективности метода сортировки обменом (метод «пузырька») в том, что меняются местами два соседних элемента, если для них нарушена упорядоченность. Менять местами надо максимально удаленные элементы.
Алгоритм одного шага быстрой сортировки
1) Положить i=1, j=N2) Выбрать в массиве случайным образом элемент x.3) ПовторятьПросматривая массив слева направо, найти элемент Aix.Просматривая массив справа налево, найти элемент Aj | Пример одного шага быстрой сортировки ![]() |
Для сортировки массива надо то же самое проделать с обеими частями (слева и справа от x), затем с частями этих частей и т.д. до тех пор, пока каждая часть не будет содержать только один элемент. Получили рекурсивный алгоритм.
procedure QSort(L,R:integer);//L, R – индексы самого левого и самого правого элементов подмассива
var i,j,x,w:integer;
begin
i:=L; j:=R;
x:=A[(L+R) div 2]; //x — средний элемент
repeat
while A[i]
while A[j]
if i
begin //Перестановка A[i] и A[j]
w:=A[i];
A[i]:=A[j];
A[j]:=w;
i:=i+1; j:=j-1
end
until ij;
if L
if iR then QSort(i,R) //Рекурсивный вызов для правой половины массива
End;
begin… Sort(1,N); . . .
End.
Задача о Ханойских башнях
Имеется башня из n дисков различного диаметра, нанизанных на один из трех стержней. Требуется построить аналогичную башню на другом стержне с использованием третьего при выполнении двух условий:
— перемещать можно только один диск;
— на диске меньшего диаметра нельзя помещать диск большего диаметра.
Трудолюбивые буддийские монахи день и ночь переносят диски со стержня на стержень. Легенда утверждает, что когда монахи закончат свою работу, наступит конец света. Для решения задачи с 64 дисками потребуется (264 – 1) перемещений. Поэтому конец света по легенде произойдет по истечении более 5 миллиардов веков, если считать, что один диск перемещается за одну секунду. Задачу и легенду для неё придумал в 1883 г. французский математик Э. Люка.
program Towers;{Перемещение с А на С, В — промежуточный}var N : integer; {число дисков}procedure Move(n:byte; A, C, B : char);beginif n=1 then writeln(A,’-’, C)else beginMove(n-1, A, B, C);writeln(A,’-’, C);Move(n-1, B, C, A)endend;beginwrite(’Число дисков=’); readln(N);Move(N, ’A’, ’C’, ’B’)end. | ![]() |
Указатели
Указательные типы
Указателем называется переменная указательного типа, в которой хранится адрес некоторого объекта (например, переменной). Говорят, что указатель указывает или ссылается на другую переменную. | ![]() |
Указатель занимает в памяти 4 байта.
Нулевой указатель – это указатель, который не ссылается ни на какой объект.
Для его обозначения служит константа Nil.
В языке Pascal различают два вида указателей:
1) бестиповые указатели, которые могут содержать адреса переменных любого типа. Они объявляются через стандартный указательный тип pointer, например: var p:pointer;
2) типизированные указатели, которые могут указывать на переменные только определенного типа; этот тип называется базовым типом для этих указателей. Далее будем рассматривать только типизированные указатели.
Статьи к прочтению:
Быстрая сортировка ( сортировка Хоара )
Похожие статьи:
-
Лабораторная работа №1 Методы сортировки Цель работы Цель данной работы: изучить различные методы сортировки; научиться проводить сравнительный анализ…
-
Быстрая сортировка — упорядочение за среднее время о(n log n).
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы (Алгоритм, приведённый ниже, неверен: если в массиве оказалось два…