Bubble Sort

What is Bubble Sort?

When neighboring components are arranged incorrectly, the straightforward comparison-based sorting algorithm known as Bubble Sort continuously swaps them. Its name refers to the way that items advance across the list while sorting, much like soda bubbles do in a glass.

Algorithm:

The algorithm works as follows:

1. Starting from the first element, compare the current element with the next element.
2. If the current element is greater than the next element, swap the two elements.
3. Move to the next pair of elements and repeat step 2.
4. Continue this process until the end of the list is reached.
5. Repeat the above steps for n-1 passes where n is the number of elements in the list.

Time Complexity:

• Worst case: O(n^2)
• Best case: Ω(n)
• Average case: Θ(n^2)

Implementation of the algorithm in Java:

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                // swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Note: The outer loop controls the number of passes over the array that the algorithm makes. In each pass, the inner loop compares adjacent elements and swaps them if necessary.

Problems based on Bubble Sort:

• Given an array nums with n objects colored red, white, or blue, sort them in place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library’s sort function.

i.e,

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Solution:

class Solution {
    public static void sortColors(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (nums[j] > nums[j+1]) {
                // swap nums[j] and nums[j+1]
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }
}

}

To represent the colors red, white, and blue as integers, we used the following mapping:

• 0: red
• 1: white
• 2: blue

and used bubble sort to arrange the colors.

• Given the head of a linked list, return the list after sorting it in ascending order.

Example:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
   public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    
    ListNode curr = head;
    int count = 0;
    while (curr != null) {
        count++;
        curr = curr.next;
    }
    
    for (int i = 0; i < count - 1; i++) {
        ListNode prev = null;
        curr = head;
        boolean swapped = false;
        for (int j = 0; j < count - 1 - i; j++) {
            if (curr.val > curr.next.val) {
                ListNode temp = curr.next;
                curr.next = temp.next;
                temp.next = curr;
                if (prev != null) {
                    prev.next = temp;
                } else {
                    head = temp;
                }
                curr = temp;
                swapped = true;
            }
            prev = curr;
            curr = curr.next;
        }
        if (!swapped) {
            break;
        }
    }
    
    return head;
}

}

• Count the number of nodes in the linked list.
• Use two nested loops to perform bubble sort.
• In each iteration of the outer loop, we iterate through the list and compare adjacent nodes. If a node is greater than its next node, we swap the two nodes.
• We keep track of the previous node to update its next pointer after swapping. If we don’t perform any swaps in an iteration of the outer loop, we know that the list is already sorted and we can break out of the loop.
• Finally, return the sorted linked list.

Note: also read about Sorting in DSA

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py