Shellsort vs Insertionsort

Bei folgendem Code handelt es sich ja um ein Insertion- und ein Shellsort wenn mich nicht alles täuscht:

template<class Ptr, class T>
void insert(Ptr begin, Ptr end, T val, unsigned step = 1)
{
	while(begin < end))
	{
		Ptr last = end;
		last-=step;
		if(val < *last)
		{
			*end = *last;
			end = last;
		}
		else
			break;
	}
	*end = val;
}

template<class Ptr>
void insertion_sort(Ptr begin, Ptr end, unsigned step = 1)
{
	for(Ptr middle=begin; middle < end; middle += step)
		insert(begin, middle, *middle);
}

template<class Ptr>
void shell_sort(Ptr begin, Ptr end)
{
	unsigned step = 3280;
	for(;0 < step; step /= 3)
		insertion_sort(begin, end, step);
	insertion_sort(begin, end, 1);
}

In meinem Buch steht nun drin, dass shell_sort schneller sein soll als insertion_sort.

Um dies zu überprüfen hab ich mir eine Klasse geschrieben die zählt wie oft Objekte verglichen und zugewiesen werden. Ich hab nun ein Array erstellt das zufällig verteilte Instancen meiner Klasse enthält. Ich hab nun mehrere Male insertion_sort(begin, end) und shell_sort(begin, end) drüber laufen lassen (das heist über eine Kopie ansonsten bekämme der eine das Ganze ja fertig vorsortiert). shell_sort brauchte immer ein paar mehr Vergleiche und Zuweisungen, desweiteren sind die Schleifen Konstruktionen von shell_sort grösser als die von insertion_sort also versteh ich nicht wieso shell_sort schneller sein soll als insertion_sort. Ich hab das ganze mit ein paar Arrays der Größen 100, 1000 und 10000 getestet.

DEvent

und was kahm da raus?

übrigens hier ist eine site die sich damit beschäftigt
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortalgo.htm

Sgt. Nukem

ShellSort ist dahingehend schneller, als daß es nicht Inversionen nur benachbarter Elemente durchführt, sondern auch über größere Index-Differenzen.

Allerdings ist die komplette Analyse von ShellSort quasi unmöglich, da es eine bestimmte Folge von Vergleich-Indizes verlangt.
Und davon kann man sich quasi unendlich ausdenken.
Da gibt es halt Folgen, die immer extrem besch..eidene Ergebnisse liefern, und Folgen, die fast immer sehr gute ( N*log(N)² ) Ergebnisse liefern.

Dein Code benutzt eine feste Step-Size - was nicht sehr erfolgversprechend ausschaut.

Ich weiß aber auch net, ob Dein Code so stimmt.

n * log(n)² im best case... pfff

Mit Quicksort vorsortieren und dann InsertionSort, ich glaub viel schneller gehts nicht.

volkard

Optimizer schrieb:

n * log(n)² im best case... pfff
Mit Quicksort vorsortieren und dann InsertionSort, ich glaub viel schneller gehts nicht.

naja, quicksort kackt fürstlich bei bestimmten eingaben ab und wird lahmer als bubblesort.
schlimmerweise sind die bösen eingaben keine wirklich unüblichen eingaben.

also quicksort nur nehmen, wenn man von zufälligen eingaben ausgehen kann. ok, mit quicksort nur ne vorsortierung machen und mit insertionsort den rest. aber was ist mit den bösen eingaben und warum gibt es introsort? warum ist merge-sort bei java so beliebt und warum lebt heap sort noch? fragen über fragen. und ich kenne die antwort auf sie alle. aber du solltest sie selber rausfinden.

Sgt. Nukem

Optimizer schrieb:

Mit Quicksort vorsortieren und dann InsertionSort, ich glaub viel schneller gehts nicht.

Ich würde MergeSort mit InsertSort kombinieren. :p

QuickSort hat zu viele Fallstricke wenn Du nichts dagegen tust. Z.B. bei schon sortierten Feldern als Eingabe -> N² !!
Da nimmst'e dann lieber InsertSort -> N

BTW: HeapSort ist geil, weil es genauso schnell wie MergeSort ist, aber keinen zusätzlichen Speicher braucht.

Sgt. Nukem

Optimizer schrieb:

Mit Quicksort vorsortieren und dann InsertionSort, ich glaub viel schneller gehts nicht.

Kommt immer auf den Fall an.

Dein Ansatz ist z.B. der fälschlichste (sic) wenn Du nur sequentiellen Zugriff auf die Elemente hast (LinkedList z.B.).
Oder Deine zu verschiebenen Datensätze sind riesig groß, und liegen auf externen Datenträgern rum -> besser SelectionSort z.B.

Etc. pp

Ganz genial sind dann natürlich RadixSort und Konsorten....

Ok es geht nun. Es lag an meiner Implementirung:

template<class Ptr>
bool is_empty(Ptr begin, Ptr end)
{
	if(begin == end)
		return true;
	return false;
}

template<class Ptr, class T>
void insert(Ptr begin, Ptr end, T val, unsigned step)
{
	while(!is_empty(begin, end))
	{
		Ptr last = end;
		last -= step;
		if(val < *last)
		{
			*end = *last;
			end = last;
		}
		else
			break;
	}
	*end = val;
}

template<class Ptr>
void insertion_sort(Ptr begin, Ptr end, unsigned step)
{
	unsigned elements_number = static_cast<unsigned>(end-begin);
	for(unsigned start=0; start<step&&start<elements_number; ++start)
		for(Ptr middle=begin+start; middle<end; middle+=step)
			insert(begin+start, middle, *middle, step);
}

template<class Ptr>
void shell_sort(Ptr begin, Ptr end)
{
	unsigned step = 1;
	while(step < static_cast<unsigned>(end - begin))
		step = step*3+1;

	for(;0<step; step /= 3)
		insertion_sort(begin, end, step);
	insertion_sort(begin, end);
}

Ist bei 10000 Elementen um etwa den Faktor 100 schneller als Insertionsort. Bringt also doch ordentlich was.

Danke für eure Hilfe.