Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2017-12-12 | 102 |
5.00
из
|
Заказать работу |
Кол-во элементов | Сортировка простым выбором | Сортировка методом Шелла | Быстрая сортировка с огрн. рек. | ||||||
Время | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | Время, с | Число сравнений ключа | Число пересылок | |
1587,29439 | 61,095304 | 21,1533577 | |||||||
6323,765326 | 189,7683288 | 84,3938507 | |||||||
14225,0402 | 311,5236291 | 170,7748294 | |||||||
25295,59026 | 408,3120362 | 226,2148742 | |||||||
39505,04711 | 550,1877857 | 318,2928401 | |||||||
56842,79165 | 700,0719592 | 408,6996313 | |||||||
77417,90677 | 796,435305 | 471,1712062 | |||||||
101143,9112 | 953,2062336 | 537,6662122 | |||||||
127890,5549 | 1082,117967 | 591,3859857 | |||||||
158054,8388 | 1210,459579 | 691,4279534 |
Число сравнений ключа
Число сравнений ключа
Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией
Сортировка простым выбором
Сортировка Шелла и Быстрая сортировка с ограниченной рекурсией
Число пересылок
Сортировка простым выбором: для поиска одного элемента с наибольшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую последовательность.
Сортировка методом Шелла: используется сортировка вставками, применяя принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.
Быстрая сортировка с ограниченной рекурсией: выбирается для сравнения один элемент х, отыскивается слева первый элемент, который не меньше х, а справа первый элемент, который не больше х. Найденные элементы меняются местами. После первого же прохода все элементы, которые меньше х, будут стоять слева от х, а все элементы, которые больше х, - справа от х. С двумя половинами массива поступают точно также. Продолжая деление этих половин до тех пор пока не останется в них по 1 элементу.
Сортировка простым выбором на языке Java
void SelectSort(tItem a[], int n)
{ int i, j, jmin;
tItem buf;
for (i = 1; i > n-1; i--)
{ jmin = i;
for (j = 1; j < i-1; j++)
if (a[j].key <(a[jmin].key))
jmin = j;
buf = a[i];
a[i] = a[jmin];
a[jmin] = buf;
}
}
Сортировка методом Шелла на языке Си#
void ShellSort(tItem[] a, int n){
int h=13;
int i, j;
tItem x;
while (h < n){
h = 3*h + 1;
}
h = (h - 1) % 3;
do {
h = (h - 1) % 3;
for (i = h+1; i <= n; i++){
buf = a[i];
j = i-h;
while ((j > 0) && (a[j].key < x.key)
{ a[j + h] = a[j];
j--;
}
}
a[j + h] = buf;
} while (h <= 1);
}
Быстрая сортировка с ограниченной рекурсией
На языке Java
protected static void Sort(tItem a[], int L, int R)
{
tItem x;
tItem y;
int i;
int j;
while (L < R)
{
x = a[(L + R) / 2];
i = L; j = R;
do
{
while (a[i].Key < x.key) { i++; };
w hile (x.key < a[j].Key) { j--; };
if (i <= j)
{
y = a[i];
a[i] = a[j];
a[j] = y;
i++;
j--;
}
} while (i <= j);
if (j - L < R - i)
{
Sort(a, L, j);
L = i;
}
Else
{
Sort(a, i, R);
R = j;
}
}
}
static void QuickSort(tItem a[], int n)
{
Sort(a, 1, n);
}
Сортировка простым выбором
Число сравнений ключа:
Число пересылок:
;
Быстрая сортировка с ограниченной рекурсией
Число сравнений ключа:
C = n + (2*n/2) + (4*n/4) + … + (n*n/n) = n * k = n * log(n);
Число пересылок:
Исследование сортировки Шелла при разных
Параметрах алгоритма
Последовательность предложенная Кнутом: все значения kk = 3*kk + 1
Последовательность предложенная Хиббардом: все значения ; такая последовательность шагов приводит к алгоритму сложностью O(N3 / 2);
Последовательность предложенная Седжвиком: , если i четное и , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: O(n7 / 6), а в худшем случае порядка O(n4 / 3).
Число сравнений ключа
Кол-во элементов: | Кнут | Хиббард | Седжвик | ||||||
Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | |
Время
Кол-во элементов: | Кнут | Хиббард | Седжвик | ||||||
Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | |
1,135 | 0,181 | 0,648 | 1,237 | 0,391 | 0,762 | 1,586 | 0,075 | 0,954 | |
3,291 | 0,747 | 1,888 | 3,619 | 1,325 | 2,065 | 4,028 | 0,803 | 2,557 | |
5,426 | 1,507 | 3,134 | 5,824 | 2,398 | 3,581 | 6,384 | 1,462 | 3,802 | |
7,795 | 2,202 | 3,955 | 8,324 | 3,365 | 4,846 | 9,029 | 2,116 | 5,192 | |
10,387 | 2,808 | 5,516 | 11,093 | 4,692 | 5,97 | 11,725 | 3,091 | 6,808 | |
12,887 | 3,471 | 7,044 | 13,913 | 5,414 | 8,039 | 14,641 | 3,845 | 8,607 | |
15,838 | 4,664 | 7,257 | 16,51 | 6,541 | 9,159 | 17,237 | 4,605 | 10,314 | |
18,513 | 5,394 | 9,56 | 19,652 | 7,561 | 10,778 | 20,361 | 5,42 | 12,572 | |
21,442 | 5,839 | 10,843 | 22,913 | 9,196 | 11,744 | 23,264 | 6,293 | 13,089 | |
24,214 | 6,576 | 11,095 | 25,846 | 10,388 | 13,684 | 26,407 | 7,03 |
Число пересылок
Кол-во элементов: | Кнут | Хиббард | Седжвик | ||||||
Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсортированный массив | Случайный массив | Отсортированный массив | Обратно отсоритрованный массив | |
Число сравнений ключа
Время
Число пересылок
Вывод: В результате исследования алгоритмов сортировки «Простым выбором», «Сортировки методом Д.Шелла» и «Быстрой сортировки с ограниченной рекурсией» показало, что Быстрая сортировка в лучшем случае работает быстрее других, а в худшем так же как и сортировка Выбором и сортировка Шелла. Сортировка Простым выбором работает всех медленнее.
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!