Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie

Sortowanie

Sortowanie

Sortowanie – jeden z podstawowych problemów informatyki . Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru . Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.

Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwienia stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.

Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego .

Spis treści

Klasyfikacja

Algorytmy sortowania są zazwyczaj klasyfikowane według:

  • złożoności (pesymistyczna, oczekiwana i obliczeniowa) – zależność liczby wykonanych operacji w stosunku od liczebności sortowanego zbioru (n). Typową, dobrą złożonością jest średnia O(n log n) i pesymistyczna Ω(n²). Idealną złożonością jest O(n). Algorytmy sortujące nie przyjmujące żadnych wstępnych założeń dla danych wejściowych wykonują co najmniej O(n log n) operacji w modelu obliczeń, w którym wartości są "przezroczyste" i dopuszczalne jest tylko ich porównywanie (w niektórych bardziej ograniczonych modelach istnieją asymptotycznie szybsze algorytmy sortowania);
  • złożoność pamięciowa
  • sposób działania: algorytmy sortujące za pomocą porównań to takie algorytmy sortowania, których sposób wyznaczania porządku jest oparty wyłącznie na wynikach porównań między elementami; Dla takich algorytmów dolne ograniczenie złożoności wynosi Ω(n log n);
  • stabilność: stabilne algorytmy sortowania utrzymują kolejność występowania dla elementów o tym samym kluczu (klucz – cecha charakterystyczna dla każdego elementu zbioru, względem której jest dokonywane sortowanie). Oznacza to, że dla każdych dwóch elementów R i S o tym samym kluczu, jeśli R wystąpiło przed S to po sortowaniu stabilnym R nadal będzie przed S;

Kiedy elementy o tym samym kluczu są nierozróżnialne, stabilność nie jest istotna.

Przykład: (para liczb całkowitych sortowana względem pierwszej wartości)

(4, 1) (3, 7) (3, 1) (5, 6)

W tym przypadku są możliwe dwa różne wyniki sortowania:

(3, 7) (3, 1) (4, 1) (5, 6) – kolejność zachowana(3, 1) (3, 7) (4, 1) (5, 6) – kolejność zmieniona
  • Stabilne algorytmy sortowania gwarantują, że kolejność zostanie zachowana.
  • Niestabilne algorytmy sortowania mogą zmienić kolejność.

Algorytmy sortujące dzielimy na proste ("naiwne") i zaawansowane ("logarytmiczne"). Powstanie lepszych niż proste algorytmów sortowania spowodowane było konsekwencjami poniższego faktu:

W losowym rozmieszczeniu n elemetów a[0],a[1],\cdots ,a[n-1] każdy element jest przesunięty względem swojej pozycji w posortowanym ciągu a'[0],a'[1],\cdots ,a'[n-1] średnio o \frac{n}{3} pozycji.

Jeżeli algorytm sortowania zamienia tylko elementy sąsiadujące ze sobą, musi dokonać średnio \frac{n}{3} zamian dla każdego z n elementów. A więc średnia liczba porównań wynosi n\cdot \frac{n}{3}= \frac{n^2}{3}=O(n^2). Jedynym sposobem zmniejszenia asymptotycznej złożoności algorytmów sortujących jest wprowadzenie możliwości zamieniania elementów nie sąsiadujących ze sobą.

Przykładowe algorytmy sortowania

W podanej złożoności n oznacza liczbę elementów do posortowania, k liczbę różnych elementów.

Stabilne

Elementy o równej wartości będą występowały, po posortowaniu, w takiej samej kolejności jaką miały w zbiorze nieposortowanym.

Niestabilne

Podobne problemy

  • wyszukiwanie elementu o największej wartości funkcji porządkującej
  • wyszukiwanie n-tego elementu.

Zobacz też

Linki zewnętrzne


Inne hasła zawierające informacje o "Sortowanie":

Sortowanie Sortowanie – jeden z podstawowych problemów informatyki . Polega na uporządkowaniu zbioru danych ...

Kod pocztowy – ciąg cyfr (rzadziej liter i cyfr) dodawany do adresu , mający ułatwiać Sortowanie przesyłek. Format i zasady umieszczania kodów pocztowych są różne w różnych ...

Sortowanie bąbelkowe ...

Sortowanie przez scalanie ...

Sortowanie przez zliczanie ...

Sortowanie kubełkowe Sortowanie kubełkowe ( ang . bucket sort) – jeden z algorytmów sortowania . Jest on ...

Sortowanie pozycyjne ...

Sortowanie biblioteczne Library sort, lub Sortowanie biblioteczne to algorytm sortowania , który bazuje na algorytmie sortowania przez wstawianie , ...

Sortowanie przez wybieranie ...

Sortowanie Shella ...


Inne lekcje zawierające informacje o "Sortowanie":

Zagrożenia gleb (plansza 21) dawkach i terminach wymywanie powierzchniowej warstwy gleby przez wodę opadową (erozja wodna) wywiewanie, przemieszczanie, Sortowanie i osadzanie w innym rejonie cząstek gruntu na wskutek erozji wietrznej zniszczenie ...

Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór (plansza 3) określić dla każdego elementu tzw. klucz (ang. key), według którego dokonywane jest Sortowanie. Klucz jest liczbą, dlatego obowiązują dla niego podane wcześniej zasady kolejności ...

Algorytmy sortujące - sortowanie bąbelkowe, część II (plansza 10) - w ten sposób nie będziemy sprawdzać już najstarszego elementu z poprzedniego obiegu. Sortowanie prowadzimy do momentu, aż w obiegu sortującym nie wystąpi ani jedna ...





Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie