22 replies to this topic

[An Alien]

I just started learning about arrays and I have this is going to lead me to more advanced sorting lists and stuff in my computer science class. But we're supposed to find out a way to sort these without learning the easy sorting stuff java has. So I want to ask you guys. I have a program that creates an int array and then adds values to each index. Then I need it to print out all of the values in order. But I tried one method that I came up with but it didn't work. So here's my code:
import java.util.Scanner;

public class ArrayTestFA {

    public static void main(String[] args) {

    	

    	Scanner in = new Scanner (System.in);

    	int input;

    	

    	int var = 0;

    	System.out.println("How many values would you like your array to hold?");

    	var = in.nextInt();

    	int array[] = new int[var];

    	

    	

    	

    	for(int count=0; count<=array.length; count++){

    		System.out.println("Enter the value for array index: " + count);

    		input = in.nextInt();

    		

    		array[count] = input;	

    	}

    	

    	

    }

}

[lethalwire]

I'd check out the different sorting algorithms.
Sorting algorithm - Wikipedia, the free encyclopedia

IIRC, you're the one in the AP class?
If so, you should probably study selection sort, insertion sort, and mergesort the most.

Selection sort and insertion sort are rather simple to understand.
Mergesort is when sorting gets fun.

I'd start with selection sort as it seems the easiest.
Loop through the array while keeping track of the smallest value you come across.
When you've looped through the entire array, swap the smallest value with the first position.
Loop through the array again, but this time start from the next index. Keep track of the smallest number again, ( no need to worry about index 0 because you should start at index 1 this time ).
Swap the smallest number with the index 1.
Repeat for all indexes.

There are some great animations of this process online. Be sure to google.

[An Alien]

Thanks man, I found out how selection sort works, but haven't found out how exactly implement that in my code.

So a simple example or a code snippet is what I'm looking for now.

And, yes, I am that same guy asking about the AP comp sci exam. We just starting learning about basic arrays, but I'm a step ahead of the class cause I've done some outside research and have wonderful helpers here.

[wim DC]

Wikipedia to the rescue :D
On Selection sort - Wikipedia, the free encyclopedia
Is a code snippet. It doesn't say it's Java. But it's incredibly close to it.

/* a[0] to a[n-1] is the array to sort */

int iPos;

int iMin;

 

/* advance the position through the entire array */

/*   (could do iPos < n-1 because single element is also min element) */

for (iPos = 0; iPos < n; iPos++)

{

  /* find the min element in the unsorted a[iPos .. n-1] */

 

  /* assume the min is the first element */

  iMin = iPos;

  /* test against all other elements */

  for (i = iPos+1; i < n; i++)

    {

      /* if this element is less, then it is the new minimum */  

      if (a[i] < a[iMin])

        {

          /* found new minimum; remember its index */

          iMin = i;

        }

    }

 

  /* iMin is the index of the minimum element. Swap it with the current position */

  if ( iMin != iPos )

  {

    swap(a, iPos, iMin);

  }

}

The only thing you don't have in Java is a Swap method.
And here, they name their variables starting with 'i' because it's an int. That's not really done in Java either.

[An Alien]

I don't really understand that code. I don't get what pos is for. Min is for minimum, but what is the "n" for?

Also, my stupid CS teacher doesn't want us to import code from other places. He says that you don't think if you just add a line of somebody else's code. But we need to know how to do this to for the exam. He said it himself that he didn't know some questions on the AP test. He shouldn't be teaching CS, I wish I had a teacher that actually knows this stuff.

[lethalwire]

If you can't import anything then just read what the algorithm does. After that determine what variables you'll need.
You'll need to
1) loop through an array
2) keep track of a minimum value
3) swap it with certain index

most algorithsm will use min, max, pos, etc.
They just mean minimum, maximum, position.

[wim DC]

I would do just like lethalwire. (No, i would actually copy paste from wiki ^^, but...)
Write some kind of pseudo code, or a list of what your code needs to do to perform a selection sort.

Loop trough array.
------
First loop: whole array.
Find minimum value, put it at the 1st position. Put the element of the 1st position at the minimimum value's position (so basicly swap the element at position 1, with the minimum element)
------
2nd loop: whole array, starting from position 2 (or 1, zero-based)
Find minimum value, put it at the 2st position. Put the element of the 2st position at the minimimum value's position (so basicly swap the element at position 2, with the minimum element)
------
...
...
Done.
Now just transform that into code and you're done :D

[An Alien]

How do I make it so that it separates the ones it's already sorted from the unsorted ones? I understand how to swap them by making a temp swap int and use that to swap the values for two indexes. But then I need to isolate the ones I've already looked at so I don't keep comparing the same values.

[lethalwire]

the for loop index should take care of this.
For example:

Define a list LIST := { 9, 3, 0, 1}

index := 0 // this is where we start

smallestValueIndex; // keep track of value by index

