Hello,
For some work I have to implement the selection sort algorithm on an array list, I dont really know how to do this. I have started off the code but I just need to actually implement the selection sort! This is proving to be the stumbling block.

Here is what I have so far:

import java.util.ArrayList;
import java.util.Random;

public class selectionSort
{
  public static final int list = 10;
  public static void main(String[] args){
    ArrayList<Integer> input = new ArrayList<Integer>();
    Random r = new Random();
    System.out.print("Selection sort-algorithm");   
    System.out.print("\n\nInput: ");
    for (int i = 0; i < list; i++)
        input.add(r.nextInt(list + 1));
    System.out.print("Input: ");
    for (int number : input)
        System.out.print(number + " ");
    System.out.print("\n\nOutput: ");
    for (int number : selectionsort(input))
        System.out.print(number + " ");
  }

If somebody could give me some advice/help then that would be great.

Thanks in advance!

First you need to find the algorithm for the selection sort and distill it down to steps that can be programmed.


What is the code you posted supposed to do? It needs a few comments to describe what each section is to do.

I can modify your program ..I used sort() methd of Collections class to sort the element

import java.util.*;
class selectionSort{ 
 public static final int list = 10; 
 public static void main(String[] args){   
 ArrayList<Integer> input = new ArrayList<Integer>();  
 Random r = new Random();
 System.out.print("Selection sort-algorithm");   
 System.out.print("\n\nInput: ");  
 for (int i = 0; i < list; i++)       
 input.add(r.nextInt());  
 System.out.println("Input Data"+input);  
 Collections.sort(input);
 System.out.println("Output Data"+input);  
 
	}
}
Comments
Meaningless post giving code

@dharma117 What is the purpose of your post?
How does it help the OP learn how to write a selection sort?

x

Thank you but this does not help me at all.

First you need to find the algorithm for the selection sort and distill it down to steps that can be programmed.


What is the code you posted supposed to do? It needs a few comments to describe what each section is to do.

Well at the minute its not really doing anything but thats the point. Im not too sharp on selection sort or on my java so this seems to be a recipe for disaster for me! Also, none of my textbooks can help either.
My understanding of selection sort is that it finds the minimum value, it then swaps it with the value in cell 0 and this loops moving on to the next cell.
The start of my code posted is following a similar format I have used to code for a quicksort implementation, I am comparing the two so I wanted them to use the same variables and such.

What is your design so far?
It looks like you'll need some loops and some pointers.
Use a piece of paper and a pencil to get the logic of moving thru the list, swapping the elements at the pointers and moving the pointers.

I know how to code it using a normal array, its just the array list because of positions and such, especially when the input will be 10 random numbers.

public static void selection_srt(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;
  }
  }

That code I just lifted from a website, I understand how its working though, I just dont know how to apply it to an array list.

Read the API doc for the ArrayList class and see which methods to use to access its element.

