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
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:
The image below shows the operation of an insertion sort. Again there are two characteristics worth noting:
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.