Results 1 to 9 of 9
  1. #1
    flubbernugget is offline Member
    Join Date
    Jul 2011
    Posts
    6
    Rep Power
    0

    Default Selection Sort Algorithm Not Working

    Given the following code, when I pass the array to the method selectionSort(), the array's contents are not sorted, but changed to {3, 3, 6, 6, 6, 6, 6, 6}. What is wrong with the code?
    Java Code:
    public class SortingAndSearching{
    	public static void main(String args[]){//Test methods
    		int[] list = {3,6,8,4,2,6,1};
    		int key = 4;
    		System.out.println(bruteForceSearch(list, key));
    		System.out.println(binarySearch(list,key));
    
    		System.exit(0);
    	} 			
    
    	//Search Methods
    	/**Good for small unsorted lists*/
    	public static int bruteForceSearch(int[] list, int key){//Slow, but easy to use.
    															//Also called linear search
    		for (int i = 0; i < list.length - 1; i++){
    			if (list[i] == key)
    				return i;
    		}
    		return -1;//If key isn't found
    	}
    	public static int binarySearch(int[] list, int key){
    		selectionSort(list);
    		int low = 0, high = list.length - 1, mid;
    		while(high >= low){
    			mid = (high + low) / 2;
    			
    			if(list[mid] == key)
    				return mid;
    			else if (key > list[mid])
    				high = mid + 1;
    			else 
    				low = mid + 1;
    		}
    		return -1;
    	}
    	public static void selectionSort(double[] list){
    		double currentMax = list[0];
    		int currentMaxIndex = 0;
    		
    		for (int i = list.length - 1; i >= 1; i--){
    			//find maximum in list
    			
    			for(int j = 1; j <= 1; j++){
    				if (currentMax < list[j]){
    					currentMax = list[j];
    					currentMaxIndex = j;
    				}
    			}
    			if(currentMaxIndex != i){
    				list[currentMaxIndex] = list[1];
    				list[i] = currentMax;
    			}
    		}
    	}
    	public static void selectionSort(int[] list){
    		int currentMax = list[0];
    		int currentMaxIndex = 0;
    		
    		for (int i = list.length - 1; i >= 1; i--){
    			//find maximum in list
    			
    			for(int j = 1; j <= 1; j++){
    				if (currentMax < list[j]){
    					currentMax = list[j];
    					currentMaxIndex = j;
    				}
    			}
    			if(currentMaxIndex != i){
    				list[currentMaxIndex] = list[1];
    				list[i] = currentMax;
    			}
    		}
    		for(int element: list){
    			System.out.println(element);
    		}	
    	}
    	
    }

  2. #2
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,558
    Rep Power
    25

    Default

    Obviously you have a logic problem. You appear to be copying a variable over the top of other variables.
    Time to do some debugging. Add some printlns to the code to show the values of variables as they change and are used to make decisions.

  3. #3
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,558
    Rep Power
    25

    Default

    I'll give you a couple of samples:
    Java Code:
    		System.out.println("bFS=" + bruteForceSearch(list, key));
    
    		System.out.println("bS=" + binarySearch(list, key));
    By putting "ids" on the printouts, it will show you who did what. Your post doesn't show what the program printed.
    Where did you get this value: {3, 3, 6, 6, 6, 6, 6, 6}.

  4. #4
    flubbernugget is offline Member
    Join Date
    Jul 2011
    Posts
    6
    Rep Power
    0

    Default

    for(int element: list){
    System.out.println(element);
    }

    Close to the end of the program.

  5. #5
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,558
    Rep Power
    25

    Default

    I don't think so. That println puts the values on separate lines without the { and }

    Did you change your printlns to use the ones I posted? They replace the printlns in the main method.
    What does your program output look like with those two changes?

  6. #6
    flubbernugget is offline Member
    Join Date
    Jul 2011
    Posts
    6
    Rep Power
    0

    Default

    Quote Originally Posted by Norm View Post
    I don't think so. That println puts the values on separate lines without the { and }
    Those are the values that were printed, they are not in the format that the program printed them as. Those are the values in the array at the end of the function. The brute force function returns 3, which is the correct address in the array. The binary search is returning -1, because selectionSort() is not sorting values like intended to. What do you mean when you say I am copying a variable on top of another variable?

  7. #7
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,558
    Rep Power
    25

    Default

    Those are the values that were printed, they are not in the format that the program printed them as
    It is VERY IMPORTANT that you show EXACTLY what a program outputs. If you edit it or change it in some way (and not tell us that you have done it) then when we look at the code there is no way we will see the code that produced the output you show.
    We're not mind readers. All we have is what you post and the code. Some times students post output from other programs.
    It can make for a waste of time trying to resolve the differences.

    What do you mean when you say I am copying a variable on top of another variable?
    The starting array: {3, 6, 8, 4, 2, 6, 1}
    The ending array: {3, 6, 6, 6, 6, 6, 6}.

    It looks like 6 was copied over the 2nd to the last element in the array.
    Last edited by Norm; 07-19-2011 at 10:08 PM.

  8. #8
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default

    Java Code:
    for(int j = 1; j <= 1; j++){
    Take a close look at your inner loop.

  9. #9
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,558
    Rep Power
    25

    Default

    This code is full of problems. The first step I'd recommend is get a design for the sort. Write out the steps that the program must take and then add comments to the code as he writes the code to do those steps.
    Simple comments in the code will help him write the code he wants.
    I just worked thru the code and added these comments as I went along:
    // Sort in ascending order
    // save index of current item
    // Start at next item past current item
    // Check if next element is smaller
    // Save index of smaller
    // Swap smallest(@ tempIdx) with element at i
    // save current
    // set current(@i) to smallest
    // finish swap

Similar Threads

  1. Selection Sort. please help!
    By cassato in forum New To Java
    Replies: 4
    Last Post: 03-14-2011, 10:26 PM
  2. Is this a Selection Sort?
    By Metastar in forum New To Java
    Replies: 2
    Last Post: 10-22-2010, 05:00 AM
  3. Problem with selection sort
    By Metastar in forum New To Java
    Replies: 6
    Last Post: 10-21-2010, 02:18 AM
  4. selection sort
    By mayhewj7 in forum New To Java
    Replies: 1
    Last Post: 04-29-2009, 12:40 AM
  5. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 08:04 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •