Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >




НазваниеСортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >
Дата конвертации23.07.2013
Размер445 b.
ТипПрезентации


Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, і , Ј .

  • Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, і , Ј .


Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (ключ сортировки).

  • Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (ключ сортировки).

  • Тип данных ключа должен включать операции сравнения ("=", ">", "<", ">=" и "<=").

  • Задачей сортировки является

  • преобразование исходной последовательности

  • в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа.



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

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

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





В сортировке подсчетом (counting sort) предполагается, что все n входных

  • В сортировке подсчетом (counting sort) предполагается, что все n входных

  • элементов — целые числа, принадлежащие интервалу от 0 до k,

  • где k - некоторая целая константа.



  • Основная идея сортировки подсчетом заключается в том, чтобы для каждого

  • рассматриваемого элемента х определить количество элементов, которые меньше х.

  • С помощью этой информации элемент х можно разместить на той позиции выходного массива, где он должен находиться.



Исходный массив: A[1..n]

  • Исходный массив: A[1..n]

  • Результат: B[1..n]

  • Вспомогательный массив С[0..k]







Временная сложность- O(n+k)

  • Временная сложность- O(n+k)



Массив делится на 2 части:

  • Массив делится на 2 части:

  • Отсортированную и неотсортированную.

  • На каждом шаге берется очередной элемент из неотсортированной части и включается в отсортированную



Простое включение

  • Простое включение

  • Отсортировано начало массива

  • A1, A2, ….,Ai-1

  • Остаток массива

  • Ai,…An – неотсортирован.

  • На очередном шаге Ai включается в отсортированную часть на соответствующее место







Алгоритм имеет сложность

  • Алгоритм имеет сложность

  • O(n2),

  • но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет

  • O(n).





  • Бинарные вставки (число сравнений NlgN)





Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и тд,

  • Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и тд,

  • где h - положительная константа. Таким образом формируется массив, в котором «h- серии» элементов, отстоящих друг от друга на h, сортируются отдельно.

  • Процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1.



Для достаточно больших массивов рекомендуемой считается такая последовательность, что

  • Для достаточно больших массивов рекомендуемой считается такая последовательность, что

  • hi+1=3hi+1, а h1=1.

  • Начинается процесс с hm-2, hm-2 первый такой член последовательности, что

  • hm-2 [n/9].

  • 1, 4, 13, 40, 121…(hi+1=3hi+1)

  • 1, 3, 7, 15, 31 (hi+1=2hi+1)



  • h ←1;

  • while h < N div 9 do h ← h*3 + 1;

  • repeat // цикл по сериям

  • for k ← 1... h do {сортировка k-ой серии}

  • i ← h + k;

  • while i <= N do //вкл. A[i] на свое место в серии

  • x ← A[i]; j ← i - h; //}

  • while (j >= 1) and (A[j]>x) do //сдвиг

  • A[j + h] ← A[j]; j ← j-h);

  • A[j + h] ← x; i ←i + h);

  • h := h div 3;{переход к нов.серии}

  • while h>0;



Сэджвик (1986г)

  • Сэджвик (1986г)

  • (h0,h1,h2,…)=(1,5,19,41,109,209..)

  • Конец последовательности – ht-1 если 3ht ≥ n

  • среднее количество операций: O(n7/6),

  • в худшем случае - порядка O(n4/3).

  • в среднем 1,66n1,25 перемещений.







Вариант 1

  • Вариант 1

  • массив делится на уже отсортированную часть

  • Ai+1, Ai+2…Аn

  • и неотсортированную

  • A1, A2, ….,Ai

  • На каждом шаге извлекается мах из неотсортированной части

  • Найденный мах ставится в начало отсортированной части



Простое извлечение

  • Простое извлечение

  • for i ←N downto 2 do

  • MaxIndex ← 1;

  • for j ← 2 to i do

  • if A[j]>A[MaxIndex] then MaxIndex ← j; Tmp ← A[i];

  • A[i] ← A[MaxIndex];

  • A[MaxIndex] ← Tmp;





Вариант 2

  • Вариант 2

  • последовательность создается, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная с первого и заканчивая (n-1)-м.

  • На i-м шаге выбираем наименьший из элементов A[i] ... A[n] и меняем его местами с A[i].





С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

  • С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

  • n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2-n )

  • = O(n2).



Усовершенствование простого выбора:

  • Усовершенствование простого выбора:

  • Лемма . В любом алгоритме нахождения максимума среди n элементов, основанном на сравнении пар элементов, необходимо выполнить, по крайней мере, n — 1 сравнений.





В общем случае, если n — точный квадрат, можно разделить массив на √n групп по √n элементов

  • В общем случае, если n — точный квадрат, можно разделить массив на √n групп по √n элементов

  • Любой выбор, кроме первого, требует не более чем √n -2 сравнений внутри группы ранее выбранного элемента плюс √n -1 сравнений среди "лидеров групп“

  • Этот метод получил название квадратичный выбор

  • общее время его работы составляет порядка O(n √n ) что существенно лучше, чем O(n2)



В алгоритме выбора проделав n-1 сравнение, мы можем построить дерево выбора и идентифицировать его корень как мин элемент

  • В алгоритме выбора проделав n-1 сравнение, мы можем построить дерево выбора и идентифицировать его корень как мин элемент

  • Второй этап сортировки – спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева

  • Элемент продвинувшийся в корень опять будет мин

  • После n шагов дерево становится пустым и сортировка заканчивается



