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__

- start at the beginning of the array
- check the entire array for the smallest element
- swap the smallest element with the first element
- repeat step 1, but start at the next element of the array (because the first element is done)

__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

## Comments (0)

You don't have permission to comment on this page.