Objective: Comparison of Sorting Algorithms Write a main java program to read in
ID: 3580805 • Letter: O
Question
Objective: Comparison of Sorting Algorithms
Write a main java program to read input file into separate array for Selection Sort, Insertion Sort, Merge Sort and Quick Sort. Compare efficiency for each sort Algorism by display the System.nanoTime() for each sort.
Given Code:
//********************************************************************
// SelectionSortS.java
//
//********************************************************************
import java.util.Comparator;
public class SelectionSortS
{
private SortNode list;
//-----------------------------------------------------------------
// Creates an initially empty linked list.
//-----------------------------------------------------------------
public SelectionSortS()
{
list = null;
}
//-----------------------------------------------------------------
// Adds an integer to the linked list
//-----------------------------------------------------------------
public void add(String value)
{
SortNode node = new SortNode(value);
SortNode current = null;
if (list == null)
list = node;
else
{
current = list;
while (current.next != null)
current = current.next;
current.next = node;
}
}
//-----------------------------------------------------------------
// Sorts the linked list using the selection sort.
//-----------------------------------------------------------------
public void sort()
{
SortNode current = list;
SortNode min = list;
SortNode swapPos = list;
if (list == null)
return;
while (swapPos.next != null)
{
while (current.next != null) // find min value
{
current = current.next;
if (current.value.compareTo(min.value) <0)
min = current;
}
// Swap the values
if (min != swapPos) // a swap was found
{
String temp = min.value;
min.value = swapPos.value;
swapPos.value = temp;
}
swapPos = swapPos.next;
current = swapPos;
min = current;
}
}
//-----------------------------------------------------------------
// Returns a listing of the contents of the linked list.
//-----------------------------------------------------------------
public String toString()
{
String report = "";
SortNode current = list;
if (current != null)
{
report += String.valueOf(current.value) + " ";
while (current.next != null)
{
current = current.next;
report += String.valueOf(current.value) + " ";
}
}
return report;
}
//*****************************************************************
// An inner class that represents a node containing String.
// The public variables are only visible in the outer class.
//*****************************************************************
private class SortNode
{
public String value;
public SortNode next;
//--------------------------------------------------------------
// Sets up the node.
//--------------------------------------------------------------
public SortNode (String current)
{
value = current;
next = null;
}
}
}
/** Source code example for "A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
// Sorting main function for testing correctness of sort algorithm.
// To use: <sortname> [+/-] <size_of_array> <threshold>
// + means increasing values, - means decreasing value and no
// parameter means random values;
// where <size_of_array> controls the number of objects to be sorted;
// and <threshold> controls the threshold parameter for certain sorts, e.g.,
// cutoff point for quicksort sublists.
import java.io.*;
public class QuickSort {
static int THRESHOLD = 0;
static int ARRAYSIZE = 0;
static <E extends Comparable<? super E>> void Sort(E[] A) {
qsort(A, 0, A.length-1);
}
static int MAXSTACKSIZE = 1000;
static <E extends Comparable<? super E>>
void qsort(E[] A, int i, int j) { // Quicksort
int pivotindex = findpivot(A, i, j); // Pick a pivot
DSutil.swap(A, pivotindex, j); // Stick pivot at end
// k will be the first position in the right subarray
int k = partition(A, i-1, j, A[j]);
DSutil.swap(A, k, j); // Put pivot in place
if ((k-i) > 1) qsort(A, i, k-1); // Sort left partition
if ((j-k) > 1) qsort(A, k+1, j); // Sort right partition
}
static <E extends Comparable<? super E>>
int partition(E[] A, int l, int r, E pivot) {
do { // Move bounds inward until they meet
while (A[++l].compareTo(pivot)<0);
while ((r!=0) && (A[--r].compareTo(pivot)>0));
DSutil.swap(A, l, r); // Swap out-of-place values
} while (l < r); // Stop when they cross
DSutil.swap(A, l, r); // Reverse last, wasted swap
return l; // Return first position in right partition
}
static <E extends Comparable<? super E>>
int findpivot(E[] A, int i, int j)
{ return (i+j)/2; }
}
/** Source code example for "A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
// Sorting main function for testing correctness of sort algorithm.
// To use: <sortname> [+/-] <size_of_array> <threshold>
// + means increasing values, - means decreasing value and no
// parameter means random values;
// where <size_of_array> controls the number of objects to be sorted;
// and <threshold> controls the threshold parameter for certain sorts, e.g.,
// cutoff point for quicksort sublists.
import java.io.*;
public class MergeSort {
static int THRESHOLD = 0;
static int ARRAYSIZE = 0;
@SuppressWarnings("unchecked") // Generic array allocation
static <E extends Comparable<? super E>> void Sort(E[] A) {
E[] temp = (E[])new Comparable[A.length];
mergesort(A, temp, 0, A.length-1);
}
static <E extends Comparable<? super E>>
void mergesort(E[] A, E[] temp, int l, int r) {
int mid = (l+r)/2; // Select midpoint
if (l == r) return; // List has one element
mergesort(A, temp, l, mid); // Mergesort first half
mergesort(A, temp, mid+1, r); // Mergesort second half
for (int i=l; i<=r; i++) // Copy subarray to temp
temp[i] = A[i];
// Do the merge operation back to A
int i1 = l; int i2 = mid + 1;
for (int curr=l; curr<=r; curr++) {
if (i1 == mid+1) // Left sublist exhausted
A[curr] = temp[i2++];
else if (i2 > r) // Right sublist exhausted
A[curr] = temp[i1++];
else if (temp[i1].compareTo(temp[i2])<0) // Get smaller
A[curr] = temp[i1++];
else A[curr] = temp[i2++];
}
}
}
/** Source code example for "A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
// Sorting main function for testing correctness of sort algorithm.
// To use: <sortname> [+/-] <size_of_array> <threshold>
// + means increasing values, - means decreasing value and no
// parameter means random values;
// where <size_of_array> controls the number of objects to be sorted;
// and <threshold> controls the threshold parameter for certain sorts, e.g.,
// cutoff point for quicksort sublists.
import java.io.*;
public class InsertionSort {
static int THRESHOLD = 0;
static int ARRAYSIZE = 0;
static <E extends Comparable<? super E>>
void Sort(E[] A, int l) {
for (int i=1; i<l; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j].compareTo(A[j-1])<0); j--)
DSutil.swap(A, j, j-1);
}
}
/** Source code example for "A Practical Introduction to Data
Structures and Algorithm Analysis, 3rd Edition (Java)"
by Clifford A. Shaffer
Copyright 2008-2011 by Clifford A. Shaffer
*/
import java.util.*;
import java.math.*;
/** A bunch of utility functions. */
class DSutil<E> {
/** Swap two Objects in an array
@param A The array
@param p1 Index of one Object in A
@param p2 Index of another Object A
*/
public static <E> void swap(E[] A, int p1, int p2) {
E temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
/** Randomly permute the Objects in an array.
@param A The array
*/
// int version
// Randomly permute the values of array "A"
static void permute(int[] A) {
for (int i = A.length; i > 0; i--) // for each i
swap(A, i-1, DSutil.random(i)); // swap A[i-1] with
} // a random element
public static void swap(int[] A, int p1, int p2) {
int temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
/** Randomly permute the values in array A */
static <E> void permute(E[] A) {
for (int i = A.length; i > 0; i--) // for each i
swap(A, i-1, DSutil.random(i)); // swap A[i-1] with
} // a random element
/** Initialize the random variable */
static private Random value = new Random(); // Hold the Random class object
/** Create a random number function from the standard Java Random
class. Turn it into a uniformly distributed value within the
range 0 to n-1 by taking the value mod n.
@param n The upper bound for the range.
@return A value in the range 0 to n-1.
*/
static int random(int n) {
return Math.abs(value.nextInt()) % n;
}
}
Text File (part):
HO09C1068A,HONDA,FIT,Front bumper license plate,2015,7.00
HO11F1213B,HONDA,ODYSSEY,RT Front bumper molding,2014,7.00
KI17B1042A,KIA,FORTE SDN,LT Front bumper cover retainer,2015,7.00
KI17B1043A,KIA,FORTE KOUP,RT Front bumper cover retainer,2015,7.00
SU04D1042D,SUBARU,FORESTER,LT Rear bumper cover retainer,2015,7.00
SU04D1043D,SUBARU,FORESTER,RT Rear bumper cover retainer,2015,7.00
HO11F1213A,HONDA,ODYSSEY,RT Front bumper molding,2014,8.00
HO11F2598A,HONDA,ODYSSEY,LT Front fog lamp cover,2014,9.00
HO11F2599A,HONDA,ODYSSEY,RT Front fog lamp cover,2014,9.00
HY03G2599A,HYUNDAI,ELANTRA SEDAN,RT Front fog lamp cover,2013,9.00
HY03G2598A,HYUNDAI,ELANTRA SEDAN,LT Front fog lamp cover,2013,9.00
SU04D1042C,SUBARU,FORESTER,LT Rear bumper cover retainer,2015,9.00
SU04D1043C,SUBARU,FORESTER,RT Rear bumper cover retainer,2015,9.00
VW11E2513B,VOLKSWAGEN,GOLF,RT Fog Lamp Ring Bezel,2014,9.00
DG06C1042A,DODGE,AVENGER,LT Front bumper cover support,2010,10.00
SZ10C2599A,SUZUKI,GRAND VITARA,RT Front fog lamp cover,2013,11.00
SZ10C2599B,SUZUKI,GRAND VITARA,RT Front fog lamp cover,2013,11.00
SZ10C2598B,SUZUKI,GRAND VITARA,LT Front fog lamp cover,2013,11.00
SZ10C2598A,SUZUKI,GRAND VITARA,LT Front fog lamp cover,2013,12.00
Explanation / Answer
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
long length = 2000;
const long max_length = 200000;
int list_sort[max_length];
void read()
{
ifstream finsort("random.dat", ios::binary);
for (long i = 0; i < length; i++)
{
fin.readsort((char*)&list[i], sizeof(int));
}
fin.close();
}
void bubbleSortList()
{
int temp;
for(long i = 0; i < length; i++)
{
for(long j = 0; j < length-i-1; j++)
{
if (list_sort[j] > list_sort[j+1])
{
temp = list_sort[j];
list_sort[j] = list_sort[j+1];
list_sort[j+1] = temp;
}
}
}
}
void insertionSort()
{
int temp;
for(long i = 1; i < length; i++)
{
temp = list_sort[i];
long j;
for(j = i-1; j >= 0 && list_sort[j] > temp; j--)
{
list_sort[j+1] = list_sort[j];
}
list_sort[j+1] = temp;
}
}
long partition(long left, long right)
{
int pivot_element = list_sort[left];
int lb = left, ub = right;
int temp;
while (left < right)
{
while(list_sort[left] <= pivot_element)
left++;
while(list_sort[right] > pivot_element)
right--;
if (left < right)
{
temp = list_sort[left];
list_sort[left] = list_sort[right];
list_sort[right] = temp;
}
}
list_sort[lb] = list[right];
list_sort[right] = pivot_element;
return right;
}
void quickSort(long left, long right)
{
if (left < right)
{
long pivot = partition(left, right);
quickSort(left, pivot-1);
quickSort(pivot+1, right);
}
}
int main()
{
double t1, t2;
for (length = 1000; length <= max_length; )
{
cout << " Length : " << length << ' ';
read();
t1 = clock();
bubbleSort();
t2 = clock();
cout << "Bubble Sort : " << (t2 - t1)/CLK_TCK << " sec ";
read();
t1 = clock();
insertionSort();
t2 = clock();
cout << "Insertion Sort : " << (t2 - t1)/CLK_TCK << " sec ";
read();
t1 = clock();
quickSort(0, length - 1);
t2 = clock();
cout << "Quick Sort : " << (t2 - t1)/CLK_TCK << " sec ";
switch (length)
{
case 1000 :
length = 5000;
break;
case 5000 :
length = 10000;
break;
case 10000 :
length = 50000;
break;
case 50000 :
length = 100000;
break;
case 100000 :
length = 200000;
break;
case 200000 :
length = 300000;
break;
case 300000 :
length = 300001;
break;
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.