Bubble Sort

Initial Array

[6, 2, 9, 0, 1, 5, 8, 7]

Step-by-Step Process

First Pass:

Compare \(6\) and \(2\):

\(6 > 2\) ? Swap ? [2, 6, 9, 0, 1, 5, 8, 7]

Compare \(6\) and \(9\):

\(6 < 9\) ? No swap ? [2, 6, 9, 0, 1, 5, 8, 7]

Compare \(9\) and \(0\):

\(9 > 0\) ? Swap ? [2, 6, 0, 9, 1, 5, 8, 7]

Compare \(9\) and \(1\):

\(9 > 1\) ? Swap ? [2, 6, 0, 1, 9, 5, 8, 7]

Compare \(9\) and \(5\):

\(9 > 5\) ? Swap ? [2, 6, 0, 1, 5, 9, 8, 7]

Compare \(9\) and \(8\):

\(9 > 8\) ? Swap ? [2, 6, 0, 1, 5, 8, 9, 7]

Compare \(9\) and \(7\):

\(9 > 7\) ? Swap ? [2, 6, 0, 1, 5, 8, 7, 9]

End of First Pass: Largest element \(9\) has bubbled to the last position.

Array after first pass: [2, 6, 0, 1, 5, 8, 7, 9]

Second Pass:

Compare \(2\) and \(6\):

\(2 < 6\) ? No swap ? [2, 6, 0, 1, 5, 8, 7, 9]

Compare \(6\) and \(0\):

\(6 > 0\) ? Swap ? [2, 0, 6, 1, 5, 8, 7, 9]

Compare \(6\) and \(1\):

\(6 > 1\) ? Swap ? [2, 0, 1, 6, 5, 8, 7, 9]

Compare \(6\) and \(5\):

\(6 > 5\) ? Swap ? [2, 0, 1, 5, 6, 8, 7, 9]

Compare \(6\) and \(8\):

\(6 < 8\) ? No swap ? [2, 0, 1, 5, 6, 8, 7, 9]

Compare \(8\) and \(7\):

\(8 > 7\) ? Swap ? [2, 0, 1, 5, 6, 7, 8, 9]

End of Second Pass: Largest element \(8\) is now in its correct position.

Array after second pass: [2, 0, 1, 5, 6, 7, 8, 9]

Third Pass:

Compare \(2\) and \(0\):

\(2 > 0\) ? Swap ? [0, 2, 1, 5, 6, 7, 8, 9]

Compare \(2\) and \(1\):

\(2 > 1\) ? Swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare \(2\) and \(5\):

\(2 < 5\) ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare \(5\) and \(6\):

\(5 < 6\) ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare \(6\) and \(7\):

\(6 < 7\) ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

End of Third Pass: The next largest element \(7\) is now in its correct position.

Array after third pass: [0, 1, 2, 5, 6, 7, 8, 9]

Fourth Pass:

Compare \(0\) and \(1\):

\(0 < 1\) ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare \(1\) and \(2\):

\(1 < 2\) ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare \(2\) and \(5\):

\(2 < 5\) ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare \(5\) and \(6\):

\(5 < 6\) ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

Compare \(6\) and \(7\):

\(6 < 7\) ? No swap ? [0, 1, 2, 5, 6, 7, 8, 9]

End of Fourth Pass: The array remains sorted, indicating that sorting is complete.

Array after fourth pass: [0, 1, 2, 5, 6, 7, 8, 9]

Selection Sort

The input array is

[2, 6, 5, 1, 3, 4]

The outer loop will iterate over each index of the array except the last one, as it will already be sorted after the previous iterations.

First Pass (i = 0):

Current Minimum Index (cm): \(0\) (pointing to \(2\))

Inner Loop:

Compare \(6\) with \(2\): No change (2 remains the minimum).

Compare \(5\) with \(2\): No change (2 remains the minimum).

Compare \(1\) with \(2\): \(1 < 2\) ? Update cm to \(3\) (pointing to \(1\)).

Compare \(3\) with \(1\): No change (1 remains the minimum).

Compare \(4\) with \(1\): No change (1 remains the minimum).

Swap: Swap the element at index \(0\) with the element at index \(3\).

Array After First Pass: [1, 6, 5, 2, 3, 4]

Second Pass (i = 1):

Current Minimum Index (cm): \(1\) (pointing to \(6\))

