Search code examples
algorithmpseudocodebubble-sortinsertion-sort

Changing Bubble Sort to Insertion Sort with Small change to Iteration


I belive the following pseudocode is correct for the Bubble Sort algorithm:

L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
    FOR J = 1 TO 10 - I
        IF L[J] > L[J + 1] THEN
            TEMP = L[J]
            L[J] = L[J + 1]
            L[J + 1] = TEMP
        ENDIF
    ENDFOR J
ENDFOR I
OUTPUT L

If I change the iteration pattern for I and J, as in the example below, have I converted the algoritm to Insertion Sort please? I'm thinking yes, but I'm surprised it could be so simple, and the various implementations I've seen tend to differ more.

L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
    FOR J = 9 TO I STEP -1
        IF L[J] > L[J + 1] THEN
            TEMP = L[J]
            L[J] = L[J + 1]
            L[J + 1] = TEMP
        ENDIF
    ENDFOR J
ENDFOR I
OUTPUT L

Solution

  • The second algorithm is another version of bubble sort. Instead of moving the largest value towards the end of the array on each pass, it moves the smallest value towards the beginning of the array. In the image below, the first row is the unsorted array, and each subsequent row is the state of the array after one execution of the inner loop. The two characteristics of a bubble sort that are worth noting:

    1. Items to the left of the line are in their final position.
    2. Items to the right are also rearranged, but not necessarily to their final position. For example, on the third line the 2 was moved from the end of the array to the middle. At that point the algorithm found the 1. So it left the 2 behind and starting moving the 1.

    enter image description here

    The image below shows the operation of an insertion sort. Again there are two characteristics worth noting:

    1. The array to the left is in sorted order, but the elements are not in their final position.
    2. Items to the right are completely untouched.

    The general concept of an insertion sort is that the algorithm (conceptually) divides the array into two parts: the sorted portion at the beginning, and the unsorted portion at the end. On each execution of the inner loop, it takes the first element of the unsorted part, and moves it to the left until it is correctly positioned in the sorted part of the array.

    enter image description here