A Examination of a Modified Bubble Sort Algorithm

Author: Kevin Bheemarasetti

Introduction

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. I will introduce a modified version of this algorithm which I am going to call the Chavin Sort, incorporating two additional variables, j, z and m, to track the sorted elements at the end and the beginning of the list respectively which will also decrease the relative size of the array, that is needing to be checked.

Method

The Chavin sort reduces the number of (unnecessary) comparisons and swaps by not considering the elements already sorted. This is achieved by the two variables, j and z. The variable j is used to track the sorted elements at the end of the list, while z is used to track the sorted elements at the beginning of the list. The algorithm reduces the number of comparisons and swaps by not considering the elements already sorted but instead sorting the next relative pairs if necessary (if needed).

Comparison with Bidirectional Bubble Sort

Bidirectional bubble sort, also known as cocktail sort or shaker sort, is a variation of the bubble sort algorithm that works by repeatedly iterating through a list of elements in both directions, swapping adjacent elements that are in the wrong order. The key difference between the Chavin sort and the bidirectional bubble sort lies in the way the sorted elements are tracked.

In the bidirectional bubble sort, the algorithm makes two passes through the list during each iteration one pass from the beginning to the end, and another pass from the end to the beginning. This allows the algorithm to sort both the smallest and largest elements in their correct positions during each iteration.

In contrast, the Chavin sort uses two variables to track the sorted elements at both ends of the list. This allows the algorithm to reduce the number of comparisons and swaps by not considering the elements already sorted. This modification could potentially make the algorithm more efficient than the bidirectional bubble sort, especially for larger lists.

Conclusion

The modified bubble sort algorithm improves the efficiency of the sorting process by reducing the number of comparisons and swaps. This makes it a good option for sorting larger lists where efficiency is a concern. Bubble sort is not the best sorting algorithm, and this is simply a way to add one of the many optimizations that people have made for bubble sort. Although this modification can help performance in some cases, the worst case time complexity for any variant of bubble sort would still be O(n²).

An implementation of Chavin sort in C++ is below:

/*  
    Kevin Bheemarasetti
    Example of Chavin sort

input format:
n
{n numbers}
test inputs:
12
3 1 11 9 2 7 8 5 4 12 6 10

15
5 3 8 1 9 14 2 15 7 4 12 11 6 10 13
*/
#include <iostream>
#include <chrono>
using namespace std;

int main() {
    int n;
    cin >> n;
    int list[n];
    //taking inputs for array
    for (int i = 0; i < n; i++) {
        cin >> list[i];
    }
    bool swapped;
    int j = 1;
    int m = n;
    int z = 0;

    auto start = chrono::high_resolution_clock::now();

    do {
        swapped = false;
        for (int i = 0; i < m-1; i++) {
            if (list[m-j] == m) {
                j++;
                m--;
            } if(list[m-j] < list[m-1-j]) {
                int temp = list[m-j];
                list[m-j] = list[m-1-j];
                list[m-1-j] = temp;
                swapped = true;
            }
            if (list[i+z] == i+1) {
                z++;
            } if (list[i+z] > list[i+1+z]) {
                int temp = list[i+z];
                list[i+z] = list[i+1+z];
                list[i+1+z] = temp;
                swapped = true;
            }
        }
        for (int i = 0; i < n; i++) {
            cout << list[i] << " ";
        }
        cout << endl;
    } while (swapped);
    //stop
    auto stop = chrono::high_resolution_clock::now();

    auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    
    cout << "time (microseconds): " << duration.count() << endl;
    return 0;
}

(this started as a thought experiment, and I later decided to turn it into reality.)