7 Replies - 308 Views - Last Post: 03 November 2011 - 10:29 PM Rate Topic: -----

#1 AlvinF  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-January 11

Help with my own version of selection sort

Posted 03 November 2011 - 05:22 PM

Hi all, I've been trying to write my own little version of selectionsort (for fun :)). I'm just having problems right now ironing out the kinks.
Firstly, my selectionsort works by finding the biggest and smallest value in an array in putting them at their respective positions. As is, it works about half the time, the other half a random value or two will be out of place and I can't seem to pinpoint why.

   private void selectionSort(int x[])
   {
	   int big = 0;
	   int little = 0;
	   for(int i = 0; i < x.length/2; i++)
	   {
		   big = x[i];
		   little = x[i];
		   int littleIndex = i, bigIndex = i;
		   for(int j = i; j < x.length-i; j++)
		   {
			   if(x[j] < little)
			   {
				   little = x[j];
				   littleIndex = j;
			   }
			   else if(x[j] > big)
			   {
				   big = x[j];
				   bigIndex = j;
			   }
		   }
		   int temp = x[i];
		   x[i] = little;
		   x[littleIndex] = temp;
		   temp = x[x.length-1-i];
		   x[x.length-1-i] = big;
		   x[bigIndex] = temp;
	   }
   }



Also, I haven't really tried/thought about how it would play with an array with an odd number of ints. The general buzz in my head says that it should all work out just fine, but I'm not sure. Anyone know if I'll have to do something special with the middle-est value? IF that problem should arise, I plan to just take that value and use insertion sort on it.
Thanks in advance for any help in making this sort work out.

Is This A Good Question/Topic? 0
  • +

Replies To: Help with my own version of selection sort

#2 AlvinF  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-January 11

Re: Help with my own version of selection sort

Posted 03 November 2011 - 06:08 PM

Here's an interesting update. I believe the errors only occur in the first half of the array. When I initialized an array of 2000 ints in reverse order (2000,1999,1998,etc), the first 999 ints were in reversed order. I think this means that when I'm swapping the ints around, the big ones are overriding the little ones or something. I can't really wrap my head around it. Any help would be appreciated!
Was This Post Helpful? 0
  • +
  • -

#3 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1152
  • View blog
  • Posts: 2,530
  • Joined: 05-May 05

Re: Help with my own version of selection sort

Posted 03 November 2011 - 07:30 PM

You can immediately see that your sort actually loses array elements.
Was This Post Helpful? 0
  • +
  • -

#4 Sheph  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 432
  • View blog
  • Posts: 1,020
  • Joined: 12-October 11

Re: Help with my own version of selection sort

Posted 03 November 2011 - 07:45 PM

You really only need to find the minimum value in each i iteration and swap it with x[i]. And you don't need the little variable this may be causing loss in the array when you swap them.

int temp = x[i];
x[i] = x[littleIndex]; // notice that i'm only switchin array elements
x[littleIndex] = temp; // not the variable little, so no loss of elements


Was This Post Helpful? 0
  • +
  • -

#5 AlvinF  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-January 11

Re: Help with my own version of selection sort

Posted 03 November 2011 - 07:58 PM

View Postblackcompe, on 03 November 2011 - 07:30 PM, said:

You can immediately see that your sort actually loses array elements.


I've been using the sort on an array of random ints of size from 50 to 1000. Like I said, sometimes it will work perfectly and everything will be sorted correctly, sometimes a couple of ints will be out of place. I'm looking for help as to how to fix this problem that sometimes comes up.



View PostSheph, on 03 November 2011 - 07:45 PM, said:

You really only need to find the minimum value in each i iteration and swap it with x[i]. And you don't need the little variable this may be causing loss in the array when you swap them.

int temp = x[i];
x[i] = x[littleIndex]; // notice that i'm only switchin array elements
x[littleIndex] = temp; // not the variable little, so no loss of elements



I could just do it with just finding the minimum, but I think this is a little more interesting! I'm not doing it for an assignment or anything, I just wanted to see if I could make my own sort. I tried substituting x[littleIndex] for little, and the same with big, and that caused EVERYTHING to be out of place when I used the sort on a reversed array. Before only the first half of the array was not in order.
Was This Post Helpful? 0
  • +
  • -

#6 Sheph  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 432
  • View blog
  • Posts: 1,020
  • Joined: 12-October 11

Re: Help with my own version of selection sort

Posted 03 November 2011 - 08:13 PM

Well the first half of the array was in order because x[i] was equaling little and i looped through only the first half , so of course it would be right. Now you see the truth of what's going on in your program, unhidden from the proper swapping technique. Now you can find what's going on more easily.
Was This Post Helpful? 0
  • +
  • -

#7 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1152
  • View blog
  • Posts: 2,530
  • Joined: 05-May 05

Re: Help with my own version of selection sort

Posted 03 November 2011 - 08:14 PM

There's a subtle problem with your method of sorting. Suppose I want to sort this list:

8, 2, 1, 3, 6, 7, 5

I get to this part of your sort method:

 int temp = x[i];
  x[i] = little;
  x[littleIndex] = temp;
  temp = x[x.length-1-i];
  x[x.length-1-i] = big;
  x[bigIndex] = temp;



