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



    Podstrony: 1 [2] [3] [4]
    Przeczytaj także...
    Dziel i zwyciężaj (ang. divide and conquer) – jedna z głównych metod projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. Nazwa pochodzi od łacińskiej sentencji dziel i rządź (łac. divide et impera). W strategii tej problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla podproblemów scala się, uzyskując rozwiązanie całego zadania.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 szybkie (ang. QuickSort) zostało wynalezione w 1962 przez C.A.R. Hoare’a.

    Algorytm sortowania szybkiego jest wydajny: jego średnia złożoność obliczeniowa jest rzędu . Ze względu na szybkość i prostotę implementacji jest powszechnie używany. Jego implementacje znajdują się w bibliotekach standardowych wielu środowisk programowania.

    Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.PHP – obiektowy język programowania zaprojektowany do generowania stron internetowych i budowania aplikacji webowych w czasie rzeczywistym.

    Algorytm[ | edytuj kod]

    Z tablicy wybiera się element rozdzielający, po czym tablica jest dzielona na dwa fragmenty: do początkowego przenoszone są wszystkie elementy nie większe od rozdzielającego, do końcowego wszystkie większe. Potem sortuje się osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa tablica nie wymaga sortowania.

    Stos (ang. Stack) – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu). Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze. Elementy stosu poniżej wierzchołka można wyłącznie obejrzeć, aby je ściągnąć, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.Wydawnictwa Naukowo-Techniczne (WNT) – polskie wydawnictwo założone w 1949 z siedzibą w Warszawie, do 1961 działało pod firmą Państwowe Wydawnictwa Techniczne.

    Jeśli przez l oznacza się indeks pierwszego, a przez r – ostatniego elementu sortowanego fragmentu tablicy, zaś przez i – indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić następującym pseudokodem:

      PROCEDURE Quicksort(tablica, l, r)
      BEGIN
        IF l < r THEN { jeśli fragment dłuższy niż 1 element }
          BEGIN
            i := PodzielTablice(tablica, l, r); { podziel i zapamiętaj punkt podziału }
            Quicksort(tablica, l, i-1);         { posortuj lewą część }
            Quicksort(tablica, i+1, r);         { posortuj prawą część }
          END
      END
    
      {wybiera element, który ma być użyty do podziału
       i przenosi wszystkie elementy mniejsze na lewo od
       tego elementu, a elementy większe lub równe, na prawo
       od wybranego elementu }
      PROCEDURE PodzielTablice(tablica, l, r)
      BEGIN
         indeksPodzialu := WybierzPunktPodzialu(l, r); {wybierz element, który posłuży do podziału tablicy}
         wartoscPodzialu := tablica[indeksPodzialu]; {zapamiętaj wartość elementu}
         Zamien(tablica, indeksPodzialu, r); {przenieś element podziału na koniec tablicy, aby sam nie brał udziału w podziale}
    
         aktualnaPozycja := l;
         FOR i:=l TO r-1 DO {iteruj przez wszystkie elementy, jeśli element jest mniejszy niż wartość elementu podziału dodaj go do "lewej" strony}
         BEGIN
             IF tablica[i] < wartoscPodzialu THEN
             BEGIN
                 Zamien(tablica, i, aktualnaPozycja);
                 aktualnaPozycja := aktualnaPozycja + 1;
             END
         END
         Zamien(tablica, aktualnaPozycja, r); {wstaw element podziału we właściwe miejsce}
         return aktualnaPozycja;
      END
    
      { podstawowa implementacja wyboru punktu podziału - wybiera element "środkowy" w tablicy }
      PROCEDURE WybierzPunktPodzialu(l, r)
      BEGIN
         return l + (r-l) div 2;
      END
    
      { zamienia miejscami elementy w komórkach i1, i2 }
      PROCEDURE Zamien(tablica, i1, i2)
      BEGIN
        IF i1<>i2 THEN
        BEGIN
         aux := tablica[i1];
         tablica[i1] := tablica[i2];
         tablica[i2] := aux;
        END
      END
    

    Właściwe działanie algorytmu wymaga, aby procedura PodzielTablice pozostawiała element rozdzielający na końcu lewej części uzyskanej z podziału. Wówczas element ten znajduje się na swojej ostatecznej pozycji i nie podlega dalszemu przetwarzaniu – rekurencyjne wywołania Quicksort nie obejmują indeksu i. Tym samym do dalszego przetwarzania przekazuje się o jeden element mniej, co gwarantuje zakończenie rekurencji.

    Biblioteka standardowa to biblioteka zawierająca podstawowe funkcje, dostarczana wraz kompilatorem lub interpreterem danego języka programowania. Dla niektórych języków, np. ANSI C, istnieje formalna specyfikacja zawartości i działania biblioteki standardowej.Charles Antony Richard Hoare (Tony Hoare, ur. 11 stycznia 1934 w Kolombo, Sri Lanka) - brytyjski informatyk, znany jako twórca algorytmu sortowania quicksort. Rozwinął także logikę Hoare’a służącą do weryfikowania poprawności programów oraz stworzył język formalny Communicating Sequential Processes (CSP) używany do specyfikowania interakcji współbieżnych procesów (zob. problem ucztujących filozofów). Przyczynił się także do powstania języka programowania Occam. W 1980 roku, w dowód uznania za wkład w rozwój języków programowania otrzymał nagrodę Turinga.


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




    Warto wiedzieć że... beta

    Definicja intuicyjna: W danym szeregu uporządkowanym liczba, która jest w połowie szeregu w wypadku nieparzystej liczby elementów. Dla parzystej liczby elementów – średnia arytmetyczna dwóch środkowych liczb.
    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.
    Algorytm in situ (łac. in situ - w miejscu) - jest to algorytm, który do wykonania potrzebuje stałej ilości pamięci komputera, niezależnej od rozmiaru danych wejściowych. Wszelkie potrzebne do otrzymania wyniku obliczenia są wykonywane w pamięci, do której zostały załadowane dane.
    Jon Louis Bentley (ur. 20 lutego 1953 w Long Beach, California) – amerykański informatyk. Zdobył tytuł bakałarza w 1974 r. na Stanford University. Tytuł magistra i doktora (1976 r.) zdobył na University of North Carolina. Ma tytuł profesora matematyki i informatyki Carnegie Mellon University.
    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.
    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.
    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:

    Reklama

    Czas generowania strony: 0.826 sek.