algorytm.org

Sortowanie szybkie (quicksort)



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie szybkie (quicksort)
Ocena użytkowników:***** / 139
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 13 sierpnia 2005 10:49

Algorytm sorotwania szybkiego jest uważany za najszybszy algorytm dla danych losowych.
Zasada jego działania opiera się o metodę dziel i zwyciężaj. Zbiór danych zostaje podzielony na dwa podzbiory i każdy z nich jest sortowany niezależnie od drugiego.
Dla zadanej tablicy a[l..p] wybieramy element v=a[l] i przeszukujemy resztę tablicy (tzn. a[l+1..p]) tak długo, aż nie znajdziemy elementu większego niż a[l]. Następnie przeszukujemy tą tablicę od strony prawej póki nie znajdziemy elementu nie większego niż a[l]. Gdy to osiągniemy, zamieniamy miejscami te dwa elementy i zaczynamy cały proces od początku. Algorytm działa tak długo, aż wskaźnik poruszający się w lewo i wskaźnik poruszający się w prawo spotkają się. Należy wówczas zamienić element v=a[l] z ostatnim elementem lewej części tablicy.
Mimo, że w najgorszym przypadku algorytm ma złożoność kwadratową, jest on bardzo często stosowany. Powodem tego jest niska- liniowologarytmiczna, złożoność w średnim przypadku.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Bartosz SypytkowskiC#
.cs
.cs
***** / 15
Michał KnasieckiC/C++
.cpp
.cpp
***** / 26
MarianC/C++C++
.cpp
.cpp
***** / 144
Jan WojciechowskiC/C++C++ templates
.cpp
.cpp
***** / 11
Michał KnasieckiDelphi/Pascal
.pas
.pas
***** / 15
Tomasz LubińskiJava
.java
.java
***** / 29
Mariusz GumiennyJavaScript
.js
.js
***** / 5
Damian DziedzicMatlab
.mat
.mat
***** / 9
kiziorgdPhp
.php
.php
***** / 3
Bartosz SypytkowskiPython
.py
.py
***** / 10
Rafał GawlikPythonPython2, Python3
.py
.py
***** / 16
mephistoRuby
.rb
.rb
***** / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 maja 2011 08:45
Komentarze
photo
-4 # Janusz 2009-09-28 01:22
Dzieki za objaśnienie :] ...jasniej sie już nie da
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+7 # izcew 2010-03-26 13:35
mogl by ktos napisac pseldo kod tych operacji a nastepnie podac obliczenia zlozonosci obliczeniowych?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-30 # Align 2012-03-31 13:11
Ja p******* kto niby ma za was odrabiać prace domowe? Ja? Autor?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Dominika 2012-11-08 23:13
Czym się ten sposób sortowania różni od sortowania przez wybór? Ostatnim punktem (tą wymianą v=a[l] z ostatnim elementem po lewej części tablicy)?
I dlaczego ta metoda jest najszybsza?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+6 # alefx 2013-05-11 19:55
http://www.youtube.com/watch?v=ywWBy6J5gz8
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+5 # Ula 2018-05-27 19:25
Przydałby się rysunek poglądowy
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # jk 2019-05-31 22:21
A potem powtarzamy quicksorta dla kazdej z polowek tablicy? Bo tego nie ma napisanego
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz