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
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);
		  }
		}

Open in new window

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();
		}	
		
	}

Open in new window

LambelAsked:
Who is Participating?
 
objectsCommented:
that quick sort implementation is wrong, try this


public static void quickSort(int[] numbers, int low, int high) {
		int i = low, j = high;
		// Get the pivot element from the middle of the list
		int pivot = numbers[low + (high-low)/2];

		// Divide into two lists
		while (i <= j) {
			// If the current value from the left list is smaller then the pivot
			// element then get the next element from the left list
			while (numbers[i] < pivot) {
				i++;
			}
			// If the current value from the right list is larger then the pivot
			// element then get the next element from the right list
			while (numbers[j] > pivot) {
				j--;
			}

			// If we have found a values in the left list which is larger then
			// the pivot element and if we have found a value in the right list
			// which is smaller then the pivot element then we exchange the
			// values.
			// As we are done we can increase i and j
			if (i <= j) {
		        int T = numbers[i];
		        numbers[i] = numbers[j];
		        numbers[j] = T;
				i++;
				j--;
			}
		}
		// Recursion
		if (low < j)
			quickSort(numbers, low, j);
		if (i < high)
			quickSort(numbers, i, high);
	}

Open in new window

0
 
LambelAuthor Commented:
Thanks for the quick reply - I'll give this a try -keep my fingers crossed!
Lynn
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.