Selection Sort
Selection sort is a very easy and simple sorting algorithm. It
repeatedly selects the smallest or largest elements from the array and places it
in the first position of the array. This process is repeated with the rest of
the array. The second smallest or largest element is selected and put onto the
next slot and this process is repeated till the end of the array. Time
complexity is O(n2)
Java program for Selection Sort
In the following, we have not taken ZERO into the array number[]. In the program, we first print the data elements without sorting them. After that selection sort algorithm applied. In that, a value is selected and checked with another value, if it is greater than the previous one then the value is swapped with each other. In this fashion, all the elements of the array arranged in ascending order. And print the elements.
import java.util.Scanner;
public class SelectoinSort {
public static void main(String
arg[]) {
Scanner sc = new
Scanner(System.in);
int number[] = new
int[10];
int i, j, l, k = 0, m;
int t; // temperory variable
System.out.println("Enter integer");
for (i = 0; i < 10;
i++) {
m = sc.nextInt();
if (m != 0) {
number[k] = m;
k++;
}
}
// Printing unsorted data
System.out.println("Unsorted order");
for (i = 0; i < k; i++)
{
System.out.print(number[i] + " ");
}
// Sorting technique
for (i = 0; i < k; i++)
{
for (j = i + 1; j <
k; j++) {
if (number[i]
>number[j]) {
t = number[i];
number[i] =
number[j];
number[j] = t;
}
}
}
// Print sorted data
System.out.println("\n Sorted order");
for (i = 0; i < k; i++)
{
System.out.print(number[i] + " ");
}
}
}
Sample output
Enter integer
50
65
90
66
45
21
45
65
25
89
Unsorted order
50 65 90 66 45 21 45 65 25 89
Sorted order
21 25 45 45 50 65 65 66 89 90
SN
|
Variables
|
Type
|
Description
|
1
|
main()
|
void
|
This is the main entry point of the program
|
2
|
number[]
|
int
|
int array for the name
|
3
|
m
|
int
|
For checking zero
|
4
|
i, j
|
int
|
i and j are for loop
|
5
|
t
|
int
|
Use for a temporary variable
|
Program to sort an array of strings using Selection Sort
import
java.util.Scanner;
public class
SelectionSortForString
{
public static void main(String arg[]) {
Scanner sc = new Scanner(System.in);
// String Array
String studentName[] = new String[10];
int i, j, l ;
String t;
System.out.println("Enter Student
Name:");
for (i = 0; i < 10; i++) {
studentName[i]= sc.next();
}
// Printing unsorted data
System.out.println("Unsorted
order");
for (i = 0; i < 10; i++) {
System.out.print(studentName[i] +
" ");
}
// Sorting technique
for (i = 0; i <9; i++) {
for (j = i + 1; j < 10; j++) {
if (studentName[i].compareTo(studentName[j])>0)
{
t = studentName[i];
studentName[i] =
studentName[j];
studentName[j] = t;
}
}
}
// Print sorted data
System.out.println("\n Sorted
order");
for (i = 0; i < 10; i++) {
System.out.print(studentName[i] +
" ");
}
}
}
Analysis of Selection sort
Selecting the lowest element requires scanning all n elements (this takes n − 1
comparisons) and then swapping it into the first position. Finding the next
lowest element requires scanning the remaining n − 1 elements and so on
(n-1) + (n-2) + (n-3) + ….. + (n-k) + 3 + 2 + 1
n(n-1)/2
O(n2)
n(n-1)/2
O(n2)