Najlepszy algorytm sortujący dla OI
-
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Najlepszy algorytm sortujący dla OI
Który z algorytmów sortujących jest waszym zdaniem najlepszy? Chodzi mi tu głównie o ich zastosowanie w zadaniach z olimpiady informatycznej. Mówi się że QuickSort jest najlepszy ale przypadek pesymistyczny w \(\displaystyle{ O(n^2)}\) w połączeniu z wrednymi testami na OI skutecznie mnie do niego zniechęca. HeapSort jest bardzo fajny i pomysłowy, ale coś mi się wydaje że kopcowanie jest zbyt czasochłonne i chyba się kieruję w kierunku stosowania MergeSort.
Sortowanie pozycyjne, kubełkowe i przez zliczanie do przypadku ogólnego się chyba nie nadają, a reszta (bąbelkowe i inne bruty) są do niczego.
Sortowanie pozycyjne, kubełkowe i przez zliczanie do przypadku ogólnego się chyba nie nadają, a reszta (bąbelkowe i inne bruty) są do niczego.
Ostatnio zmieniony 7 gru 2016, o 08:16 przez Afish, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex] .
Powód: Całe wyrażenia matematyczne umieszczaj w tagach
-
- Użytkownik
- Posty: 107
- Rejestracja: 7 lis 2006, o 12:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Pomógł: 20 razy
Najlepszy algorytm sortujący dla OI
Wszystko zależy od ilości danych i konkretnego przypadku. Generalnie wszystkie te algorytmy mają taką samą złożoność obliczeniową O(nlogn). W ogólności quicksort powinien być najszybszy w praktyce, jednak faktycznie dla specyficznie ułożonych danych może spowolnić, co widoczne by było szczególnie w sytuacji, gdy mielibyśmy do czynienia z dużą ilością danych. Na korzyść heapsorta przemawia też jego złożoność pamięciowa, która jest najlepsza wśród wymienionych algorytmów. Warto też zwrócić uwagę na fakt, iż quicksorta i mergesort łatwiej zrównoleglić, co może wymiernie wpłynąć na czas działania w systemach wieloprocesorowych.
Prawdę mówiąc zwykle najłatwiej i najszybciej skorzystać z bibliotecznego qsorta.
Prawdę mówiąc zwykle najłatwiej i najszybciej skorzystać z bibliotecznego qsorta.
- eloar
- Użytkownik
- Posty: 106
- Rejestracja: 18 cze 2007, o 16:59
- Płeć: Mężczyzna
- Lokalizacja: Kobyłka
- Podziękował: 8 razy
- Pomógł: 12 razy
Najlepszy algorytm sortujący dla OI
Czy nie lepiej przeprowadzić samodzielną analizę, lub porównanie tych algorytmów poprzez implementację w jednym języku i przetestowanie ich dla tych samych danych wejściowych? Najlepiej dużych danych wejściowych, czyli tak na przykład dla 1000000 rekordów/znaków/liczb? Ta ankieta moim zdaniem nie ma większego sensu, ponieważ każde z sortowań ma swoje plusy i minusy i w implementacji i w samym zastosowaniu, a skoro to ma być pod kątem olimpiady, to nie licz na to, że konkurencja właściwie Ci podpowie.
-
- Użytkownik
- Posty: 941
- Rejestracja: 17 gru 2007, o 21:48
- Płeć: Mężczyzna
- Lokalizacja: Kingdom Hearts
- Podziękował: 6 razy
- Pomógł: 222 razy
Najlepszy algorytm sortujący dla OI
Podpisuję się pod eloarem I tak btw, Dumel, nie wiem czy wiesz ale jest taka sytuacja, kiedy bubblesort zadziała szybciej niż quicksort
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Najlepszy algorytm sortujący dla OI
Kod: Zaznacz cały
#include <vector>
#include <algorithm>
...
vector<int> V;
...
sort(V.begin(),V.end());
- Mariusz M
- Użytkownik
- Posty: 6909
- Rejestracja: 25 wrz 2007, o 01:03
- Płeć: Mężczyzna
- Lokalizacja: 53°02'N 18°35'E
- Podziękował: 2 razy
- Pomógł: 1246 razy
Najlepszy algorytm sortujący dla OI
Quick sort , jeśli jesteś w stanie względnie szybko stwierdzić czy
dla danych wejściowych wystąpi przypadek pesymistyczny to czemu nie
Chociaż sprawdzanie czy nie mamy do czynienia z przypadkiem pesymistycznym może spowolnić
algorytm
Merge sort jeżeli możemy sobie pozwolić na poświęcenie dodatkowej pamięci
aby uzyskać stabilność algorytmu to możemy go stosować także na tablicach
Powinien dobrze działać na listach i plikach
Kolejność elementów o tych samych kluczach w tablicy posortowanej jest taka sama jak
w tablicy przed sortowaniem
Heap sort nie jest stabilny ale ma pesymistyczną złożoność nlogn
Występują w nim skoki po tablicy
Na podstawie pseudokodów u Cormena napisałem takie funkcje
Merge sort (from Algorithms unlocked)
Heap sort (from Introduction to algorithms)
Pozostaje jeszcze usunąć rekurencję w obydwu tych algorytmach
dla danych wejściowych wystąpi przypadek pesymistyczny to czemu nie
Chociaż sprawdzanie czy nie mamy do czynienia z przypadkiem pesymistycznym może spowolnić
algorytm
Merge sort jeżeli możemy sobie pozwolić na poświęcenie dodatkowej pamięci
aby uzyskać stabilność algorytmu to możemy go stosować także na tablicach
Powinien dobrze działać na listach i plikach
Kolejność elementów o tych samych kluczach w tablicy posortowanej jest taka sama jak
w tablicy przed sortowaniem
Heap sort nie jest stabilny ale ma pesymistyczną złożoność nlogn
Występują w nim skoki po tablicy
Na podstawie pseudokodów u Cormena napisałem takie funkcje
Merge sort (from Algorithms unlocked)
Kod: Zaznacz cały
program sort;
uses crt;
const maxT=2500;
type tablica=array[1..maxT]of real;
procedure merge(var A:tablica;p,q,r:integer);
var n1,n2,i,j,k:integer;
B:tablica;
begin
n1:=q-p+1;
n2:=r-q;
for i:=p to r do
B[i-p+1]:=A[i];
i:=1;
j:=n1+1;
k:=p;
while((i<=n1)and(j<=n1+n2)) do
begin
if(B[i]<=B[j]) then
begin
A[k]:=B[i];
i:=i+1;
end
else
begin
A[k]:=B[j];
j:=j+1;
end;
k:=k+1;
end;
while(i<=n1) do
begin
A[k]:=B[i];
i:=i+1;
k:=k+1;
end;
while(j<=n1+n2) do
begin
A[k]:=B[j];
j:=j+1;
k:=k+1;
end;
end;
procedure mergesort(var A:tablica;p,r:integer);
var q:integer;
begin
if(p<r) then
begin
q:=(p+r) div 2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
end;
end;
var k,n,p,q:integer;
A:tablica;
esc:char;
begin
clrscr;
repeat
writeln('Podaj rozmiar tablicy');
readln(n);
randomize;
for k:=1 to n do
begin
p:=(1-2*random(2))*random(10);
q:=1+random(10);
A[k]:=(p/q);
end;
for k:=1 to n do
write(A[k]:1:10,' ');
writeln;
writeln;
mergesort(A,1,n);
for k:=1 to n do
write(A[k]:1:10,' ');
writeln;
writeln;
esc:=readkey;
until esc=#27;
end.
Kod: Zaznacz cały
program sort;
uses crt;
const maxT=2500;
type tablica=array[1..maxT]of real;
procedure heapify(var A:tablica;i,heapsize:integer);
var l,r,largest:integer;
temp:real;
begin
l:=2*i;
r:=2*i+1;
if((l<=heapsize)and(A[l]>A[i])) then
largest:=l
else
largest:=i;
if((r<=heapsize)and(A[r]>A[largest])) then
largest:=r;
if(largest<>i) then
begin
temp:=A[i];
A[i]:=A[largest];
A[largest]:=temp;
heapify(A,largest,heapsize);
end;
end;
procedure buildheap(var A:tablica;len:integer);
var i:integer;
begin
for i:=len div 2 downto 1 do
heapify(A,i,len);
end;
procedure heapsort(var A:tablica;len:integer);
var i,heapsize:integer;
temp:real;
begin
buildheap(A,len);
heapsize:=len;
for i:=len downto 2 do
begin
temp:=A[1];
A[1]:=A[i];
A[i]:=temp;
heapsize:=heapsize-1;
heapify(A,1,heapsize);
end;
end;
var k,n,p,q:integer;
A:tablica;
esc:char;
begin
clrscr;
repeat
writeln('Podaj rozmiar tablicy');
readln(n);
randomize;
for k:=1 to n do
begin
p:=(1-2*random(2))*random(10);
q:=1+random(10);
A[k]:=(p/q);
end;
for k:=1 to n do
write(A[k]:1:10,' ');
writeln;
writeln;
heapsort(A,n);
for k:=1 to n do
write(A[k]:1:10,' ');
writeln;
writeln;
esc:=readkey;
until esc=#27;
end.
Pozostaje jeszcze usunąć rekurencję w obydwu tych algorytmach
Ostatnio zmieniony 7 gru 2016, o 08:00 przez Mariusz M, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 22211
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Najlepszy algorytm sortujący dla OI
Pytanie wydaje się być kompletnie nietrafione.
Czas sortowania zależy od wielu czynników (uporządkowania danych, kosztu porównania, kosztu zamiany itp). Bez tej wiedzy nie da się odpowiedzieć na pytanie. Poza tym wybór pod kątem szybkości jest istotny wtedy, gdy takie sortowanie wykonujemy wiele razy. W przypadku olimpiady nie ma to chyba znaczenia.
Czas sortowania zależy od wielu czynników (uporządkowania danych, kosztu porównania, kosztu zamiany itp). Bez tej wiedzy nie da się odpowiedzieć na pytanie. Poza tym wybór pod kątem szybkości jest istotny wtedy, gdy takie sortowanie wykonujemy wiele razy. W przypadku olimpiady nie ma to chyba znaczenia.