Технологии и методы программирования
 Скачать 0.71 Mb.
|
|
Технологии и методы программирования Online-edu.mirea.ru ФИО преподавателя: Русаков Алексей Михайлович e-mail: rusakov.a@mirea.ru Подготовил студент БСБО-02-19 Аушев Ахмед Борисович На тему: Алгоритмы сортировки. «Сравнение и подсчет». Алгоритм Шелла 1)Алгоритм сортировки «Сравнение и подсчет» 1.1)Пример работы сортировки 1.2) Реализация 2) Описание алгоритма шелла 2.1) Пример работы сортировки 2.3) Примеры реализации на языках программирование Содержание Данный метод впервые упоминается в работе Э.Х. Фрэнда, хотя он и не заявил о ней как о своей собственной разработке. Сортировка подсчётом - это алгоритм, основанный на подсчёте повторяющихся элементов в массиве. Общая идея алгоритма (простой вариант): Есть массив A длиной n элементов, который нужно отсортировать. Создаётся вспомогательный массив C с индексами от 0 до k (максимальное значение в массиве A) и заполняется нулями. Последовательно проходим по массиву A и записываем в C[i] количество чисел, равных i. Таким образом индексы в массиве C - это значения массива A, а значение в массиве C - это то, сколько раз это число повторяется в массиве A. Проходим по массиву C и переносим значения в массив A. Алгоритм сортировки «Сравнение и подсчет» Сортировка подсчетом (Counting Sort) не использует операции сравнения, и применяется для массива A дискретных данных (например, целых чисел, символов), которые принимают значения из небольшого диапазона 𝑎𝑖 = [0,𝐾 − 1]. Для данного алгоритма применяют вспомогательный массив C, элементы которого с[𝑖] = 𝑐𝑜𝑢𝑛𝑡(А, 𝑖) , где 𝑐𝑜𝑢𝑛𝑡(А, 𝑖) - количество элементов в массиве А, равных значению i. Размер массива С равен максимальному элементу массива А. Приведем пример исходного массива А и вспомогательного массива С. По массиву С легко получить упорядоченный массив А. Делая проход по массиву С, мы столько раз последовательно включаем в массив А элемент i, сколько раз он встречался в А, а именно с[𝑖] раз. Пример работы Реализация кода на С //array — указатель на начало массива //n — размер массива //k — максимальное число в массиве void countingSort(int* array, int n, int k) { int* c = (int*)malloc((k+1) * sizeof(*array)); memset(c, 0, sizeof(*array)*(k+1)); for (int i = 0; i < n; ++i){ ++c[array[i]]; } int b = 0; for (int i = 0; i < k+1; ++i){ for (int j = 0; j < c[i]; ++j) { array[b++] = i; } } free(c); } Описание алгоритма Шелла Этот метод сортировки Д. Шелл предложил в 1959 г. Он использует минимум памяти и показывает высокие скорости при сортировке. По сути в методе Шелла применяются сравнения и перестановки элементов аналогичные методу вставок, но при этом порядок сравниваемых элементов совершенно другой. Идея сортировки методом Шелла состоит в том, чтобы сортировать элементы отстоящие друг от друга на некотором расстоянии step. Затем сортировка повторяется при меньших значениях step, и в конце процесс сортировки Шелла завершается при step = 1 (а именно обычной сортировкой вставками). До сих пор продолжает обсуждаться вопрос выбора шага сортировки step. Шелл предложил такую последовательность: N/2, N/4, N/8 …, где N — количество элементов в сортируемом массиве. Пример реализации на : Пример реализации на : template< typename RandomAccessIterator, typename Compare > void shell_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp ) { for( auto d = ( last - first ) / 2; d != 0; d /= 2 ) //нужен цикл для first = a[0..d-1] for( auto i = first + d; i != last; ++i ) for( auto j = i; j - first >= d && comp( *j, *( j - d ) ); j -= d ) std::swap( *j, *( j - d ) ); } Пример реализации на: Пример реализации на: const ShellSort = arr => { const l = arr.length; let gap = Math.floor(l / 2); while (gap >= 1) { for (let i = gap; i < l; i++) { const current = arr[i]; let j = i; while (j > 0 && arr[j - gap] > current) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = current; } gap = Math.floor(gap / 2); } return arr; }; Пример реализации на: def shell_sort(data: list[int]) -> list[int]: last_index = len(data) step = len(data)//2 while step > 0: for i in range(step, last_index, 1): j = i delta = j - step while delta >= 0 and data[delta] > data[j]: data[delta], data[j] = data[j], data[delta] j = delta = j - step //= 2 return data WhiteSnake Спасибо за внимание! |