• 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 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.

    Spis treści

  • 1 Algorytm
  • 2 Złożoność
  • 2.1 Przypadek optymistyczny
  • 2.2 Przypadek przeciętny
  • 2.3 Przypadek pesymistyczny
  • 3 Usprawnienia algorytmu
  • 3.1 Wybór elementu
  • 3.2 Ograniczenie rekursji
  • 3.3 Quicksort w miejscu
  • 3.4 Drobne fragmenty
  • 3.5 Gwarancja złożoności
  • 4 Przykładowe implementacje
  • 5 Przypisy
  • 6 Linki zewnętrzne
  • 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.


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



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    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.
    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.

    Reklama

    Czas generowania strony: 0.025 sek.