Implementation of selection sort in Java

Question

I think I have done the selection sort but I am not sure. Is this really an implementation of selection sort?

static void selectionSort()
    {
        int min = Integer.MIN_VALUE;
        int n = 0;
        for(int I=0; I<arraySize; I++)
        {

            min = dataArray[I];
            for(int j=I; j<n; j++)
            {
                if(dataArray[min]<dataArray[j])
                  {
                        min = j;
                        if(dataArray[min] < dataArray[I])
                        {
                            int temp = dataArray[I];
                            dataArray[I] = dataArray[min];
                            dataArray[min] = temp;
                        }
                  }
            }
        }   
    }

How could this works if in the inner cycle you have a condition like j<n and n=0 just before the begin of the first cycle? — DonCallisto
– DonCallisto, Commented Mar 15, 2012 at 13:23

aioobe · Accepted Answer · 2012-03-15 13:37:59Z

4

I'm not sure I understand how your algorithm works at all. Specifically, you do

min = dataArray[i];

and then later

dataArray[min]<dataArray[j]

i.e. you treat min both as a value in the array, and an index.

Selection sort works as follows:

Find the minimum value in the list
Swap it with the value in the first position
Repeat the steps above for the remainder of the list

(source)

The changes required for your code to accurately implement selection sort would be the following:

Change the inner loop to just find the index of the smallest element. Call it minIndex for instance.
Do the swapping after the inner loop. i.e., swap element at index I with minIndex.

Oh, and as DonCallisto points out in the comments, you may want to do n = dataArray.length instead of n = 0 :-)

edited Mar 15, 2012 at 13:37

answered Mar 15, 2012 at 13:22

aioobe

423k115 gold badges831 silver badges844 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Kiril Over a year ago

i assign the same value of i to j

DonCallisto Over a year ago

for(int j=I; j<n; j++) is this cycle ever executed?

aioobe Over a year ago

Haha, no that seems like a minor problem too ;-)

Bo Persson · Accepted Answer · 2012-07-24 19:50:41Z

public class SelectionSort {

 /**
  * @Author Chandrasekhara Kota
  */

 public static void main(String[] args) {

        int arr[]={9,1,8,5,7,-1,6,0,2,2718};
        int sortedArr[]=selectionSort(arr);
        for (int i = 0; i <sortedArr.length; i++) 
        { 
           System.out.println(sortedArr[i]);
        }

      }

      private static int[] selectionSort(int[] arr) { 

      int  minIndex, tmp; 
      int n = arr.length; 
      for (int i = 0; i < n - 1; i++) 
      { 
              minIndex = i; 
              for (int j = i + 1; j < n; j++) 
                   if (arr[j] < arr[minIndex]) 
                        minIndex = j; 
              if (minIndex != i) { 
                    tmp = arr[i]; 
                    arr[i] = arr[minIndex]; 
                    arr[minIndex] = tmp; 
              } 
        }
  return arr; 

}

}

Frank · Accepted Answer · 2014-02-01 14:59:51Z

Here is a selection sort implementation in java -

public class SelectionSort {

static int intArray[] = { 10, 5, 100, 1, 10000 };

public static void doSort() {
    for (int outer = 0; outer < intArray.length; outer++) {
        int minPosition=outer;
        for(int inner=outer;inner<intArray.length;inner++){
            if(intArray[inner]<intArray[minPosition]){
                minPosition=inner;
            }
        }
        int temp=intArray[minPosition];
        intArray[minPosition]=intArray[outer];
        intArray[outer]=temp;
    }
}

public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
        System.out.print("  " + intArray[i]);
    }
}

public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort();
    System.out.print("\nArray After Sorting ->");
    printArray();
}

}

The above code is picked from - http://www.javabrahman.com/algorithms-in-java/selection-sort-in-java/. This link has detailed explanation on the working of the above code just in case you need the same.

Collectives™ on Stack Overflow

Implementation of selection sort in Java

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related