Sortieralgorithmen: Shaker sort / Cocktail sort

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 

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