Sortieralgorithmen: Shaker sort / Cocktail sort

in de-stem •  last month 

Der Shaker sort-Algorithmus, oder auch Cocktail sort genannt, ist ein Sortierverfahren welches auf den Bubble sort basiert.

Die Funktionsweise ist folgende: Pro Iteration wird zuerst das größte Element an das Listenende verschoben. Dabei wird der Bubble sort von links nach rechts angewendet. Danach wird die Liste zurück bis zum Listenanfang iteriert und dabei das kleinste Element an den Listenanfang verschoben.

Für den zweiten Durchlauf wird der erste und der letzte Listenindex nicht mehr berücksichtigt, da diese bereits sortiert sind. Ansonsten passiert das gleiche wie vorhin. Es wird das zweitgrößte und das zweitkleinste Element gesucht und an entsprechenden Index verschoben. Der "Schüttelvorgang" wird pro Durchlauf geringer, da die unsortierte Liste immer kleiner wird.

  • Shaker sort (c++)
#include <iostream>

void cocktailSort(int a[], int size) { 
    bool swapped = true; 
    int startIndex = 0; 
    int endIndex = size - 1; 
  
    while(swapped) { 
        swapped = false; 
  
        /* loop from left to right */
        for(int i = startIndex; i < endIndex; ++i) { 
            if (a[i] > a[i + 1]) { 
                std::swap(a[i], a[i + 1]); 
                swapped = true; 
            } 
        } 
  
        /* if nothing is swapped, then the list is sorted */ 
        if(!swapped){
            break;
        } else {
            swapped = false; 
        }
        
        /* last element is sorted, decrement one */ 
        endIndex--; 
  
        /* loop from right to left now */
        for(int i = endIndex - 1; i >= startIndex; --i) { 
            if (a[i] > a[i + 1]) { 
                std::swap(a[i], a[i + 1]); 
                swapped = true; 
            } 
        } 
  
        /* first element is sorted, increment one */
        startIndex++; 
    } 
} 
  
int main()  {
    const unsigned int SIZE = 10;
    int list[SIZE] = {52,34,81,13,12,61,73,11,31,22};
    cocktailSort(list, SIZE); 
  
    for(unsigned int i=0; i<SIZE; i++) {
        std::cout << list[i] << "\n";
    }
    return 0; 
}
  • Quelle
    A comparative Study of Sorting Algorithms Comb, Cocktail and Counting Sorting. In: International Research Journal of Engineering and Technology (IRJET),Volume 4, Issue 1, Januar 2017, p. 1338
Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  


This post has been voted on by the SteemSTEM curation team and voting trail. It is elligible for support from @curie and @minnowbooster.

If you appreciate the work we are doing, then consider supporting our witness @stem.witness. Additional witness support to the curie witness would be appreciated as well.

For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

Please consider using the steemstem.io app and/or including @steemstem in the list of beneficiaries of this post. This could yield a stronger support from SteemSTEM.