Java

TOPIC 07 – SORTING ARRAYS

LESSON WORK

GROUP TASKS

TASK #1

Examine the differences between the approaches used in:

• Insertion sort
• Selection sort
• Bubble sort
• Merge sort
  
  

TASK #2

Together, we will implement one of Insertion sort, Selection sort or Bubble sort.

TASK #3

We will make use of the Sorting.java class which can be found in the Resources section of the main index file for this course.

Possible things to check:

SWAP

• Check out how swap works and how it is implemented.

SHUFFLE

• Use the shuffle function.
• Maybe use the naiveShuffle function which seems to work well but doesn’t give an equal chance to all possible orders.
• Discuss the shuffle function vs the naiveShuffle function.

TEST INSERTION, SELECTION and BUBBLE SORT

• Test all three algorithms on 10000 elements. Compare how long they take. Which seems to be best?
• How many elements can the best algorithm sort in about 1 second? in about 10 seconds?
• How fast can Java’s built-in sort function sort the same amount of elements?

INDIVIDUAL WORK

QUESTION #1

Is the following array trace showing Insertion Sort, Selection Sort, Bubble Sort or Merge Sort?

A)

B)

C)

D)

QUESTION #2

Consider the array below:

a) Do an array trace of it being sorted with Selection sort.

b) Do an array trace of it being sorted with Insertion sort.

QUESTION #3

Implement the following function:

public static void swap (int[] a, int i, int k)

The function simply swaps the values at element i with the value at element k.