Scientific Programming II

Programming in Java

Sorting Test

Due Date: January 8, 2015

Problem 1 (10 Points)

Insertion Sort

Visual example from Virginia Tech

Insertion sort is a special type of sorting algorithm that sorts a collection as the collection is built. Or, in fancy Wikipedia jargon:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

• Simple implementation
• Efficient for (quite) small data sets
• More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
• Adaptive, i.e., efficient for data sets that are already substantially sorted
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it
  When people manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.

Insertion sort is similar to that of selection sort in that a marker for the beginning of the unsorted part of the collection is kept.

Here is a pseudocode implementation of the insertion sort:

func insertionSort(arr)
    for 1...length[arr]
        tmp  <- arr[i]
        j    <- i - 1
        done <- false
        while (not done)
            if arr[j] > tmp then
                arr[j+1] = arr[j]
                j--
                if j < 0 done <- true
            else
                done <- true
        endwhile
        arr[j+1] <- tmp
    endfor
endfunc

Note: In psuedocode, <- means assignment and = means equality

Write a method public void insertionSort(int[] arr) that sorts an integer array.

Problem 2 (20 Points)

Bucket Sort

A bucket sort begins with a one-dimensional array of positive integers to be sorted and a two-dimensional array of integers with rows indexed from 0 to 9 and columns indexed from 0 to n – 1, where n is the number of values to be sorted. Each row of the two-dimensional array is referred to as a bucket. The bucket sort algorithm operates as follows:

1. Place each value of the one-dimensional array into a row of the bucket array, based on the value’s “ones” (rightmost) digit. For example, 97 is placed in row 7, 3 is placed in row 3 and 100 is placed in row 0. This procedure is called a distribution pass.
2. Loop through the bucket array row by row, and copy the values back to the original array. This procedure is called a gathering pass. The new order of the preceding values in the one-dimensional array is 100, 3 and 97.
3. Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.). On the second (tens digit) pass, 100 is placed in row 0, 3 is placed in row 0 (because 3 has no tens digit) and 97 is placed in row 9. After the gathering pass, the order of the values in the one-dimensional array is 100, 3 and 97. On the third (hundreds digit) pass, 100 is placed in row 1, 3 is placed in row 0 and 97 is placed in row 0 (after the 3). After this last gathering pass, the original array is in sorted order.

Note that the two-dimensional array of buckets is 10 times the length of the integer array being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memory—the bubble sort requires space for only one additional element of data. This comparison is an example of the space–time trade-off: The bucket sort uses more memory than the bubble sort, but performs better. This version of the bucket sort requires copying all the data back to the original array on each pass.

One pseudocode implementation could be as follows:

func bucketSort(arr)
    max <- max value in arr
    digits <- number of digits in max

    for 0 to (digits - 1)
        // implement program here
    endfor
endfunc

Write a method public void bucketSort(int[] arr) that sorts an integer array using the bucket sort algorithm described above. Your output need not be justified, but should be legible.

Example I/O

Input Array: 25 346 12 8 55 355 155  
 
 
Pass#1:
Values in the Matrix:
0  0  12  0  0  25  346  0  8  0 
0  0  0   0  0  55  0    0  0  0 
0  0  0   0  0  355 0    0  0  0 
0  0  0   0  0  155 0    0  0  0 
0  0  0   0  0  0   0    0  0  0 
0  0  0   0  0  0   0    0  0  0 
0  0  0   0  0  0   0    0  0  0 
 
Array: 12 25 55 355 155 346 8  
 
Pass#2:
Values in the Matrix:
8   12  25  0   346  55   0  0  0  0 
0   0   0   0   0    355  0  0  0  0 
0   0   0   0   0    155  0  0  0  0 
0   0   0   0   0    0    0  0  0  0 
0   0   0   0   0    0    0  0  0  0 
0   0   0   0   0    0    0  0  0  0 
0   0   0   0   0    0    0  0  0  0 
 
Array: 8 12 25 346 55 355 155  
 
 
Pass#3:
Values in the Matrix :
8   155  0  346  0  0  0  0  0  0 
12  0    0  355  0  0  0  0  0  0 
25  0    0  0    0  0  0  0  0  0 
55  0    0  0    0  0  0  0  0  0 
0   0    0  0    0  0  0  0  0  0 
0   0    0  0    0  0  0  0  0  0 
0   0    0  0    0  0  0  0  0  0 
 
Array: 8 12 25 55 155 346 355