Selection Sort In Java
Introduction
In this example we are going to sort the values of an array using
selection sort. In selection sorting algorithm,
find the minimum value in the array then swap it first position. In next
step leave the first value and find the minimum value within remaining values.
Then swap it with the value of minimum index position. Sort the
remaining values by using same steps. Selection sort is probably the most intuitive sorting algorithm to invent.
The complexity of selection sort algorithm is in worst-case, average-case, and best-case run-time of Θ(n2), assuming that
comparisons can be done in constant time.
Code description:
In selection sort algorithm to find the
minimum value in the array. First assign minimum index in key (index_of_min=x).
Then
find the minimum value and assign the index of minimum value in key
(index_of_min=y). Then swap the minimum value with the value of minimum
index.
At next iteration leave the value of minimum index position and sort the
remaining values by following same steps.
Working of the selection sort : Say we have an array unsorted A[0],A[1],A[2]................ A[n-1] and A[n] as input. Then the following steps are followed by
selection sort algorithm to sort the values of an array . (Say we have a
key index_of_min that indicate the position of minimum value)
1.Initaily varaible index_of_min=0;
2.Find the minimum value in the unsorted array.
3.Assign the index of the minimum value into index_of_min variable.
4.Swap minimum value to first position.
5.Sort the remaining values of array (excluding the first value).
The code of the program :
public class selectionSort{
public static void main(String a[]){
int i;
int array[] = {12,9,4,99,120,1,3,10};
System.out.println("\n\n RoseIndia\n\n");
System.out.println(" Selection Sort\n\n");
System.out.println("Values Before the sort:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
selection_srt(array, array.length);
System.out.print("Values after the sort:\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
System.out.println("PAUSE");
}
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;
}
}
}
|
Output of the example:
C:\array\sorting>javac selectionSort.java
C:\array\sorting>java selectionSort
RoseIndia
Selection Sort
Values Before the sort:
12 9 4 99 120 1 3 10
Values after the sort:
120 99 12 10 9 4 3 1
PAUSE
C:\array\sorting>_
|
Download this example.
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
