Najlepszy algorytm sortujący dla OI

[Dumel]

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.

[MGT]

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.

[eloar]

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.

[matshadow]

Podpisuję się pod eloarem I tak btw, Dumel, nie wiem czy wiesz ale jest taka sytuacja, kiedy bubblesort zadziała szybciej niż quicksort

[Dumel]

wiem, a insertionsort dla danych niewielkich rozmiarów jest szybszy niż wszystkie pozostałe algorytmy

[Zordon]

Kod: Zaznacz cały

#include <vector>
#include <algorithm>

...

vector<int> V;

...

sort(V.begin(),V.end());

I tyle. Sort z STL jest zaimplementowany tak, że dla kazdych danych ma zlozonosc nlogn.

[Mariusz M]

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)

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.

Heap sort (from Introduction to algorithms)

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

[a4karo]

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.