Using the provided code for sorting, demonstrate each one of the sorts using an array of objects of your own custom class. Your class should have at least 3 attributes and must implement the Comparable interface and override compareTo to establish how you want to compare your custom class. Display the array of objects before and after the sort (note you need to rerun with the different sort, or "unsorted" your array to demonstrate each sort. Incorporate code for an additional sort of your choice (heap, shell) and integrate it as a generic method implementing comparable. For this assignment you may reuse sorting code from the textbook or an internet site to integrate, but you MUST cite any code that is not your own by listing the source of the code in the comments. In summary:

1) create own custom class with at least 3 attributes (also override the toString)

2) implement the Comparable interface in your class and override compareTo to establish a way to order your objects

3) demonstrate each of the sorts using your class, display the array before (unsorted) and after (sorted) each sort

4) add a method for an additional sort type. It must be generic and accept an array of objects

5) demonstrate the additional method, display the array before and after sorting. Note that you need to make sure the starting array is unsorted before each sort call and each one should be labeled to show which sort results are being displayed.

Ref

publicclass Sorting

{

/**

* Sorts the specified array using the selection

* sort algorithm.

*/

publicstatic extends Comparable>

void selectionSort(T[] data)

{

int min;

T temp;

for (int index = 0; index < data.length - 1; index++)

{

min = index;

for (int scan = index + 1; scan < data.length; scan++)

if (data[scan].compareTo(data[min]) < 0)

min = scan;

swap(data, min, index);

}

}

/**

* Swaps to elements in an array. Used by various sorting algorithms.

*

* data the array in which the elements are swapped

* index1 the index of the first element to be swapped.

* index2 the index of the second element to be swapped

*/

privatestatic extends Comparable>

void swap(T[] data,int index1,int index2)

{

T temp = data[index1];

data[index1] = data[index2];

data[index2] = temp;

}

/**

* Sorts the specified array of objects using an insertion

* sort algorithm.

*/

publicstatic extends Comparable>

void insertionSort(T[] data)

{

for (int index = 1; index < data.length; index++)

{

T key = data[index];

int position = index;

// shift larger values to the right

while (position > 0 && data[position-1].compareTo(key) > 0)

{

data[position] = data[position - 1];

position--;

}

data[position] = key;

}

}

/**

* Sorts the specified array of objects using a bubble sort

* algorithm.

*/

publicstatic extends Comparable>

void bubbleSort(T[] data)

{

int position, scan;

for (position = data.length - 1; position >= 0; position--)

{

for (scan = 0; scan <= position - 1; scan++)

{

if (data[scan].compareTo(data[scan + 1]) > 0)

swap(data, scan, scan + 1);

}

}

}

/**

* Sorts the specified array of objects using the quick sort algorithm.

*/

publicstatic extends Comparable>

void quickSort(T[] data)

{

quickSort(data, 0, data.length - 1);

}

/**

* Recursively sorts a range of objects in the specified array using the

* quick sort algorithm.

* min the minimum index in the range to be sorted

* max the maximum index in the range to be sorted

*/

privatestatic extends Comparable>

void quickSort(T[] data,int min,int max)

{

if (min < max)

{

// create partitions

int indexofpartition = partition(data, min, max);

// sort the left partition (lower values)

quickSort(data, min, indexofpartition - 1);

// sort the right partition (higher values)

quickSort(data, indexofpartition + 1, max);

}

}

/**

* Used by the quick sort algorithm to find the partition.

* min the minimum index in the range to be sorted

* max the maximum index in the range to be sorted

*/

privatestatic extends Comparable>

int partition(T[] data,int min,int max)

{

T partitionelement;

int left, right;

int middle = (min + max) / 2;

// use the middle data value as the partition element

partitionelement = data[middle];

// move it out of the way for now

swap(data, middle, min);

left = min;

right = max;

while (left < right)

{

// search for an element that is > the partition element

while (left < right && data[left].compareTo(partitionelement) <= 0)

left++;

// search for an element that is < the partition element

while (data[right].compareTo(partitionelement) > 0)

right--;

// swap the elements

if (left < right)

swap(data, left, right);

}

// move the partition element into place

swap(data, min, right);

return right;

}

/**

* Sorts the specified array of objects using the merge sort

* algorithm.

*/

publicstatic extends Comparable>

void mergeSort(T[] data)

{

mergeSort(data, 0, data.length - 1);

}

/**

* Recursively sorts a range of objects in the specified array using the

* merge sort algorithm.

* min the index of the first element

* max the index of the last element

*/

privatestatic extends Comparable>

void mergeSort(T[] data,int min,int max)

{

if (min < max)

{

int mid = (min + max) / 2;

mergeSort(data, min, mid);

mergeSort(data, mid + 1, max);

merge(data, min, mid, max);

}

}

/**

* Merges two sorted subarrays of the specified array.

* first the beginning index of the first subarray

* mid the ending index fo the first subarray

* last the ending index of the second subarray

*/

@SuppressWarnings("unchecked")

privatestatic extends Comparable>

void merge(T[] data,int first,int mid,int last)

{

T[] temp = (T[])(new Comparable[data.length]);

int first1 = first, last1 = mid; // endpoints of first subarray

int first2 = mid + 1, last2 = last; // endpoints of second subarray

int index = first1; // next index open in temp array

// Copy smaller item from each subarray into temp until one

// of the subarrays is exhausted

while (first1 <= last1 && first2 <= last2)

{

if (data[first1].compareTo(data[first2]) < 0)

{

temp[index] = data[first1];

first1++;

}

else

{

temp[index] = data[first2];

first2++;

}

index++;

}

// Copy remaining elements from first subarray, if any

while (first1 <= last1)

{

temp[index] = data[first1];

first1++;

index++;

}

// Copy remaining elements from second subarray, if any

while (first2 <= last2)

{

temp[index] = data[first2];

first2++;

index++;

}

// Copy merged data into original array

for (index = first; index <= last; index++)

data[index] = temp[index];

}

}