| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Files spread between Dropbox, Google Drive, Gmail, Slack, and more? Dokkio, a new product from the PBworks team, integrates and organizes them for you. Try it for free today.

View
 

Exercises - Sorting ICS3M

Page history last edited by Steve Sweeney 10 years, 9 months ago

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

 

  1. start at the beginning of the array
  2. check the entire array for the smallest element
  3. swap the smallest element with the first element
  4. 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.