cocktail Shaker Sort Algorithm

Shaker Sort Algorithm, also known as Cocktail Sort or Bidirectional Bubble Sort, is a variation of the Bubble Sort Algorithm that sorts a given data set by comparing and swapping adjacent elements in two alternating directions - left to right, and right to left. The two-directional sorting mechanism allows the algorithm to eliminate the so-called "turtle" elements, which are small elements located towards the end of the list that take a long time to be sorted using a standard Bubble Sort. By sorting in two directions, Shaker Sort can move these small elements to their correct positions more quickly, leading to a more efficient sorting process. In the Shaker Sort Algorithm, the elements are first sorted from left to right, comparing adjacent pairs and swapping them if they are in the wrong order. This process is repeated until the end of the list is reached, placing the largest element in its correct position. The sorting process then reverses direction, moving from right to left, comparing and swapping elements in a similar fashion to place the smallest unsorted element in its proper position. This bidirectional process continues, with the endpoints of the unsorted section moving inward after each pass, until the entire list is sorted. Although Shaker Sort exhibits better performance than Bubble Sort on certain data sets, it still has an average-case and worst-case time complexity of O(n^2), making it less suitable for large data sets when compared to more efficient sorting algorithms like Merge Sort or Quick Sort.
/*
 * Cocktail shaker sort is a sort algorithm that is a bidirectional bubble sort
 * more information: https://en.wikipedia.org/wiki/Cocktail_shaker_sort
 * more information: https://en.wikipedia.org/wiki/Bubble_sort
 *
 */
function cocktailShakerSort (items) {
  for (let i = items.length - 1; i > 0; i--) {
    let swapped = false
    let j

    // backwards
    for (j = items.length - 1; j > i; j--) {
      if (items[j] < items[j - 1]) {
        [items[j], items[j - 1]] = [items[j - 1], items[j]]
        swapped = true
      }
    }

    // forwards
    for (j = 0; j < i; j++) {
      if (items[j] > items[j + 1]) {
        [items[j], items[j + 1]] = [items[j + 1], items[j]]
        swapped = true
      }
    }
    if (!swapped) {
      return
    }
  }
}

// Implementation of cocktailShakerSort

var ar = [5, 6, 7, 8, 1, 2, 12, 14]
// Array before Sort
console.log(ar)
cocktailShakerSort(ar)
// Array after sort
console.log(ar)

LANGUAGE:

DARK MODE: