Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Java QuickSort and Selection Sort

Posted on 2011-04-28
2
Medium Priority
?
720 Views
Last Modified: 2012-05-11
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

0
Comment
Question by:Lambel
2 Comments
 
LVL 92

Accepted Solution

by:
objects earned 2000 total points
ID: 35489088
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
 

Author Closing Comment

by:Lambel
ID: 35489090
Thanks for the quick reply - I'll give this a try -keep my fingers crossed!
Lynn
0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Suggested Courses
Course of the Month20 days, 19 hours left to enroll

810 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question