Inner Loop:

Compare \(5\) with \(6\): \(5 < 6\) ? Update cm to \(2\) (pointing to \(5\)).

Compare \(2\) with \(5\): \(2 < 5\) ? Update cm to \(3\) (pointing to \(2\)).

Compare \(3\) with \(2\): No change (2 remains the minimum).

Compare \(4\) with \(2\): No change (2 remains the minimum).

Swap: Swap the element at index \(1\) with the element at index \(3\).

Array After Second Pass: [1, 2, 5, 6, 3, 4]

Third Pass (i = 2):

Current Minimum Index (cm): \(2\) (pointing to \(5\))

Inner Loop:

Compare \(6\) with \(5\): No change (5 remains the minimum).

Compare \(3\) with \(5\): \(3 < 5\) ? Update cm to \(4\) (pointing to \(3\)).

Compare \(4\) with \(3\): No change (3 remains the minimum).

Swap: Swap the element at index \(2\) with the element at index \(4\).

Array After Third Pass: [1, 2, 3, 6, 5, 4]

Fourth Pass (i = 3):

Current Minimum Index (cm): \(3\) (pointing to \(6\))

Inner Loop:

Compare \(5\) with \(6\): \(5 < 6\) ? Update cm to \(4\) (pointing to \(5\)).

Compare \(4\) with \(5\): \(4 < 5\) ? Update cm to \(5\) (pointing to \(4\)).

Swap: Swap the element at index \(3\) with the element at index \(5\).

Array After Fourth Pass: [1, 2, 3, 4, 5, 6]

Fifth Pass (i = 4):

Current Minimum Index (cm): \(4\) (pointing to \(5\))

Inner Loop:

Compare \(6\) with \(5\): No change (5 remains the minimum).

No Swap Needed: Since cm is still \(4\), the array remains the same.

Array After Fifth Pass: [1, 2, 3, 4, 5, 6]

Insertion Sort:

Initial Array

Input Array:

[2, 6, 5, 1, 3, 4]

Algorithm Explanation

Insertion sort works by building a sorted portion of the array one element at a time. It takes each element from the unsorted part and finds its correct position in the sorted part.

Step-by-Step Process

Initialization:

The input array is [2, 6, 5, 1, 3, 4]. The outer loop starts at index \(1\) (the second element), treating the first element as a sorted list of one element.

First Pass (i = 1):

Current Element: \(6\)

Comparison:

Compare \(6\) with \(2\) (the element before it):

2 < 6: No swap needed.

Array After First Pass:

[2, 6, 5, 1, 3, 4]

Second Pass (i = 2):

Current Element: \(5\)

Comparison:

Compare \(5\) with \(6\):

6 > 5: Swap ? [2, 5, 6, 1, 3, 4]

Now compare \(5\) with \(2\):

2 < 5: No swap needed.

Array After Second Pass:

[2, 5, 6, 1, 3, 4]

Third Pass (i = 3):

Current Element: \(1\)

Comparison:

Compare \(1\) with \(6\):

6 > 1: Swap ? [2, 5, 1, 6, 3, 4]

Compare \(1\) with \(5\):

5 > 1: Swap ? [2, 1, 5, 6, 3, 4]

Compare \(1\) with \(2\):

2 > 1: Swap ? [1, 2, 5, 6, 3, 4]

Array After Third Pass:

[1, 2, 5, 6, 3, 4]

Fourth Pass (i = 4):

Current Element: \(3\)

Comparison:

Compare \(3\) with \(6\):

6 > 3: Swap ? [1, 2, 5, 3, 6, 4]

Compare \(3\) with \(5\):

5 > 3: Swap ? [1, 2, 3, 5, 6, 4]

Compare \(3\) with \(2\):

2 < 3: No swap needed.

Array After Fourth Pass:

[1, 2, 3, 5, 6, 4]

Fifth Pass (i = 5):

Current Element: \(4\)

Comparison:

Compare \(4\) with \(6\):

6 > 4: Swap ? [1, 2, 3, 5, 4, 6]

Compare \(4\) with \(5\):

5 > 4: Swap ? [1, 2, 3, 4, 5, 6]

Compare \(4\) with \(3\):

3 < 4: No swap needed.

Array After Fifth Pass:

[1, 2, 3, 4, 5, 6]