Lambel
asked on
Java QuickSort and Selection Sort
I am (still) trying to get a section sort and a quicksort working. I found some samples online at
http://www.roseindia.net/java/beginners/arrayexamples/SelectionSort.shtml
They worked originally, but when I added the features I need, the quicksort hang up every time.
I'd appreciate any suggestions.
Lynn
http://www.roseindia.net/java/beginners/arrayexamples/SelectionSort.shtml
They worked originally, but when I added the features I need, the quicksort hang up every time.
I'd appreciate any suggestions.
Lynn
public class Sort{
/**
* Method: public Sort(int array[], int n)
*
* Parameters:
* array[] - the capacity of the array
* n - the minimum value in the population
* Returns:
* an instance of sort which is an array of sorted items
*
* Postcondition:
* an instance of a sorted array
*/
// code from Rose India Technologies
// http://www.roseindia.net/java/beginners/arrayexamples/SelectionSort.shtml
public static void selectionSort(int array[], int n){
for(int x=0; x<n; x++){
int index_of_min = x;
for(int y=x; y<n; y++){
if(array[index_of_min]<array[y]){
index_of_min = y;
}
}
int temp = array[x];
array[x] = array[index_of_min];
array[index_of_min] = temp;
}
}
/**
* Constructor Method: quickSort(int array[],int low, int n)
*
* Parameters:
* array[] - the capacity of the array
* low - the minimum value in the population
* n - length of array
* Returns:
* an instance of sort which is an array of sorted items
*
* Postcondition:
* an instance of a sorted array
*/
// code credited to C. A. R. Hoare from Rose India Technologies website
// http://www.roseindia.net/java/beginners/arrayexamples/SelectionSort.shtml
public static void quickSort(int arrayIn[],int low, int n){
int lo = low;
int hi = n;
if (lo >= n) {
return;
}
int mid = arrayIn[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && arrayIn[lo] < mid) {
lo++;
}
while (lo<hi && arrayIn[hi] > mid) {
hi--;
}
if (lo < hi) {
int T = arrayIn[lo];
arrayIn[lo] = arrayIn[hi];
arrayIn[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
quickSort(arrayIn, low, lo);
quickSort(arrayIn, lo == low ? lo+1 : lo, n);
}
}
import java.util.*;
import java.util.Date;
public class SortTester {
// code from Rose India Technologies website
// http://www.roseindia.net/java/beginners/arrayexamples/SelectionSort.shtml
public static void main(String a[]) {
int i = 0;
// Variable to hold various times below
long timeQS;
long timeSS;
// Add 2 Integer objects of random numbers
int numItems = 20;
int[] array = new int[numItems];
int[] array1 = new int[numItems];
// load arrays with elements
for(int j = 0;j< array.length; j++){
array[j] = (int)(Math.random() * 9);
}
for(int k = 0; k < 20; k++){
array1[k] = (int)(Math.random() * 9);
}
///////// selectionSort testing
System.out.println(" Selection Sort\n\n");
System.out.println("Values Before the sort:\n");
for (i = 0; i < array.length; i++)
System.out.print(array[i] + " ");
System.out.println();
/// Start Timer for selectionSort
timeSS = new Date().getTime();
Sort.selectionSort(array, array.length);
/// Stop Timer and print elapsed time
timeSS = new Date().getTime() - timeSS;
System.out.println("Time for selectionSort:");
printDateTime(timeSS);
System.out.print("Values after the sort:\n");
for (i = 0; i < array.length; i++){
System.out.print(array[i] + " ");
}
System.out.println();
System.out.println("PAUSE");
////////// quickSort testing
System.out.println(" Quick Sort\n\n");
System.out.println("Values Before the sort:\n");
for (i = 0; i< array1.length; i++){
System.out.print(array1[i] + " ");
}
System.out.println();
/// Start Timer for selectionSort
timeQS = new Date().getTime();
Sort.quickSort(array1, 0, array1.length - 1);
System.out.print("Values after the sort:\n");
for (i = 0; i < array1.length; i++){
System.out.print(array1[i] + " ");
}
System.out.println();
//// Stop Timer and print elapsed time
timeQS = new Date().getTime()-timeQS;
System.out.println("Time for selectionSort:");
printDateTime(timeQS);
}
/**
* Method to print elapsed time for method execution
*
* @param args
* Optional argument from the command line
*/
private static void printDateTime(long a_date_time)
{
int mills = (int)(a_date_time % 1000);
int secs = (int)((a_date_time/1000) % 60);
int mins = (int)((a_date_time/60000) % 60);
int hours = (int)((a_date_time/1440000) % 24);
System.out.printf("%d hours %d mins %d secs %d mills", hours, mins, secs, mills);
System.out.println();
System.out.println();
}
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Lynn