/* related posts with thumb nails */

### procedure for Selection sort:

Selection sort is a sorting algorithm is a type of comparison sort. It is inefficient on large lists, and generally performs worse than insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms. The selection sort performs the same number of comparisons as the bubble sort: N*(N-1)/2. For 10 data items, this is 45 comparisons. However, 10 items require fewer than 10 swaps. Thus, the selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N2) to O(N). Unfortunately, the number of comparisons remains O(N2).

Selection sort logic:

1. Find the maximum value in the list

2. Swap it with the value in the last position

3. Repeat the steps above for the remainder of the list

Complexity: The time complexity of Selection sort is shown below in three different cases and worst-case space complexity.

 Worst Case Best Case Average Case Worst case Space Complexity O(n2) O(n2) O(n2) O(n) total, O(1) auxiliary

Example: The selection sort marks the last element (12). It then goes through the list to find the biggest number (72). It swaps this with the last element and the biggest element is now in its correct position. It then marks the last but one element (1) and looks through the remaining data (excluding the last element) for the next biggest number (64). These two numbers are then swapped. This process continues until n-1 passes have been made.

 Initial Data 27 11 64 →72 1 12 1st pass 27 11 →64 12 1 72 2nd pass →27 11 1 12 64 72 3rd pass →12 11 1 27 64 72 4th pass 1 →11 12 27 64 72 5th pass 1 11 12 27 64 72

Program: The following program uses Selection sort algorithm to sort the elements of the array.

import java.io.*;

class SelectionSort

{

public static void main(String as[]) throws Exception

{

int i,j,k,n,t,max,a[]=new int;

System.out.println("How many values:");

System.out.println("Enter Values:");

for(i=0;i

for(i=0;i

{

max=a;

k=0;

for(j=1;j

{

if(a[j]>max)

{

max=a[j];

k=j;

}

}

t=max;

a[k]=a[n-i-1];

a[n-i-1]=t;

}

System.out.println("After Sorting");

for(i=0;i

System.out.print("\t"+a[i]);

}

}

Output:

How many values: 4

Enter Values:

45

36

87

12

After Sorting:

12 36 45 87

Related Topics: