Правила сортировки. Saralash qoidalari План

• ЛЕКЦИЯ №5

• Saralash vaqti pastki chegarada

Правила сортировки. Saralash qoidalari

• План

• Правила сортировки. Saralash qoidalari
• Нижняя граница сортировки сравнением. Taqqoslash pastki chegarani saralash
• Сортировка подсчетом. Hisoblash bo'yicha saralash
• Поразрядная сортировка. Bitli tartibda saralash

Процедура REALLY-SIMPLE-SORТ(A,n)

• Правила сортировки Saralash qoidalari

• Процедура REALLY-SIMPLE-SORТ(A,n)
• Вход: Kirish:
• А: массив, все элементы которого имеют значения 1 или 2. Javob: barcha elementlari 1 yoki 2 qiymatga ega bo'lgan qator.
• n: количество сортируемых элементов А. saralanadigan elementlar soni A.
• Результат: элементы А отсортированыв неубывающем порядке. A elementlari kamaymaydigan tartibda saralanadi.
• 1. Установить k равным нулю. K ni nolga qo'ying.
• 2. Для до :Oldin uchun:
• А. Если , увеличить. k на единицу. A. Agar o'ssa. birlik uchun k
• 3. Для до :
• А. Установить равным . A. Agar o'ssa. birlik uchun k
• 4. Для до :
• А. Установить равным . Teng sozlash

Любой алгоритм сортировки сравнением требует для сортировки элементов сравнений пар элементов.

• Нижняя граница сортировки сравнением

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

Метод REALLY-SIMPLE-SORТ можно обобщить на случай различных возможных значений ключей сортировки, которые являются целыми числами из диапазона, представляющего собой последовательных целых чисел ( скажем, от 0 до ), а элементы при этом могут иметь сопутствующие данные.

• Сортировка подсчетом

• Метод REALLY-SIMPLE-SORТ можно обобщить на случай различных возможных значений ключей сортировки, которые являются целыми числами из диапазона, представляющего собой последовательных целых чисел ( скажем, от 0 до ), а элементы при этом могут иметь сопутствующие данные.

Процедура Count-Keys-Equal(A,n,m)

• Процедура Count-Keys-Equal(A,n,m)
• Вход:
• А: массив целых чисел в диапазоне от 0 до .
• n: количество элементов в массиве А.
• m: определяет диапазон значений в массиве А.
• Выход: массив , такой, что содержит количество элементов массива А, равных , для .
• 1. Пусть представляет собой новый массив.
• 2. Установить все значеиИJ1 массива equal равными нулю.
• 3. Для до :
• А. Установить значение переменной key равным .
• В. Увеличить на единицу.
• 4. Вернуть массив .

Процедура Count-Keys-Less(equal,m)

• Теперь мы можем использовать массив equal для выяснения, у какого количества элементов ключи сортировки меньше каждого возможного значения.

• Процедура Count-Keys-Less(equal,m)
• Вход:
• : массив, возвращаемый вызовом процедуры Count-Keys-Less.
• : определяет диапазон индексов массива -oт 0 до .
• Выход: массив , такой, что для элемент содержит сумму .
• l. Пусть представляет собой новый массив.
• 2. Установить равным нулю.
• 3. Для до :
• А. Установить равным .
• 4. Вернуть массив less.

Процедура COUNТING-SORТ(A.n,m)

• Процедура COUNТING-SORТ(A.n,m)
• Вход:
• А: массив целых чисел в диапазоне от 0 до .
• : количество элементов в массиве А.
• : определяет диапазон значений в массиве А.
• Выход: массив В, содержащий элементы массива А в отсортированном порядке.

Последовательность после сортировки

• Поразрядная сортировка

• Последовательность после сортировки
• 1.
  
• 2.
  
• З
• 4.
  
• 5. <Кl4WR2, Xl7FS6, JI8FR9, JL2ZVЗ, PL4ZQ2, XL8FQ6, KV7WS9, PY2ZR5>
• 6