Shaker Sort In C++

Introduction

Sorting techniques play a vital role in the field of computer science and have a significant influence on different domains, such as data analysis, database systems, and routine activities like arranging files on your device. The Shaker Sort, alternatively referred to as Cocktail Sort or Ripple Sort, stands out as a sorting algorithm within the array of choices. It presents a sophisticated variation of the Bubble Sort method.

Shaker Sort was created to address a drawback of Bubble Sort, which involves iterating through the entire array in each pass, even after larger elements are already sorted. Through the utilization of comparison and swapping strategies, Shaker Sort enhances array traversal efficiency by operating from both ends simultaneously, thereby minimizing the number of comparisons and swaps needed.

This guide explores the inner workings of Shaker Sort, examines its time complexity, and offers guidance on implementing it in C++. We will detail the algorithm's functionality, assess its efficiency, and compare it with other common sorting methods. Furthermore, we present a C++ code example for Shaker Sort that you can utilize in your projects or further explore its features.

Understanding sorting techniques is essential in the field of computer science, playing a crucial role in problem-solving strategies. It is vital to comprehend the strengths and constraints of these methods. Whether you are a learner, a programmer, or an individual interested in expanding your knowledge, this article provides an in-depth look at Shaker Sort and its practical implementations.

Exploring the Shaker Sorting Technique

• ✅ The process commences with a disordered array of items.
• ✅ The array is divided into two segments: one sorted and one unsorted
• ✅ Initially, the entire array is deemed unsorted.
• ✅ A sequence of passes in both directions is executed: left to right and right to left.
• ✅ During each pass, neighbouring elements are compared and interchanged if necessary.

Passing from Left to Right:

• ✅ Progresses from left to right.
• ✅ Compares adjacent elements.
• ✅ If the element on the left is larger than the one on the Right, they are swapped.
• ✅ Continues until reaching the end of the array.
• ✅ The largest element moves towards the Right in the section.

Passing from Right to Left:

• ✅ Changes direction and moves from Right to left.
• ✅ Compares adjacent elements.
• ✅ Swaps them if the element on the Right is smaller than its neighbour on the left.
• ✅ Iterates until reaching the beginning of the array.
• ✅ The smallest element shifts towards the far left in the unsorted section.

Expanding the Range of the Unordered Section:

After every two-way traversal, a new item is included on both sides to enlarge the ordered portion.

Consequently, the unordered section diminishes in size.

Stopping Condition:

• ✅ The algorithm keeps doing back-and-forth passes.
• ✅ It stops when no exchanges are needed in a left-to-right and right-to-left-right pass.
• ✅ This signals that the whole array is sorted.

Key Benefits:

• ✅ Swapping bidirectionally reduces unnecessary comparisons and swaps.
• ✅ Effective for arrays with some order or few inversions.
• ✅ You can picture elements moving back and forth like they're being gently nudged into place.

The Approach of Exchanging Elements in Two Directions

• ✅ How Shaker Sort differs from the conventional Bubble Sort method.
• ✅ Requires moving through the array in two opposite directions: from left to right and from right to left.

Left-to-Right Pass:

• ✅ Iterates from the leftmost index to the rightmost index.
• ✅ Compares each pair of adjacent elements.
• ✅ If the left element is greater than the right element, swap them.
• ✅ Ensures the largest element gets "bubbled up" towards the right end.

When performing the right-to-left-right pass in Shaker Sort:

• ✅ Begin after completing the left-to-right pass.
• ✅ Go through elements from the rightmost to the leftmost index.
• ✅ Compare elements and swap them if the right one is smaller than the left one.
• ✅ This process ensures that the smallest element moves towards the left end efficiently.

Benefits of this approach include:

• ✅ Reducing unnecessary comparisons and swaps.
• ✅ Avoiding redundant comparisons with already sorted elements.
• ✅ Being effective for partially sorted arrays or arrays with few inversions.

To illustrate this procedure:

• ✅ Components are shifted to and fro as if shaken or rippled.
• ✅ Bigger elements progressively slide towards the right side, whereas smaller ones shift towards the left side.

As this two-way pass progresses:

• ✅ The section that is sorted increases from both directions during each cycle.
• ✅ Simultaneously, the segment that remains unsorted decreases until no further exchanges are required in a single pass.

