Add Headings and they will appear in your table of contents.
4.2.1 Describe the characteristics of standard algorithms on linear arrays.
Bubble Sort Algorithm
Bubble sort is an introductory sorting algorithm that iterates through a list and compares pairings of adjacent elements. Adjacent means side by side. Left element is compared to the right and if the left is greater than the right, swap the elements or the values.
According to the sorting criteria, the algorithm swaps elements to shift elements towards the beginning or end of the list.
Bubble Sort example question:
Write a pseudocode using Bubble Sort to sort the values in the given array VALUES = [20, 6, 38, 50, 40] in ascending order.
Bubble Sort in Plain English Version 1: [Using two (2) from/to loops]
1. Create the outer loop / 1st loop. Iteration from 0 to [length - 3] // 0 to (5-3)
2. Create the inner loop / 2nd loop. Iteration from 0 to [length - 2] // 0 to (5-2)
3. Inside the 2nd loop / inner loop. Compare the left element with the right element. If the left element is greater than the right element then swap them.
4. For this algorithm, iteration or loop will be performed 12 times.
Bubble Sort Pseudocode Version 1:
VALUES = [20, 6, 38, 50, 40]
loop X from 0 to 2 // inclusive of 2 since this is Pseudocode
loop Y from 0 to 3 // inclusive of 3 since this is Pseudocode
if VALUES[Y]>VALUES[Y+1] then
TEMP = VALUES[Y]
VALUES[Y]=VALUES[Y+1]
VALUES[Y+1]=TEMP
end if
end loop
end loop
Python Code Version 1:
VALUES = [20, 6, 38, 50, 40]
for X in range (0,3): # Excluding 3 so 3 times only
for Y in range(0,4): # Excluding 4 so 4 times only
if VALUES[Y]>VALUES[Y+1]:
TEMP = VALUES[Y]
VALUES[Y]=VALUES[Y+1]
VALUES[Y+1]=TEMP
print (VALUES)
Bubble Sort in Plain English Version 2: (using a FLAG to stop immediately)
1. Create an inner loop/2nd loop (inside 1st loop) from 0 until [Number of Elements - 1]
2. Compare the left element with the right element. If the left element is greater than the right element then we swap them and FLAG = TRUE to indicate a swapped took place.
3. Create an outer loop/1st loop. Outer loop will be performed while FLAG is TRUE. Meaning, there was a swap that took place.
4. Inside the outer loop and just above the inner loop. Set FLAG = FALSE. This will terminate the outer loop once no more swap happened. Inner loop will change it to TRUE when a swap happened.
5. For this algorithm, iteration / loop will be performed 8 times.
Note: You can also change the order above by using steps 4, 3, 1, 2.
Bubble Sort Pseudocode Version 2: (using a FLAG to stop immediately)
Answer:
LIMIT = 4
FLAG = TRUE
loop while FLAG = TRUE
FLAG = FALSE
loop COUNTER from 0 to LIMIT - 1 // loop from 0 to 3 which means 4 iterations
if VALUES[COUNTER] > VALUES[COUNTER+1] // left is greater than the right
TEMPORARY = VALUES[COUNTER]
VALUES[COUNTER] = VALUES[COUNTER+1]
VALUES[COUNTER+1] = TEMPORARY
FLAG = TRUE // TRUE indicates that there was a swapped that happened
end if
end loop
end loop