Odpowiedzi

2010-02-16T01:14:46+01:00
Algorytmy sortowania :
a) bąbelkowe - (ang. bubble sort) - prosta metoda sortowania o złożoności czasowej O(n2) i pamięciowej O(1).

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.

b)kubełkowe - (ang. bucket sort) – jeden z algorytmów sortowania. Jest on najczęściej stosowany, gdy liczby w zadanym przedziale są rozłożone jednostajnie, ma on wówczas złożoność Θ(n). W przypadku ogólnym pesymistyczna złożoność obliczeniowa tego algorytmu wynosi O(n²).

c) grzebieniowe - (ang. combsort) – wynaleziona w 1980 przez Włodzimierza Dobosiewicza, odkryta ponownie i opisana w 1991 roku przez Stephena Lacey'a i Richarda Boxa metoda sortowania tablicowego. Jej główne cechy to:

* oparta na metodzie bubblesort (sortowanie bąbelkowe)
* prawdopodobnie złożoność wynosi O(n log n), statystycznie gorsza niż quicksort (sortowanie szybkie)
* włączono empirię - współczynnik 1.3 wyznaczony doświadczalnie

3 1 3