Classwork:
The purpose of this assignment is to observe the different performance of the quick sort based on the data.
- Create 3 data sets of 50,000 integers:
Data Set A: randomly generate the data in range from 1 to 50,000.(no duplicates)
Data Set B: generate integers in range from 1 to 50,000 sorted in ascending order.
Data Set C: generate integers in range from 1 to 50,000 sorted in descending order.
- Set up a counter in your quick sort trace program and run the three sets separately.
Your results will be meaningful depending where you put the counter. So be mindful of what you are trying to achieve. -
Find an expression that relates the size of the data to the number of comparisons or visits to the data.
-
Make a conclusion about the three different cases.
NOTE: Use Arrays and the version of Quick sort we have used.
**** If your program crashes with “stack overflow”, change the number of elements from 50,000 to 10,000 ****
Documentation:
Besides the usual, explain where and why your counter is placed.
The conclusion about the behavior of the sort based on the data characteristic.
Sorting Project
Due date: February 15th, 2017
You are to write a program that tests each of five sorting algorithms with arrays of random integer values of four different sizes. You also need a counter for this project. And just like in the previous assignment you need to decide where the counter should be so the comparisons make sense for the all the sorts. The documentation must explain where and why the counter is placed.
The five algorithms are: selection sort, insertion sort, bubble sort, quick sort 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 posted 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.
- 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 shown.
- It should create a scatter plot for each of the sorts. The plot could be either text based or as a GUI. You have the option of entering the data in a spreadsheet and use the graphing feature to create the scatter plot.
- Use mathematical regressions to find an expression for each of the sorts’ data.
NOTE: Counter, RandomIntArray classes, and public static void bubbleSort1(int[] x) resources are optional. You can make substitutions.
import java.util.Scanner;
//********************************************************************
// RecursiveSorts.java Author: Lewis/Loftus/Cocking
//
// Demonstrates the merge sort and quick sort algorithms.
//********************************************************************
public class RecursiveSorts
{
//-----------------------------------------------------------------
// Sorts the specified array of integers using merge sort.
//-----------------------------------------------------------------
public static void mergeSort (int[] numbers)
{
doMergeSort(numbers, 0, numbers.length - 1);
}
//-----------------------------------------------------------------
// Recursively sorts the the portion of the given array beginning
// at start and ending at end.
//-----------------------------------------------------------------
private static void doMergeSort (int[] numbers, int start, int end)
{
if (start < end)
{
int middle = (start + end) / 2;
doMergeSort (numbers, start, middle);
doMergeSort (numbers, middle + 1, end);
merge (numbers, start, middle, end);
}
}
//-----------------------------------------------------------------
// Merges in sorted order the two sorted subarrays
// [start, middle] and [middle + 1, end].
//-----------------------------------------------------------------
private static void merge (int[] numbers, int start, int middle,
int end)
{
// This temporary array will be used to build the merged list.
int[] tmp = new int[end - start + 1];
int index1 = start;
int index2 = middle + 1;
int indexTmp = 0;
// Loop until one of the sublists is exhausted, adding the smaller
// of the first elements of each sublist to the merged list.
while (index1 <= middle && index2 <= end)
{
if (numbers[index1] < numbers[index2])
{
tmp[indexTmp] = numbers[index1];
index1++;
}
else
{
tmp[indexTmp] = numbers[index2];
index2++;
}
indexTmp++;
}
// Add to the merged list the remaining elements of whichever sublist
// is not yet exhausted.
while (index1 <= middle)
{
tmp[indexTmp] = numbers[index1];
index1++;
indexTmp++;
}
while (index2 <= end)
{
tmp[indexTmp] = numbers[index2];
index2++;
indexTmp++;
}
// Copy the merged list from tmp into numbers.
for (indexTmp = 0; indexTmp < tmp.length; indexTmp++)
{
numbers[start + indexTmp] = tmp[indexTmp];
}
}
//-----------------------------------------------------------------
// Sorts the specified array of integers using quick sort.
//-----------------------------------------------------------------
public static void quickSort (int[] numbers)
{
doQuickSort(numbers, 0, numbers.length - 1);
}
//-----------------------------------------------------------------
// Recursively sorts the portion of the given array beginning
// at start and ending at end.
//-----------------------------------------------------------------
private static void doQuickSort (int[] numbers, int start, int end)
{
if (start < end)
{
int middle = partition(numbers, start, end);
doQuickSort(numbers, start, middle);
doQuickSort(numbers, middle + 1, end);
}
}
//-----------------------------------------------------------------
// Partitions the array such that each value in [start, middle]
// is less than or equal to each value in [middle + 1, end].
// The index middle is determined in the procedure and returned.
//-----------------------------------------------------------------
private static int partition (int[] numbers, int start, int end)
{
int pivot = numbers[start];
int i = start - 1;
int j = end + 1;
// As the loop progresses, the indices i and j move towards each other.
// Elements at i and j that are on the wrong side of the partition are
// exchanged. When i and j pass each other, the loop ends and j is
// returned as the index at which the elements are partitioned around.
while (true)
{
i = i + 1;
while (numbers[i] < pivot)
i = i + 1;
j = j - 1;
while (numbers[j] > pivot)
j = j - 1;
if (i < j)
{
int tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
for (int index = 0; index < numbers.length; index++)
System.out.print (numbers[index] + " ");
}
else return j;
}
}
}
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;
}
}
}
}
Optional Resources:
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;
}
}
Homework:
Start working on the project.