Bubble Sort Analogy: Step-by-Step

Initial Value in Bubble Sort Algorithm

In the Bubble Sort algorithm, the initial values typically refer to the starting points for comparison and iteration through the array. The main variables include the array length (n) and the loop counters (i and j), which control the number of passes and element comparisons.

Key Initial Values in Bubble Sort

• Array Length (n): The total number of elements in the array to be sorted.
• Outer Loop Counter (i): Starts at 0 and runs until n - 1, representing each pass through the array.
• Inner Loop Counter (j): Starts at 0 for each pass and runs until n - i - 1, comparing adjacent elements.

Example Initialization

For an array like [5, 3, 8, 4, 2], the initial setup is:

        int n = 5;

        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]
                }

           }
        }
    

In the first pass (i = 0):

• Comparisons: (5,3), (5,8), (8,4), (8,2)
• Largest element (8) moves to the end.

In the second pass (i = 1):

• Comparisons: (3,5), (5,4), (5,2)
• Next largest element (5) moves before 8.

Why These Initial Values Matter

• They control the number of comparisons and swaps per pass.
• They ensure elements “bubble up” in correct order after each pass.
• They maintain the algorithm’s time complexity of O(n²).

Visualization of Passes

        Initial: [5, 3, 8, 4, 2]
        Pass 1:  [3, 5, 4, 2, 8]
        Pass 2:  [3, 4, 2, 5, 8]
        Pass 3:  [3, 2, 4, 5, 8]
        Pass 4:  [2, 3, 4, 5, 8]
        Sorted:  [2, 3, 4, 5, 8]    
    

References

• Bubble sort in 2 minutes - Michael Sambol - YouTube

Data Structures and Algorithms Official Website