for( starting at index, loop while index < LIST.length, increment index by one ) {

    smallestValueIndex = index;

    for(  index + 1 ( let's call it j ), loop while j < LIST.length, increment j by one ) { 

       if( LIST[ j ] is less than LIST[ smallestValueIndex ] then

            smallestValueIndex = j;

        else 

            do nothing

    }

    swap( index, smallestValueIndex );

}

The first time through we have

LIST = { 9, 3, 0, 1 }

smallestValueIndex = 0;

index = 0;

j = 1; // remember j starts off as index + 1, but then changes in the inner-for loop

So we'll do our first test
if( LIST[ j ] is less than LIST[ smallestValueIndex ]
or ( substituting numbers in )
if ( list[ 1 ] is less than LIST[ 0 ] )
or ( substituting in correct values )
if ( 3 is less than 9 )
Now ask yourself, is 3 < 9 ??? I hope so.
So set smallestValueIndex equal to 1 ( which is j ) now.
so we'll increment j of the inner-for loop. We now have:

LIST = { 9, 3, 0, 1 }

smallestValueIndex = 1;

index = 0;

j = 2; // remember j starts off as index + 1, but then changes in the inner-for loop

We'll do the same test again, but with a different index.
is LIST[2] < LIST[ 1 ] ???
or
is 0 < 3 ?? I hope so, so we'll set smallestValueIndex to j, which is 2
again...

LIST = { 9, 3, 0, 1 }

smallestValueIndex = 2;

index = 0;

j = 3; // remember j starts off as index + 1, but then changes in the inner-for loop

again...
is LIST[J] < list[ smallestValueIndex ] ?
or
is 1 < 0??? I hope not!
so don't set smallestValueIndex to anything different, leave it alone.
Now we have

LIST = { 9, 3, 0, 1 }

smallestValueIndex = 2;

index = 0;

j = 4; // remember j starts off as index + 1, but then changes in the inner-for loop

j == 4 means that the inner loop will terminate because it doesn't pass it's conditional test
which leaves us at:

swap( index, smallestValueIndex );

which just means, swap the value at index, with the value at smallestValueIndex
or
swap ( 0, 2 ).
this should leave us with:

LIST = { 0, 3, 9, 1 }

smallestValueIndex = 1;

index = 1;

j = 2; // remember j starts off as index + 1, but then changes in the inner-for loop

Notice 0 and 9 were swapped
index was increased by one
smallestValueIndex is now index (again)
j = 2 which is index + 1 ( again )

By index increasing after the inner-for loop terminates, it causes the algorithm to never check anything before index. ( anything before index is already sorted )

[An Alien]

Wow, that was quite confusing. I understood it a little. But with multiple for loops, my mind just gets lost. lol. But you did a great job explaining cause I did understand this a little. I tried to copy your code exactly but I'm not sure if I did it right. I also created a swap method. I wish I could just user Arrays.sort lol.
Code:

import java.util.Scanner;

public class ArrayTestFA {

    public static void main(String[] args) {

    	

    	Scanner in = new Scanner (System.in);

    	int input;

    	

    	int var = 0;

    	System.out.println("How many values would you like your array to hold?");

    	var = in.nextInt();

    	int min = 999999999;

    	int array[] = new int[var];

    	int swap1 = 0;

    	int swap2;

    	

    	

    	

    	

    	for(int count=0; count<array.length; count++){

    		System.out.println("Enter the value for array index: " + count);

    		input = in.nextInt();

    		

    		array[count] = input;

    		

    		if (input < min){

    			min = input;

    			swap1 = array[0];

    			array[0] = min;

      		}

    		

    	}

    	

    	int index = 0;

    	int smallestValueIndex = 0;

    	

    	for (index=0; index < array.length; index++){

    		for(int j = index + 1; j <array.length; j++){

    			if (array[j] < array[smallestValueIndex]){

    				smallestValueIndex = j;

    				

    			}

    			

    		}

    	    swap( index, smallestValueIndex );

    	}

    	

    	printArray(array);

    	

    	

    }


	private static void swap(int index, int smallestValueIndex) {

		int swap1;

		swap1 = index;

		index = smallestValueIndex;

		smallestValueIndex = swap1;

	}

	

	private static void printArray(int[] array){

		for(int count=0; count< array.length; count++){

			System.out.println(array[count]);

		}

	}


}

[lethalwire]

You're missing 2 small pieces.

Define a list LIST := { 9, 3, 0, 1}

index := 0 // this is where we start

smallestValueIndex; // keep track of value by index

for( starting at index, loop while index < LIST.length, increment index by one ) {

   [COLOR="red"] smallestValueIndex = index;[/COLOR]

    for(  index + 1 ( let's call it j ), loop while j < LIST.length, increment j by one ) { 

       if( LIST[ j ] is less than LIST[ smallestValueIndex ] then

            smallestValueIndex = j;

        else 

            do nothing

    }

    swap( index, smallestValueIndex );

}

Your swap method isn't actually swapping the data in the array around. Instead it's just swapping 2 numbers around. (The indexes)
Example:
When you want to swap the numbers 4, and 8 out of { 3, 1, 8, 4, 8 }
You're storing 4 in index and 8 in smallestValueIndex.
You correctly swap these 2 INDEXES around but you want to swap the data in the array around!
You need to pass your array as a paramter INTO your swap method.
Example:

swap( array[], int index1, int index2 ) {

    int temporary = array[ index1 ]; // holds data at index1

    // code omitted for you to complete

}

[An Alien]

Crap, eclipse somehow changed that. I changed it to the way I originally made the swap method. But it looks like it is still wrong.

    	int index = 0;

    	int smallestValueIndex = 0;

    	

    	for (index=0; index < array.length; index++){

    		for(int j = index + 1; j <array.length; j++){

    		    smallestValueIndex = index;

    			if (array[j] < array[smallestValueIndex]){

    				smallestValueIndex = j;

    				

    			}

    			

    		}

    	    swap(array, array[index], smallestValueIndex );

    	}

    	

    	printArray(array);

    	

    	

    }


	private static void swap(int x[],int index, int smallestValueIndex) {

		int swap1;

		swap1 = x[index];

		x[index] = smallestValueIndex;

		smallestValueIndex = swap1;

	}

	

	private static void printArray(int[] array){

		for(int count=0; count< array.length; count++){

			System.out.println(array[count]);

		}

	}


}