Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

Thread: Selection sort code needs reverse

  1. #1
    Junior Member
    Join Date
    Jun 2011
    Posts
    29
    Thanks
    11
    Thanked 0 Times in 0 Posts

    Default Selection sort code needs reverse

    Hi, I've been working on this part of the code for at least 10 hours.


    private static void  selectionSort( int[]  arr )
    	{				
    		for (int stopInd = arr.length - 1; stopInd >= 0; stopInd--) {
    			int positionOfMax = indOfMax(arr,stopInd);
    			for (int i = 0; i <= stopInd; i++) {
    				if (arr[i] < arr[positionOfMax])
    					positionOfMax = i;
     
    			}
    			int temp = arr[stopInd];  // swap stopInd item with biggest item
    			arr[stopInd] = arr[positionOfMax ];
    			arr[positionOfMax] = temp;
    		}
    	}

    It finally works but there's a slight problem: The selection sort sorts from larges => smallest.

    I.e.
    RANDOM:
    127 16 175 114 64 5 169 80 53 122 126 82 103 197 195 150 177 161 154 164
    SELECTIONSORTED:
    197 195 177 175 169 164 161 154 150 127 126 122 114 103 82 80 64 53 16 5
    But i want it to be 5, 16, 56, 64 etc.

    I've switched THE if (arr[i] < arr[positionOfMax]) "<" TO ">" but it doesn't work. instead i would get:
    RANDOM:
    34 119 56 40 83 11 190 168 138 154 63 163 33 141 39 71 99 21 172 18
    SELECTIONSORTED:
    190 34 119 56 40 83 11 18 168 138 154 63 163 33 141 39 71 99 21 172
    And the program we're writing using cmd line args and I can't find a way to use debugging mode(looking at each step of line of code) on eclipse with cmd line args becaues it just executes at once.

    Full code
    /*
      Program2.java
     
     
     
    */
     
     
    import java.io.*;
    import java.util.*;
     
     
    public class Program2
    {
    	private static final int NOT_FOUND = -1;
     
        public static void main( String[] args )
        {
     
    try // ILL EXPLAIN THIS IN CLASS SOON. JUST LEAVE IT IN HERE SO YOUR PROGRAM CRASH CANT CRASH THE GRADING SCRIPT
    	{
     
     
            Random rand = new Random();
    		int[] arr;
     
            if (args.length < 1 )
            {
                System.out.println("\n\n      !! You must enter a desired arr length on the cmd line !!\n");
                System.exit(0);
            }
     
            int dimension = Integer.parseInt(args[0]);
     
    		if ( dimension < 100 && dimension > 10)
    		{// YOU MUST VALIDATE THAT 10 < DIMENSION < 100.  JUST EXIT IF INVALID
     
    		arr = new int[dimension];
     
    		randomizearr( arr ); // fill with random ints between 1 .. dimension*10 inclusive
    		printarr( "\nRANDOM:", arr );
    		bubbleSort( arr );
    		printarr( "BUBBLESORTED:", arr );
     
    		randomizearr( arr );  // fill with random ints between 1 .. dimension inclusive
    		printarr( "RANDOM:", arr );
    		selectionSort( arr );
    		printarr( "SELECTIONSORTED:", arr );
     
     
    		}
    		else {
    			System.out.println("Invalid. Program now exits.");
    		}
     
    	} // LEAVE THIS HERE - DO NOT MODIFY
    	catch (Exception e ) // catch-all  Exception is the most general Exception type
    	{
    		System.out.println("EXCEPTION DETECTED\n" + e );  // THIS WILL SHOW UP IN YOUR OUTPUT AND I CAN DETECT IT
    		System.exit(0);
    	}
     
    	} // END MAIN
     
    	// ########################################################################################
    // - - - - - - - - -  Y O U  A R E    G I V E N    T H E S E   M E T H O D S.  D O  N O T   M O D I F Y   - - - - - - - - - - -
     
        // USE THIS METHOD AS GIVEN: DO NOT CHANGE
     
        private static void printarr( String label, int[] arr )
        {
            System.out.println(label);
            for( int i=0 ; i<arr.length ;++i )
                System.out.printf("%-3d ",arr[i] );
            System.out.println();
        }
     
     
     
        // USE THIS METHOD AS GIVEN: DO NOT CHANGE
     
    	private static void randomizearr( int[] arr )
    	{
    		Random r = new  Random();
    		int i=0;
    		while ( i < arr.length  )
    		{
    			int n = r.nextInt(arr.length*10) + 1;  // 1 .. dimension*10 inclusive
     
    			// INSERT ONLY IF NUMBER NOT ALREADY IN arr
     
    			if (  linearSearch( arr, n ) == -1  ) arr[i++] = n;
    		}
    	}
     
     
     	// USE THIS METHOD AS GIVEN: DO NOT CHANGE
     
    	private static int linearSearch( int[] arr, int target )
    	{
    		for ( int i=0 ; i < arr.length ; ++ i )
    			if (arr[i] == target ) return i;
     
    		return NOT_FOUND; // i.e. return -1 which is never a valid index - means NOT_FOUND
    	}
     
     
     
     
     
     
     
     
     
     
    // - - - - - - - - -  Y O U   W R I T E   T H E S E   M E T H O D S   B E L O W - - - - - - - - - - -
     
     
    	// YOU  WRITE THIS METHOD
    	// BUBBLESORT:
    	private static void bubbleSort( int[] arr )
    	{
    	      boolean swapped = true;
    	      int j = 0;
    	      int temp;
    	      while (swapped) {
    	            swapped = false;
    	            j++;
    	            for (int i = arr.length-2; i >= 0 ; i--) {                                       
    	                  if (arr[i] > arr[i + 1]) {                          
    	                        temp = arr[i];
    	                        arr[i] = arr[i + 1];
    	                        arr[i + 1] = temp;
    	                        swapped = true;
    	                  }
    	            }                
    	      }
     
    		// YOUR CODE HERE
     
    		//	for i= index of the next_to_last element  DOWNTO 0
    		//			for j = 0 upto i
    		//					if arr[j] and arr[j+1] are out of order then swap 'em
     
    	}
     
     
    	// YOU  WRITE THIS METHOD
    	// SELECTIONSORT
    	private static void  selectionSort( int[]  arr )
    	{				
    		for (int stopInd = arr.length - 1; stopInd >= 0; stopInd--) {
    			int positionOfMax = indOfMax(arr,stopInd);
    			for (int i = 0; i <= stopInd; i++) {
    				if (arr[i] < arr[positionOfMax])
    					positionOfMax = i;
     
    			}
    			int temp = arr[stopInd];  // swap stopInd item with biggest item
    			arr[stopInd] = arr[positionOfMax ];
    			arr[positionOfMax] = temp;
    		}
    	}
     
    	// YOU  WRITE THIS METHOD
    	// INDOFMAX
    	// WITH EACH CALL FROm SELECTION SORT YOU WILL BE PASSING  IN THE RIGHT SIDE SstopIndPING POINT
    	//	OF HOW FAR INTO THE arr TO SCAN
    	// ONLY SCAN THAT SUB-RANGE AND RETURN THE INDEX OF THE LARGEST ELEMENT IN THE SUB-RANGE
    	private static int indOfMax( int[] arr,  int stopIndInd )
    	{
    		// YOUR CODE HERE
    		// for i = 0 upto index of last element
    		//		keep track of the largest number you have seen so far and save the index postion of each new winner
    		//
    		// return the index position of the largest numnber seen
    		int max = arr[0];
    		for(int i = 1; i < arr.length; i++){
    			if(arr[i] > max) {
    				max = arr[i];
    				stopIndInd = i;
    			}
    		}
     
    return stopIndInd;  // JUST TO MAKE IT COMPILE - YOU CHANGE AS NEEDED
    	}
     
     
    } // END Of CLASS PROGRAM2

    Help will be appreciated
    Last edited by steel55677; September 24th, 2011 at 01:32 PM.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Selection sort code needs reverse

    Where in your logic do you chose the biggest item?
    Can you change that logic to chose the smallest?

  3. #3
    Junior Member
    Join Date
    Jun 2011
    Posts
    29
    Thanks
    11
    Thanked 0 Times in 0 Posts

    Default Re: Selection sort code needs reverse

    Here: int positionOfMax = indOfMax(arr,stopInd);

    We're to write a method that finds the biggest item's index in the indofMax method.

    then we're to use the indofMax method to make the range smaller each time. I'm still confused on that part. I've tried to make it the smallest and it works but my professor will not accept it, he sent me a explaining we're suppose to use the max value's index.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Selection sort code needs reverse

    I guess the idea would be to move the max value's index to the bottom of the list.

  5. #5
    Junior Member
    Join Date
    Jun 2011
    Posts
    29
    Thanks
    11
    Thanked 0 Times in 0 Posts

    Default Re: Selection sort code needs reverse

    Yes sir,

    I've looked at his pseudo code
    // YOUR CODE HERE -
    // YOU MUST USE THE indOfMax() METHOD IN THIS METHOD

    // for stopInd = index of last element DOWNTO 0
    // swap the i'th element with element at indOfMax(arr,stopInd) (puts largest remaining element in its proper place)
    and this what I came up with.
    for (int stopInd = arr.length - 1; stopInd >= 0; stopInd--) { // for stopInd = index of last element  DOWNTO   0
    			int positionOfMax = indOfMax(arr,stopInd);
    			for (int i = 0; i <= stopInd; i++) {
    				if (arr[i] < arr[positionOfMax])
    					positionOfMax = i; ///swap the i'th element with element at indOfMax(arr,stopInd)   (puts  largest remaining element in its proper pla
     
    			}
    			int temp = arr[stopInd];  // swap stopInd item with biggest item

    Arrrggh, frustration

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Selection sort code needs reverse

    Have you worked through the logic on paper so you know how it is supposed to work?

  7. #7
    Junior Member
    Join Date
    Sep 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Selection sort code needs reverse

    package ravi;

    import java.util.Arrays;
    import java.util.Collections;


    public class SortArrayWithOrder {

    public static void main(String[] args) {

    Integer[] points = new Integer[5];

    points[0] = 94;

    points[1] = 53;

    points[2] = 70;

    points[3] = 44;

    points[4] = 64;





    // Sort the points array, the default order is in ascending order.

    // [44, 53, 64, 70, 94]



    Arrays.sort(points);

    System.out.println(Arrays.toString(points));





    // Sort the points array in descending order.

    // [94, 70, 64, 53, 44]



    Arrays.sort(points, Collections.reverseOrder());

    System.out.println(Arrays.toString(points));

    }
    }

  8. #8
    Think of me.... Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Pakistan
    Posts
    1,136
    My Mood
    Grumpy
    Thanks
    20
    Thanked 82 Times in 78 Posts
    Blog Entries
    1

    Default Re: Selection sort code needs reverse

    Well, first thing, you need not to change only replace '<' with '>' at a single place but one or more than one places too. Like everyone else has said you to find out the place in your code where you are finding the largest number, now find the smallest and replace it.

    Anyways, the simplest solution is to print array in opposite direction.

Similar Threads

  1. Reverse the Pattern of this output
    By rbradan in forum Member Introductions
    Replies: 2
    Last Post: July 11th, 2011, 05:01 PM
  2. Reverse String
    By WantHelp in forum What's Wrong With My Code?
    Replies: 7
    Last Post: July 5th, 2011, 06:14 AM
  3. bubble sort and selection sort on strings
    By Sir Saula in forum What's Wrong With My Code?
    Replies: 5
    Last Post: July 3rd, 2010, 09:44 AM
  4. Pseudo code of insertion sort linked list
    By sungirl in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 23rd, 2010, 09:25 AM
  5. Reverse Number
    By java1 in forum Java Theory & Questions
    Replies: 2
    Last Post: October 28th, 2009, 10:19 AM