Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > worst case алгоритмов сортировки

Автор: Killer_13 14.4.2011, 18:27

Здр,
Один из вопросов на который следует найти ответ.
Значит сейчас изучаем различные алгоритмы сортировки, время сортировки и так д...
Может кто знает, или знает как это сделать.

1. Как посчитать worst case?
Например при bubble sort есть определенное число проходов цыкла и определенное число перестановок.
Так вот в bubble sort worst case =n^2 Здесь мне наверное нужно считать проходы цыкла.

В QuickSort worst case = n^2 - так вот собственно е чему я все это. Мне нужно найти такую последовательность элементов чтоб при сортировке Quick sort случился worst case. насколько я понимаю, то нужно считать сколько раз мы поменяли местами элементы?
Припустим у меня 10 элементов, чтоб случился worst case нужно получить 100 в результате, что это за последовательность такая?

Спасибо за ответ.

Автор: Akina 14.4.2011, 20:05

Берём и проходим алгоритм в обратном порядке, на каждом сравнении проводя обмен.

Автор: Killer_13 14.4.2011, 20:14

При QuickSort даже в обратном порядке, n будет равно 10 или около того,
Вот алгоритм

Код


public class QuickSort {
public static void sort (int[] a) { 
quicksort(a, 0, a.length-1); 
}
private static void quicksort (int[] a, int unten, int oben) {
int tmp ;
int i = unten;
int j = oben;
int x = a[(unten+oben) / 2]; 
do {
while (a[i] < x) i++; 
while (a[j] > x) j--;
if ( i<=j ) {
tmp = a[i];
a[i] = a[j]; 
a[j] = tmp; 
i++;
j--;
}
} while (i <= j);

if (unten < j) quicksort(a, unten, j); 
if (i < oben ) quicksort(a, i, oben );
}
}

И как в нем на каждом сравнении проводить обмен? smile

Должна же быть такая последовательность!
Тут не алгоритм нужно править, нужно править последовательность. тоисть алгоритм изменять неззя.

Автор: Akina 14.4.2011, 20:37

Цитата(Killer_13 @ 14.4.2011, 21:14

)

И как в нем на каждом сравнении проводить обмен?

Что сравниваем, то и меняем.

Добавлено через 48 секунд

Цитата(Killer_13 @ 14.4.2011, 21:14

)

Тут не алгоритм нужно править, нужно править последовательность. тоисть алгоритм изменять неззя.

Он не изменяется, а инвертируется. Получается "алгоритм медленного разупорядочивания".

Автор: Killer_13 14.4.2011, 22:25

Что-то не совсем понял, так что нужно сделать, чтоб не менять алгоритм?

Автор: qwertinpop 23.4.2011, 20:01

надо чтобы выбирались всегда наибольшие или наименьшие значения int x = a[(unten+oben) / 2] здесь

Автор: esperanto 27.4.2011, 00:08

В рандомизированной быстрой сортировке нет худшего случая.

А в нерандомизированном, худший случай, это когда массив длиной к, делится на два массива длиной 1 и к-1 соответственно