tree1

  • tree1

  • На каждом из n шагов выбора требуется только log n сравнений. Поэтому на весь процесс понадобится порядка

  • n*log(n) , т.е. T(n) = O(n*log n )

  • элементарных операций и n шагов на построение дерева



Пирамида (двоичное дерево) определяется как последовательность

  • Пирамида (двоичное дерево) определяется как последовательность

  • HL, H L+1, … HR такая, что

  • Hi H2i & Hi  H 2i+1 для i=L …R/2

  • H1 = min(H1, H2,…HN)

  • tree2



Алгоритм Флойда:

  • Алгоритм Флойда:

  • Построение пирамиды на «том же месте»:

  • пусть H1, H2,…HN есть сортируемый массив, причем HM,…HN , где

  • M= (N div 2) +1 образует нижний слой пирамиды, поскольку нет индексов

  • i, j таких что j=2i или j=2i +1, т.е. для этого слоя упорядоченности не требуется



Алгоритм Флойда:

  • Алгоритм Флойда:

  • Пирамида расширяется влево -

  • каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент, пока элементы стоящие слева от HM

  • не будут образовывать пирамиду

  • (tree2) (table1)

  • Такая процедура называется – Sift



Sift(L, R: index);

  • Sift(L, R: index);

  • // i, j: index; x: item; х – элемент вставляемый в пирамиду

  • // i, j - пара индексов, фиксирующих элементы, меняющиеся на каждом шаге местами.

  • i ← L; j ← 2*L; X ← a[L];

  • if (j < R) & (a[j+1] < a[j]) then j ← j+1

  • while (j < = R) & (a[j] < X) do

  • a[i] ← a[j]; a[j] ← X; i ← j; j ← 2*j;

  • if (j < R) & (a[j+1] < a[j] then j ← j+1

  • // end Sift;



Процесс формирования пирамиды из n элементов h1 ... hn. на том же самом месте описывается так:

  • Процесс формирования пирамиды из n элементов h1 ... hn. на том же самом месте описывается так:

  • L ← (n div 2)+ 1;

  • while L > 1 do

  • L ← L - 1;

  • sift(L, n)

  • table1



n сдвигающих шагов выталкивания наименьших элементов на вершину дерева с последующим смещением в конец массива:

  • n сдвигающих шагов выталкивания наименьших элементов на вершину дерева с последующим смещением в конец массива:

  • R ← n;

  • while R>1 do

  • x ← a[1]; a[1] ← a[R]; a[R] ← x;

  • R ← R-1; sift(1,R )

  • table2









Procedure HeapSort;

  • Procedure HeapSort;

  • var L, R: index; x: item;

  • Procedure sift(L, R: index);

  • var i, j: index; x: item;

  • begin i := L; j := 2*L; X := a[L];

  • if (j < R) & (a[j+1] < a[j] then j := j+1

  • while (j < = R) & (a[j] < X) do

  • begin

  • a[i]:=a[j]; a[j]:= X; i:=j; j:=2*j;

  • if (j < R) & (a[j+1] < a[j] then j := j+1

  • end;

  • end sift;



begin

  • begin

  • L:=(n div 2)+ 1;R := n;

  • while L > 1 do

  • begin

  • L :== L - 1; sift(L, r)

  • end;

  • while R>1 do

  • begin

  • x:=a[1]; a[1] := a[R]; a[R] := x;

  • R := R-1; sift(1,R )

  • end;

  • end HeapSort;



В самом плохом из возможных случаев Heapsort потребует n*log n шагов.

  • В самом плохом из возможных случаев Heapsort потребует n*log n шагов.

  • т.е. T(n) = O (n*log n)

  • Heapsort «любит» начальные последовательности, в которых элементы более или менее отсортированы, то фаза порождения пирамиды потребует мало перемещений.

  • Среднее число перемещений приблизительно равно n/2*log(n), причем отклонения от этого значения незначительны.



Похожие:

Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconСортировка в базах данных Сортировка – процесс упорядочения записей в таблице
При использовании строки меню появляется диалоговое окно в котором можно задать параметры сортировки
Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconКомбинаторика — раздел математики, изучающий множества (сочетания, перестановки, размещения и перечисление элементов) и отношения на них (например, частичного порядка). Комбинаторика
Развитие исследовательских умений: выявление и решение ключевых задач, сбор информации, обобщение результатов
Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconЯзык теории множеств Множество состоит из элементов
...
Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconТеория вероятностей Основные понятия комбинаторики
...
Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconТеория вероятностей Основные понятия комбинаторики
...
Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconУрок по информатике. 3 класс. Цели урока
«множество», «элементы множества», «подмножество» научить определять число элементов множества; учить определять принадлежность элементов...
Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconКомбинаторика Сочетания Определение 1
А называется неупорядоченный набор попарноразличных элементов множества а длины k. Другими словами k-сочетание это k-элементное подмножество...
Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconКомбинаторика Комбинаторный анализ
Комбинаторика раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов)...
Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconСортировка- это упорядочивание данных (числа, текст, даты, логические значения) в электронных таблицах. Можно сортировать по возрастанию или по убыванию. Сортировка

Сортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка > iconПонятие и сущность права. Отрасли права. Сущность права состоит в равновесии
Норма права это общеобязательное и охраняемое государством правила поведения, регулирующее общественные отношения с целью их упорядочения...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница