Classwork:
1. Create 3 data sets of 5000 integers: (USE ARRAYS and the light version of the quicksort algorithm)

Data Set A: randomly generate the data in range from 1 to 5000.

Data Set B: generate integers in range from 1 to 5000 (no duplicates) sorted in ascending order.

Data Set C: generate integers in range from 1 to 5000 (no duplicates) sorted in descending order.

1. Set up counters in your quick sort trace program and run the three sets separately.
2. Find an approximate expression that relates the size of the data to the number of comparisons or visits or swaps to the data.
3. Make a conclusion about the three different cases.

Sorting Project

Due date: February 26th, 2016

You are to write a program that tests each of five sorting algorithms with arrays of random integer values of four different sizes. You will need to keep count of the number of times the innermost steps of the sort algorithm are executed in order to judge the relative Big-O of each sort.

The five algorithms are: selection sort, insertion sort, bubble sort, quicksort and merge sort.

The array sizes to use are: 10, 100, 1000, and 5000.

The Counter class and also a class that generates arrays of random integers are below.

You will need to modify the sort code to include an increment to the counter where appropriate.

The main part of this project is the design and implementation of a driver program that will test the sorts on the same set of arrays.

1. It should keep track of the count result for each sort for each array size and generate a table to summarize the results. A sample table is given below.

1. It should create a scatter plot for each of the sorts. The plot could be either text based or as a GUI. You can also use a program excel.

2. Source code available for you to use but you can have your own program for this project.

public class Counter

{
    private static int count = 0;

    public static int getcount( )

    {
        return count;
    }

    public static void reset( )
    {
        count = 0;
    }

    public static void increment( )
    {
        count++;
    }
}

import java.util.Random;

public class RandomIntArray
{
    public static int[ ] generateArray( int n )
    {
    // generates an array of length n populated
    // with random integers

        int[ ] result = new int[n];
                Random random = new Random();
        for (int i = 0; i < n; i++)

            result[i] = random.nextInt(5*n);

        return result;
    }
}

Bubble Sort — fixed number of passes
This version of bubble sort makes a fixed number of passes (length of the array – 1). Each inner loop is one shorter than the previous one.

public static void bubbleSort1(int[] x) {
    int n = x.length;
    for (int pass=1; pass < n; pass++) {  // count how many times
        // This next loop becomes shorter and shorter
        for (int i=0; i < n-pass; i++) {
            if (x[i] > x[i+1]) {
                // exchange elements
                int temp = x[i];  
                x[i] = x[i+1];  
                x[i+1] = temp;
            }
        }
    }
}

Homework:
Start working on the project.