Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

ShellSort Algorithm

Shellsort description + examples german
by

Jeremy Bruns

on 24 June 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ShellSort Algorithm

The ShellSort Algorithm Finally Woher stammt der Name? Das Prinzip Insertionsort vergleicht jedes einzelne Element mit allen übrigen Elemente.

Shellsort Vergleicht Elemente, die weit auseinander liegen. Dadurch bewegen sich Elemente schneller zur Vorderseite. Shellsort
braucht mehr vergleiche als der
Insertionsort Shell & Insertion-Sort Das Problem des Insertionsort ist, dass er viele Schritte bei stark unsortierten Listen braucht .
Es entstand ein Algorithmus, der dieses Problem durch einen Vergleich weit auseinander liegender Elemente löst: Weiteres zum Shell und Insertionsort Bei jedem Durchlauf ist ein Abstand zwischen den Elementen festgelegt.
Dieser Wert wird nach jeder aufeinander folgenden Iteration verringert. Der Shellsort benötigt mehr Vergleiche als der Insertionsort.

Warum sollten wir Ihn überhaupt nutzen? Die Antwort ist ganz einfach:
Wenn die Liste im Shell-sort für Abstand(= i) geordnet ist, ist auch jeder Abstand(=j)
wo j < i ist geordnet! Shellsort insertionsort Reversed ( umgekehrte Reihenfolge ) Vergleich von insertion und Shellsort Listensortierung Nearly Sorted ( fast geordnet ) Shellsort insertionsort Insertionsorts sind am effektivsten bei einer fast geordneten Liste Erster sortier Durchlauf Abstand = 5 a[5] < a[0] a[6] !< a[1] ... a[9] < a[4] Insertion Abstand = 1 Shell Abstand =3 : Lasst uns das nochmal etwas genauer Shellsort ist ein von Donald L. Shell im Jahre 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert. Wie funktioniert der Shellsort? zu erst setzt man eine Vergleichsweite von
n/2
( Abstand = n ; Abstand = Abstand / 2 ) Bei der sortierung von 7 Zahlen hat man eine Vergleichsweite von 7 Elementen.
Daraus ergibt sich ein Abstand von 3, denn
7 / 2 = 3 ( abgerundet! ) Der sortiervorgang ist beendet, wenn der Abstand 1 beträgt und keine weiteren Vertauschungen mehr nötig sind.
z.Bsp. Eine Vergleichsweite von 30 Elementen
30 / 2 = 15 | 7 / 2 = 3
15 / 2 = 7 | 3 / 2 = 1 unter die Lupe nehmen... Vielen Dank für Eure Aufmerksamkeit! :) Presented by Jeremy Bruns $input = array(6, 5, 3, 1, 8, 7, 2, 4);



function shell_sort($arr)

{

$len = count($arr);

$gap = floor($len/2);



while($gap > 0)

{

for($i = $gap; $i < $len; $i++) {



$temp = $arr[$i];

$j = $i;



while($j >= $gap && $arr[$j - $gap] > $temp) {

$arr[$j] = $arr[$j - $gap];

$j -= $gap;

}



$arr[$j] = $temp;

}



$gap = floor($gap/2);

}



return $arr;

}



// 1, 2, 3, 4, 5, 6, 7, 8

shell_sort($input); Der Shellsort. 10 / 2 = Abstand 5 static void Main(string[] args)
{
long[ ] inputArray = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; long j, temp = 0;
int abstand = ( inputArray.Length ) / 2;
while ( abstand > 0 )
{
for ( int index = 0; index < inputArray.Length; index++ )
{
j = index;
temp = inputArray[ index ];
while ( ( j >= abstand ) && inputArray[ j - abstand ] > temp )
{
inputArray[ j ] = inputArray[ j - abstand ];
j = j - abstand;
}
inputArray[ j ] = temp;
}
if ( abstand / 2 != 0 )
abstand = abstand / 2;
else if ( abstand == 1 )
abstand = 0;
else
abstand = 1;
}
} C# Dr.Donald Shell's Variante: Code Review : Endlich verstehe ich den Shellsort. :) Quellen: http://www.stoimen.com/blog/2012/02/27/computer-algorithms-shell-sort/
http://codingvilla.com/shell-sort-csharp-single-article-642.aspx
http://de.wikipedia.org/wiki/Donald_L._Shell
http://de.wikibooks.org/wiki/Algorithmen_und_Datenstrukturen_in_C/_Shellsort
http://www.cs.princeton.edu/~rs/shell/animate.html
http://www.devx.com/vb2themax/Tip/19474
http://www.herongyang.com/Sort/Shell-Sort-Algorithm-Introduction.html
Media:
Google Picture search
www.Prezi.com
http://www.sorting-algorithms.com/shell-sort Gliederung Namensgebung
Shell und Insertionsort - Erklärung, Vergleich und Beispiele
kurzes Code Review
Quellen
Ende
Full transcript