Ein Array mit einer gewissen Anzahl von Werten ist zu sortieren. Der Shakersort erledigt dies so:
Er durchläuft das zu sortierende Feld abwechselnd von vorne nach hinten. Dabei tauscht er, wenn er von vorne durchläuft, die Zahlen aus, wenn die erste größer ist als die zweite Zahl, dasselbe passiert analog in der anderen Richtung.
Wie zu erkennen ist, beschreibt der Shakersort eine gewisse Ähnlichkeit mit dem Bubblesort, er ist nämlich eine Erweiterung dessen.
Andere Namen für den Shakersort sind:
Hier sind Pseudocode, ein C++ Code und die Visualisierung dargestellt.
prozedur shakerSort( A : Liste sortierbarer Elemente ) beginn := -1 ende := Länge( A ) - 2 wiederhole vertauscht := falsch beginn := beginn + 1 für jedes i von beginn bis inklusive ende wiederhole falls A[ i ] > A[ i + 1 ] dann vertausche( A[ i ], A[ i + 1 ] ) vertauscht := wahr ende falls ende für falls vertauscht = falsch dann brich wiederhole-solange-Schleife ab ende falls vertauscht := falsch ende := ende - 1 für jedes i von ende bis inklusive beginn wiederhole falls A[ i ] > A[ i + 1 ] dann vertausche( A[ i ], A[ i + 1 ] ) vertauscht := wahr ende falls ende für solange vertauscht prozedur ende
#include <iostream> #include <conio.h> #include <math.h> using namespace std; int main() { int z[6], hilfe; //Array für Zahlen und Variable für die Hilfsvariable. int beginn=-1, ende=4; //Beginn- und Endvariable bool bewegt=false; //Boolean, ob bewegt oder nicht cout<<"Unsortierte Zahlen:\n"; for(int i=0;i<6;i++) { z[i]=rand()%100; if(z[i]<99) z[i]=z[i]++; if(z[i]==z[i-1]) i--; //Wenn gleiche Zahl, nocheinmal berechnen cout<<z[i]<<" "; } cout<<endl<<"Zahlen werden sortiert:\n"; do { bewegt=false; //Am Anfang jeder Schleife wird bewegt auf false gesetzt. beginn++; //Beginn wird erhöht, um unnötige Rechenarbeit zu sparen. for(int j=beginn;j<=ende;j++) //for-Schleife - von beginn bis ende, wenn getauscht werden muss, wird getauscht { if(z[j]>z[j+1]) { hilfe=z[j]; z[j]=z[j+1]; z[j+1]=hilfe; hilfe=0; //Test für Zahlenausgabe nach jedem Schritt for(int h=0;h<6;h++) { cout<<z[h]<<" "; } bewegt=true; cout<<endl; } } if(!bewegt) break; //Wichtiger Schritt: Wenn nichts vertauscht wird, sind die Zahlen bereits geordnet. bewegt=false; //bewegt wegen neuer Schleife auf false gesetzt. ende--; //Ende wird erniedrigt, um Rechenarbeit zu sparen. for(int k=ende;k>=beginn;k--) //for-Schleife - von ende bis beginn, wenn getauscht werden muss, wird getauscht { if(z[k]>z[k+1]) { hilfe=z[k]; z[k]=z[k+1]; z[k+1]=hilfe; hilfe=0; //Test für Zahlenausgabe nach jedem Schritt for(int a=0;a<6;a++) { cout<<z[a]<<" "; } cout<<endl; bewegt=true; } } } while(bewegt); //Solange Zahlen bewegt werden, wird die Schleife ausgeführt. getch(); return 0; }