littleIndex points to 1, bigIndex points 8. You swap the first element in the array with the element at littleIndex and you get

1, 2, 8, 3, 6, 7, 5

Then you swap the last element of the array, 5, with the element at bigIndex which now equals 1 (instead of 8) and you get

5, 2, 8, 3, 6, 7, 1

And, obviously that's not right. So, you have to handle the case where the first swap is going to corrupt the second swap.

Working code:

import java.util.Random;

public class Main {

	//run 50 sort tests on random input
	public static void main( String[] args ) {
		for(int i = 0; i < 50; i++) {
			int ar[] = randomArray( 10000 );
			selectionSort( ar );
			System.out.println( "Is sorted =  " + isSorted( ar ) );
		}
	}

	static boolean isSorted( int ar[] ) {
		for ( int i = 0; i < ar.length - 1; i++ ) {
			if ( ar[ i ] > ar[ i + 1 ] )
				return false;
		}
		return true;
	}

	static int[] randomArray( int size ) {
		int a[] = new int[ size ];
		Random rand = new Random();
		for ( int i = 0; i < size; i++ )
			a[ i ] = rand.nextInt( 100000 );
		return a;
	}

	static private void selectionSort( int ar[] ) {
		for ( int i = 0; i < ar.length / 2; i++ ) {
			int minIndex = i, maxIndex = i;
			for ( int j = i; j < ar.length - i; j++ ) {
				if ( ar[ j ] < ar[ minIndex ] )
					minIndex = j;
				else if ( ar[ j ] > ar[ maxIndex ] )
					maxIndex = j;
			}
			//tricky: your going to first swap(i, minIndex), if maxIndex == i, then swap(ar.length-1-i, maxIndex) will
			//turn into swap(ar.length-1-i, minIndex), so you have to handle that possibility
			swap( ar, i, minIndex );
			if ( i == maxIndex )
				maxIndex = minIndex;
			swap( ar, ar.length - 1 - i, maxIndex );
		}
	}

	static private void swap( int ar[], int i, int j ) {
		int temp = ar[ i ];
		ar[ i ] = ar[ j ];
		ar[ j ] = temp;
	}
}


This post has been edited by blackcompe: 03 November 2011 - 08:18 PM

Was This Post Helpful? 1
  • +
  • -

#8 AlvinF  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 28-January 11

Re: Help with my own version of selection sort

Posted 03 November 2011 - 10:29 PM

View Postblackcompe, on 03 November 2011 - 08:14 PM, said:

There's a subtle problem with your method of sorting. Suppose I want to sort this list:

8, 2, 1, 3, 6, 7, 5

I get to this part of your sort method:

 int temp = x[i];
  x[i] = little;
  x[littleIndex] = temp;
  temp = x[x.length-1-i];
  x[x.length-1-i] = big;
  x[bigIndex] = temp;



littleIndex points to 1, bigIndex points 8. You swap the first element in the array with the element at littleIndex and you get

1, 2, 8, 3, 6, 7, 5

Then you swap the last element of the array, 5, with the element at bigIndex which now equals 1 (instead of 8) and you get

5, 2, 8, 3, 6, 7, 1

And, obviously that's not right. So, you have to handle the case where the first swap is going to corrupt the second swap.

Working code:

import java.util.Random;

public class Main {

	//run 50 sort tests on random input
	public static void main( String[] args ) {
		for(int i = 0; i < 50; i++) {
			int ar[] = randomArray( 10000 );
			selectionSort( ar );
			System.out.println( "Is sorted =  " + isSorted( ar ) );
		}
	}

	static boolean isSorted( int ar[] ) {
		for ( int i = 0; i < ar.length - 1; i++ ) {
			if ( ar[ i ] > ar[ i + 1 ] )
				return false;
		}
		return true;
	}

	static int[] randomArray( int size ) {
		int a[] = new int[ size ];
		Random rand = new Random();
		for ( int i = 0; i < size; i++ )
			a[ i ] = rand.nextInt( 100000 );
		return a;
	}

	static private void selectionSort( int ar[] ) {
		for ( int i = 0; i < ar.length / 2; i++ ) {
			int minIndex = i, maxIndex = i;
			for ( int j = i; j < ar.length - i; j++ ) {
				if ( ar[ j ] < ar[ minIndex ] )
					minIndex = j;
				else if ( ar[ j ] > ar[ maxIndex ] )
					maxIndex = j;
			}
			//tricky: your going to first swap(i, minIndex), if maxIndex == i, then swap(ar.length-1-i, maxIndex) will
			//turn into swap(ar.length-1-i, minIndex), so you have to handle that possibility
			swap( ar, i, minIndex );
			if ( i == maxIndex )
				maxIndex = minIndex;
			swap( ar, ar.length - 1 - i, maxIndex );
		}
	}

	static private void swap( int ar[], int i, int j ) {
		int temp = ar[ i ];
		ar[ i ] = ar[ j ];
		ar[ j ] = temp;
	}
}



Thank you so much. I knew big was corrupting little, but I couldn't figure out how to fix it.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1