Your code needs formatting. It makes a big difference to someone else trying to read your code. Align } with the start of the lines with the starting {
Indent the code between those two lines 3 to 4 spaces. Each nesting level should go in more. Also spaces around operators make it easier to see them.

for(int y=x; y < n; y++){
     // Compare current smallest value with the current element
     if(array[index_of_min] < array[y]) {
        index_of_min = y;  // Save the index to the smaller value
     }
  } // end for(y)

Edited 5 Years Ago by NormR1: n/a

Ok, so far ive got:

import java.util.ArrayList;
import java.util.Random;

public class selectionSort
{
  public static final int list = 10;
  public static void main(String[] args){
    ArrayList<Integer> input = new ArrayList<Integer>();
    Random r = new Random();
    System.out.print("Selection sort-algorithm by Oliver Johnson");   
    System.out.print("\n\nInput: ");
    for (int i = 0; i < list; i++)
        input.add(r.nextInt(list + 1));
    System.out.print("Input: ");
    for (int number : input)
        System.out.print(number + " ");
    System.out.print("\n\nOutput: ");
    for (int number : selectionsort(input))
        System.out.print(number + " ");
  }
  
  public static ArrayList<Integer> selectionsort(ArrayList<Integer> input) {
      if (input.size() <= 1)
          return input;
      for (int x = 0; x < n; x++) {
          int x = input.get(0);
      for (int y = x; y < n; y++) {
          if(input.get(0) < [B]....[/B]

I just dont know what to do past the bold elipsis though! Ive been looking at code using an array and trying to almost convert it, so im not sure if what ive posted is correct?

How does your code follow the algorithm in your sort method?
You listed three steps:

it finds the minimum value,
it then swaps it with the value in cell 0 and this
loops moving on to the next cell.

Your formatting is still off or you are using the wrong tags to post it. The second if should be indented from the first:

for (int x = 0; x < n; x++) {
     int x = input.get(0);
     for (int y = x; y < n; y++) {

How does your code follow the algorithm in your sort method?
You listed three steps:

I dont know because I dont know if what ive put down is right. As I said, im copying existing code using an array and trying to change it so it uses an array, so I dont know where x or n has came from :s

Ok then forget about copying existing code.
Do the three steps you listed in your own code.
First write a loop to find the index of the smallest element.

Ok then forget about copying existing code.
Do the three steps you listed in your own code.
First write a loop to find the index of the smallest element.

for (int x = 0; x < list.size(); x++) {
          int x = input.get(0);

Is this correct? Find the index of the first element and compare it to the next element in the array list and continue?

Edited 5 Years Ago by xThrash: n/a

Your posted code gets the value of the first element (its index is 0).
What is The for statement you posted supposed to do?
You have defined x twice.

Before writing any more code, describe the steps you must take to find the smallest element in the array.

Your posted code gets the value of the first element (its index is 0).
What is The for statement you posted supposed to do?
You have defined x twice.

Before writing any more code, describe the steps you must take to find the smallest element in the array.

The code I posted (I thought at least) checked the value of the element at index 0 and then checked all of the rest of the values.

I think I need more help than this because im just not getting anywhere, I feel like im going round in circles.

The last code you posted only copied the value of element at index 0 to the variable x.
It do not check anything.
In your loop you must compare the value of the first element against all the other elements in the array. You would use a < or > operator to compare the values to see which was greater.

If you can't write down, in English, the steps to move thru an array and find the smallest value, you'll have a hard time writing the code.
Here is a start:
Get value of first element into firstElVal
Set the idx to 0
begin loop thru rest of array one by one starting at second element
if the current element's value is less than firstElVal
then save the index of the current element in idx
end loop
Swap the value at idx with the value at 0

The last code you posted only copied the value of element at index 0 to the variable x.
It do not check anything.
In your loop you must compare the value of the first element against all the other elements in the array. You would use a < or > operator to compare the values to see which was greater.

If you can't write down, in English, the steps to move thru an array and find the smallest value, you'll have a hard time writing the code.
Here is a start:
Get value of first element into firstElVal
Set the idx to 0
begin loop thru rest of array one by one starting at second element
if the current element's value is less than firstElVal
then save the index of the current element in idx
end loop
Swap the value at idx with the value at 0

OK I understand this, obviously I can write it in plain English but the point is I dont know how to write it in java which is the problem.
My java isnt great, I openly admit that which is why ive came and asked because I was hoping someone would be able to help me a little more. I do appreciate your help though but I was hoping someone could give me some code, I find it much easier to work backwards; when someone tells me what it is and why then I usually pick it up and learn from there, I dont need much, just a start.

Sorry, I don't give out code for homework.
You have working code and you have descriptions of what it does.
Now its up to you.

Good luck.

Sorry, I don't give out code for homework.
You have working code and you have descriptions of what it does.
Now its up to you.

Good luck.

Its not about giving out code for homework, its just helping. Plus, it isnt homework either.
I havent actually gained anything from this thread yet, weve just discussed what we already know; my original code was wrong but I still dont know how to correct it in java and ive defined a selection sort algorithm which I knew before I even posted this thread!

If you have a design, then let's work thru it step by step.
I listed 3 steps above.
I suggested as a first problem to write a loop to find the index of the smallest value in the list. You gave up after writing two lines of code.
So lets get simpler.
Can you Write a loop that prints out every element in an array and its index?

This article has been dead for over six months. Start a new discussion instead.