Modified Bubble Sort

Introduction

Bubble sort is a simple and widely-used sorting algorithm that compares and
swaps adjacent elements in an array. It is often used as an introduction to sorting algorithms,as it is easy to understand and implement.The algorithm gets its name from the way smaller elements "bubble" to the top of the list as larger elements "sink" to the bottom. The basic idea is that the largest element will "bubble" to the end of the list during each pass through the array. Modified Bubble Sort or Short bubble sort is a variation of the standard bubble sort algorithm that improves the best-case time complexity from O(n^2) to O(n) by using a flag to check if the array is already sorted. This means that if the array is already in order, the algorithm will exit early and not continue making unnecessary passes over the array

Idea behind Bubble Sort

The basic idea behind bubble sort is to repeatedly traverse an
array and compare adjacent elements. If the element at the current position is larger than the element at the next position, the two elements are swapped. This process is repeated until the entire array is sorted in the desired order.
The algorithm starts by comparing the first two elements of the array. If the first element is larger than the second element, they are swapped. The algorithm then moves on to the next pair of elements and repeats the process. This continues until the end of the array is reached.

After the first pass through the array, the largest element will have "bubbled" to the end of the list. The algorithm then repeats the process, but this time ignoring the last element of the array since it is already in its correct position. This continues until the entire array is sorted.

The number of passes required to sort the array is equal to the number of elements in the array minus one. This is because after the first pass, the largest element will have moved to its correct position, and so on.

Modified Bubble Sort

Introduction to Modified Bubble Sort: Short bubble sort is a variation of the standard bubble sort algorithm that improves the best-case time complexity from O(n^2) to O(n) by using a flag to check if the array is already sorted. This means that if the array is already in order, the algorithm will exit early and not continue making unnecessary passes over the array. However, the worst-case time complexity remains O(n^2) as in the original bubble sort.

Bubble sort is a simple and intuitive sorting algorithm that is often used as an introduction to sorting algorithms for beginners. It is a comparison-based sorting algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in the correct order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Basic Idea Behind Modified Bubble Sort: The idea behind short bubble sort is to improve the best-case time complexity of the standard bubble sort algorithm by using a flag to check if the array is already sorted.

In the standard bubble sort algorithm, the algorithm makes n-1 passes through the array, and on each pass, it compares and swaps n-1 pairs of elements. This results in a time complexity of O(n^2) in the worst case, which makes it inefficient for large arrays.

The short bubble sort algorithm improves the best-case time complexity by adding a flag that is set to true at the beginning of each pass. If no exchanges are made during the pass, the flag remains true, indicating that the array is already sorted. In this case, the algorithm can exit early, avoiding unnecessary passes over the array.

By adding this flag, the short bubble sort algorithm checks if the array is already sorted after each pass, and if it is, the algorithm exits early. This results in a best-case time complexity of O(n) when the array is already sorted, making it much more efficient than the standard bubble sort algorithm.

It is important to note that the worst-case time complexity remains O(n^2) as in the original bubble sort. This means that if the array is in reverse order or randomly ordered, the short bubble sort algorithm will still perform poorly. It is generally not recommended to use the short bubble sort algorithm for large arrays or arrays that are not almost sorted.

Algorithm:
Here is the more detailed explanation of how modified bubble or short bubble sort works:

1. Initialize a variable 'flag' to true. This variable will be used to check if the array is already sorted or not.
2. Start a loop for 'i' from 0 to n-1, to make n-1 passes over the array.
3. Within the outer loop, start another loop for 'j' from 0 to n-i-1.
4. Compare the current element (arr[j]) with the next element (arr[j+1]). If thecurrent element is greater than the next element, swap them and set the flag to false.
5. After the inner loop, check the value of the flag. If it is still true, then the array is already sorted, and we can exit the algorithm. If it is false, it means that the array is not sorted yet, and we need to continue with the next pass.
6. Repeat steps 2 to 5 for n-1 passes.
7. The array is now sorted and we can return it as the output.

It is important to note that the outer loop runs for n-1 times, while the inner loop runs for n-i-1 times. This is done to reduce the number of unnecessary comparisons in each pass, as the largest element in the array will be in its correct position after the first pass, the second largest element after the second pass, and so on.

Also, the flag is used to check if any exchange has been made during a pass, if no exchange is made, it means that the array is already sorted and no more iterations are required.

Implementation of Modified Bubble Sort using Python

import time

def short_bubble_sort(arr):
    n = len(arr)
    start_time = time.time()
    for i in range(n):
        flag = True
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = False
        if flag == True:
            break
    end_time = time.time()
    print("Time complexity: ",end_time-start_time)
    return arr

Sample Output

Sorted array is:
Time complexity: 1.9550323486328125e-05
[11, 12, 22, 25, 34, 64, 90]

References:

1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein - This is a widely used textbook in computer science that provides a comprehensive introduction to various algorithms, including bubble sort.
2. "The Art of Computer Programming, Volume 1: Fundamental Algorithms" by Donald E. Knuth - This is a classic book on computer programming that includes a discussion of the bubble sort algorithm.
3. "Sorting Algorithms: An Overview" by Dinesh P. Mehta and Sartaj Sahni - This article provides an overview of various sorting algorithms, including bubble sort and its variants, and its time complexity.

With this article at OpenGenus, you must have the complete idea of Modified Bubble Sort.