Технологии и методы программирования

• Название: Технологии и методы программирования
• Дата: 18.10.2022
• Размер: 1.09 Mb.
• Имя файла: 6MetodXoara.Alfogitm.pptx
• Тип: Документы; #739198

Технологии и методы программирования

Online-edu.mirea.ru

ФИО преподавателя: Русаков Алексей Михайлович

e-mail: [e-mail]

Подготовил студент БСБО-02-19

Аушев Ахмед Борисович

На тему: Алгоритмы сортировки. Бинарная вставка. Быстрая сортировка Хоару
1)Алгоритм сортировки Бинарная вставка 1.1)Пример работы сортировки 1.2) Реализация 1.3) Плюсы и минусы алгоритма 2) Быстрая сортировка Хоару 2.1) Пример работы сортировки 2.2) Примеры реализации на языках программирование

Содержание

Алгоритм работает по следующему принципу. К примеру есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по не возрастанию

Бинарная вставка

Пример реализации на:

# iterative implementation def binarySearch(a, item, low, high):     while (low <= high):         mid = low + (high - low) // 2         if (item == a[mid]):             return mid + 1         elif (item > a[mid]):             low = mid + 1         else:             high = mid - 1     return low   def insertionSort(a, n):     for i in range (n):          j = i - 1         selected = a[i]                 loc = binarySearch(a, selected, 0, j)                          while (j >= loc):             a[j + 1] = a[j]             j-=1         a[j + 1] = selected a = [37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54] n = len(a) insertionSort(a, n) print("Sorted array: ") for i in range (n):     print(a[i], end=" ")

Плюсы и минусы

Очень много перемещений элементов массива

Алгоритм может работать с последовательно поступающими данными.

Алгоритм эффективен при работе со списками, алгоритм отлично справляется с массивами небольшого размера

высокая алгоритмическая сложность N²

7

Быстрая сортировка Хоара без медианного pivot элемента

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

Пример реализации на :

Пример реализации на :

Пример реализации на :

var i = low;                        

var j = high;        

var middle = arr[ Math.round(( low + high ) / 2) ];

do {          

  while(arr[i] < middle)                       

++i;                  

while(arr[j] > middle)                              

--j;            

if(i <= j){                          

  var temp = arr[i];                

arr[i] = arr[j];                

arr[j] = temp;                              

i++; j--;            

}        

}        

while(i < j);                

if(low < j){        

 quickSort(arr, low, j);        

}          

if(i < high){          

        quickSort(arr, i, high);

}

}

Спасибо за внимание!