1. Bubble Sort
(a) Write a program that uses an array with 5 elements. Fill the array with random numbers between 1 and 9. Output the array to the screen on a single line. Use nice formatting (i.e., proper spacing between elements).
Sample Output:
Array Data: 3 8 2 5 1
(b) Add to the program from part (a) by sorting your data using the bubble sort algorithm. Output your new, sorted array below the original data. Turing Solution
Sample Output:
Array Data: 3 8 2 5 1
Sorted Data: 1 2 3 5 8
Using pseudocode (which is like Turing, but not quite), the algorithm might look like this:
loop
swaps <-- 0
for i = 2 to length(array)
if array(i-1) > array(i) then
temp <-- array(i-1)
array(i-1) <-- array(i)
array(i) <-- temp
swaps <-- swaps + 1
end if
end for
until no swaps were needed
Why do we count the swaps? If no swaps were needed, then the array is in order, and we're done!
Why does the for loop start at 2? We always compare two elements of the array, so the number of "compares" must be one less than the size of the array (we could also loop from 1 to (size-1))
(c) Modify your program so you keep track of the total # of swaps required to sort the array. Output this data after the sorted array.
Sample Output:
Array Data: 3 8 2 5 1
Sorted Data: 1 2 3 5 8
total swaps = 7
(d) Modify your program so you keep track of the total # of comparisons required to sort the array. Output this data after the sorted array.
Sample Output:
Array Data: 3 8 2 5 1
Sorted Data: 1 2 3 5 8
total swaps = 7
total compares = 16
(e) Modify your program so that you perform a sort N times (as specified by the user). Each sort should use a new list of randomly generated values.
(f) Modify the program so the arrays are no longer displayed. The only output should be the average number of swaps and comparisons.
(g) Modify the program to use larger arrays. One way to do this is to have the user specify the number of elements. You might also want to move some of your code into procedures.
# 2 - Selection Sort
Using your work from #1 (bubble sort), implement the selection sort algorithm for steps (b), (c) and (d). You should be able to reuse most of your code from #1. Make sure you save your new work with new file names (so you don't lose the previous work).
Selection Sort Algorithm #1 - in plain english
Selection Sort Algorithm #2 - in pseudocode
start = 1
for i = start to end(array)
# assume the first element is the smallest (for now)
smallest = start
# check the rest of the array against the smallest element
for j = start+1 to end(array)
if array(j) < array(smallest) then
# record the new smallest element position
smallest = j
end if
end for
# now that we have found the smallest element, swap it with the start of the array
# only do this if they are now the same element!
if smallest != start then
temp = array(start)
array(start) = array(smallest)
array(smallest) = temp
end if
end for
(***) Challenge - Can you make a Turing program that does something similar to this web page (i.e., it could be used to teach how the bubble sort works). Sorting with Animated Code