• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Sortowanie



    Podstrony: 1 [2] [3] [4]
    Przeczytaj także...
    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie "dziel i zwyciężaj".

    Sortowanie – jeden z podstawowych problemów informatyki, polegający 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.

    Sortowanie przez zliczanie – metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy.Sortowanie przez wybieranie - jedna z prostszych metod sortowania o złożoności O(n). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.

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

    Algorytmy, do działania których nie jest potrzebna większa niż stała pamięć dodatkowa (elementy sortowane przechowywane są przez cały czas w tablicy wejściowej), nazywane są algorytmami działającymi w miejscu.

    Algorytmy sortujące, które dla elementów o tej samej wartości zachowują w tablicy końcowej kolejność tablicy wejściowej, nazywamy algorytmami stabilnymi.

    Sortowanie 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²).Permutacja – wzajemnie jednoznaczne przekształcenie pewnego zbioru na siebie. Najczęściej termin ten oznacza funkcję na zbiorach skończonych.

    Problem sortowania[ | edytuj kod]

    Formalna definicja problemu sortowania Dane wejściowe: ciąg liczb Wynik: permutacja (zmiana uporządkowania) ciągu wejściowego taka, że

    Klasyfikacja[ | edytuj kod]

    Algorytmy sortowania są zazwyczaj klasyfikowane według:

    Sytuacja trudna – ma miejsce, gdy dochodzi do nierównowagi między potrzebami i zadaniami a sposobami i warunkami ich realizacji. Nierównowaga ta dotyczy sytuacji normalnej, która powoduje, że zakłócony zostaje normalny przebieg aktywności i zmniejsza się prawdopodobieństwo realizacji zadania na poziomie normalnym. Zaburzenia przewidywalności sytuacji, zwiększające prawdopodobieństwo niepowodzenia (zagrożenia celu) definiują na nowo sytuację jako trudną, a człowiek aby sobie poradzić musi zmobilizować dodatkowe zasoby.Przeszukiwanie liniowe (lub wyszukiwanie sekwencyjne) to najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.
  • złożoności (pesymistyczna, oczekiwana) – zależność liczby wykonanych operacji w stosunku od liczebności sortowanego zbioru Typową, dobrą złożonością jest średnia i pesymistyczna Idealną złożonością jest Algorytmy sortujące nie przyjmujące żadnych wstępnych założeń dla danych wejściowych wykonują co najmniej 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
  • 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 i o tym samym kluczu, jeśli wystąpiło przed to po sortowaniu stabilnym nadal będzie przed
  • Kiedy elementy o tym samym kluczu są nierozróżnialne, stabilność nie jest istotna.

    Sortowanie grzebieniowe (ang. combsort) – wynaleziona w 1980 przez Włodzimierza Dobosiewicza, odkryta ponownie i opisana w 1991 roku przez Stephena Laceya i Richarda Boxa metoda sortowania tablicowego. Jej główne cechy to:Informatyka – dyscyplina nauki zaliczana do nauk ścisłych oraz techniki zajmująca się przetwarzaniem informacji, w tym również technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informację. Początkowo stanowiła część matematyki, później rozwinęła się do odrębnej dyscypliny – pozostaje jednak nadal w ścisłej relacji z matematyką, która dostarcza informatyce podstaw teoretycznych.

    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:

    Sortowanie introspektywne (ang. introspective sort lub introsort) - odmiana sortowania hybrydowego, w której wyeliminowany został problem złożoności O(n) występującej w najgorszym przypadku algorytmu sortowania szybkiego.Zbiór – pojęcie pierwotne teorii zbiorów (znanej szerzej jako teoria mnogości; za jej twórcę uważa się Georga Cantora) leżące u podstaw całej matematyki; intuicyjnie jest to nieuporządkowany zestaw różnych obiektów, czy też kolekcja niepowtarzających się komponentów bez wyróżnionej kolejności.

    W losowym rozmieszczeniu elemetów każdy element jest przesunięty względem swojej pozycji w posortowanym ciągu średnio o pozycji.

    Sortowanie Shella (ang. Shellsort) – algorytm sortowania działający w miejscu i korzystający z porównań elementów. Stanowi uogólnienie sortowania przez wstawianie, dopuszczające porównania i zamiany elementów położonych daleko od siebie. Jego pierwszą wersję opublikował w 1959 roku Donald Shell.W informatyce sortowanie przez scalanie (ang. merge sort), to rekurencyjny algorytm sortowania danych, stosujący metodę dziel i zwyciężaj. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi.

    Jeżeli algorytm sortowania zamienia tylko elementy sąsiadujące ze sobą, musi dokonać średnio zamian dla każdego z elementów. A więc średnia liczba porównań wynosi 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ą.

    Sortowanie zewnętrzne, sortowanie plików (ang. external sort) – rodzaj algorytmów sortowania, które są stosowane, kiedy z pewnych względów nie jest możliwe jednoczesne umieszczenie wszystkich elementów zbioru sortowanego w pamięci operacyjnej.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.


    Podstrony: 1 [2] [3] [4]




    Warto wiedzieć że... beta

    Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort) - jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty - kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe. Jest efektywny dla niewielkiej liczby elementów, jego złożoność wynosi O(n). Pomimo tego, że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort, posiada pewne zalety:
    Sortowanie biblioteczne (ang. Library sort) – algorytm sortowania, który bazuje na algorytmie sortowania przez wstawianie, ale z dodawaniem pustych miejsc w tablicy w celu przyspieszenia wstawiania elementów.
    Klasyfikacja statystyczna to rodzaj algorytmu statystycznego, który przydziela obserwacje statystyczne do klas, bazując na atrybutach (cechach) tych obserwacji.

    Reklama

    Czas generowania strony: 0.034 sek.