The termination condition is met when:

• ✅ There is no requirement for any swaps in either direction, indicating that the complete array is in a sorted order.

The effectiveness of Shaker Sort stems from its unique swapping approach, giving it an advantage over Bubble Sort when dealing with arrays that are partially ordered or contain minimal inversions.

Implementing Shaker Sort in C++

#include <iostream>
#include <vector>

using namespace std;

void shakeSort(vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;
    bool swapped = true;

    while (swapped) {
        swapped = false;

        // Left to right pass
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }

        right--;

        //Right to left pass
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i - 1]) {
                swap(arr[i], arr[i - 1]);
                swapped = true;
            }
        }

        left++;
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};

    cout << "Unsorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    shakeSort(arr);

    cout << "Sorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

Unsorted array: 64 34 25 12 22 11 90 

Sorted array: 11 12 22 25 34 64 90

Explanation:

1. We create a function called shakeout that accepts a reference to a std::vector containing integers.
2. Initially, we set up two pointers, left and right, pointing to the array's beginning and end.
3. Moreover, a Boolean variable named swapped is initialized to track whether any swaps occurred in the iteration.
4. The primary loop continues as the swap remains true, indicating swaps and an unsorted array.
5. Within the loop, we start with a to-right scan;

We progress from the left to the right when comparing elements.

If the value on the left side is larger than the value on the right side, we swap them and then mark swapped as true.

Following this iteration, we reduce the Right index to exclude the element at the end from upcoming comparisons.

1. Afterward, we continue with a scan from right to left;

We iterate from the right side to the left side + 1 when comparing elements sequentially.

When facing a scenario where a component on the right side is less than its equivalent on the left, we interchange them and appropriately adjust the swapped variable. Throughout the cycle, we shift the pointer from right to left to eliminate the sorted component in the subsequent run. This sequence persists until no further swaps occur in a run, signifying that the array is now arranged in a sorted manner.

This approach relies on the Shaker Sort technique, which includes traversing in two directions, exchanging elements that are out of order, and progressively narrowing down the array segment from both ends.

Benefits of Shaker Sort

• ✅ Effective for Arrays with Some Order: Shaker Sort works efficiently on arrays that are partially sorted or have out-of-order elements. It minimizes comparisons and swaps by moving between left-to-right and right-to-left passes.
• ✅ Superior Performance over Bubble Sort: Despite having the time complexity of Bubble Sort (O(n²)) , Shaker Sort generally performs better in real-world scenarios due to its two-way swapping technique, which reduces the number of necessary comparisons and swaps.
• ✅ Responsive: Shaker Sort is an algorithm that makes use of the sorted nature of the input array to decrease the number of comparisons and swaps required.
• ✅ Memory Efficient: Shaker Sort is an in-place sorting algorithm That sorts the array without needing memory equal to the input array's size.
• ✅ Implementation: The algorithm is quite simple to understand and apply, making it a good choice for situations where simplicity is important.

Downsides of Shaker Sort

• ✅ Challenges with Arrays: While Shaker Sort performs well with organized arrays, its efficiency decreases significantly when dealing with large, highly disorganized arrays. In these cases, opting for efficient sorting methods like Quicksort or Mergesort would be more beneficial.
• ✅ Unfavourable Worst-Case Time Complexity: Like Bubble Sort, Shaker Sort has a worst-case time complexity of O(n²), making sorting datasets that lack organization inefficient.
• ✅ Swaps: Despite its back-and-forth approach, Shaker Sort still conducts swaps when elements are already in their correct positions, although fewer than Bubble Sort.
• ✅ Not Suitable for Sorting Linked Lists: Designed for arrays, Shaker Sort is not suitable for sorting linked lists because it requires accessing elements by their indices.
• ✅ Lack of Adaptability for Parallel Processing: Shaker Sort is not easily adaptable to processing, making it less ideal for processing environments compared to algorithms like Mergesort or Radix Sort.

In summary, Shaker Sort is a suitable option for sorting arrays that are partially sorted or have minimal disorder. Nevertheless, it may not be the optimal method for large, highly disorganized arrays or situations where time optimization is critical. Its simple methodology and capability to operate within memory constraints make it beneficial for educational use or scenarios where memory restrictions are a factor.