JavaGian java tutorial and java interview question and answer

Selection Sort

In selection sort, the smallest value among the unsorted elements of the array is selected in every pass and inserted to its appropriate position into the array.

First, find the smallest element of the array and place it on the first position. Then, find the second smallest element of the array and place it on the second position. The process continues until we get the sorted array.

The array with n elements is sorted by using n-1 pass of selection sort algorithm.

• In 1st pass, smallest element of the array is to be found along with its index pos. then, swap A[0] and A[pos]. Thus A[0] is sorted, we now have n -1 elements which are to be sorted.
• In 2nd pas, position pos of the smallest element present in the sub-array A[n-1] is found. Then, swap, A[1] and A[pos]. Thus A[0] and A[1] are sorted, we now left with n-2 unsorted elements.
• In n-1th pass, position pos of the smaller element between A[n-1] and A[n-2] is to be found. Then, swap, A[pos] and A[n-1].

Therefore, by following the above explained process, the elements A[0], A[1], A[2],...., A[n-1] are sorted.

Example

Consider the following array with 6 elements. Sort the elements of the array by using selection sort.

A = {10, 2, 3, 90, 43, 56}.

Pass	Pos	A[0]	A[1]	A[2]	A[3]	A[4]	A[5]
1	1	2	10	3	90	43	56
2	2	2	3	10	90	43	56
3	2	2	3	10	90	43	56
4	4	2	3	10	43	90	56
5	5	2	3	10	43	56	90

Sorted A = {2, 3, 10, 43, 56, 90}

Complexity

Complexity	Best Case	Average Case	Worst Case
Time	Ω(n)	θ(n2)	o(n2)
Space			o(1)

Algorithm

SELECTION SORT(ARR, N)

• Step 1: Repeat Steps 2 and 3 for K = 1 to N-1
• Step 2: CALL SMALLEST(ARR, K, N, POS)
• Step 3: SWAP A[K] with ARR[POS]
  [END OF LOOP]
• Step 4: EXIT

SMALLEST (ARR, K, N, POS)

• Step 1: [INITIALIZE] SET SMALL = ARR[K]
• Step 2: [INITIALIZE] SET POS = K
• Step 3: Repeat for J = K+1 to N -1
  IF SMALL > ARR[J]
  SET SMALL = ARR[J]
  SET POS = J
  [END OF IF]
  [END OF LOOP]
• Step 4: RETURN POS

C Program

1. #include<stdio.h>  
2. int smallest(int[],int,int);  
3. void main ()  
4. {  
5.     int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
6.     int i,j,k,pos,temp;  
7.     for(i=0;i<10;i++)  
8.     {  
9.         pos = smallest(a,10,i);  
10.         temp = a[i];  
11.         a[i]=a[pos];  
12.         a[pos] = temp;  
13.     }  
14.     printf("\nprinting sorted elements...\n");  
15.     for(i=0;i<10;i++)  
16.     {  
17.         printf("%d\n",a[i]);  
18.     }  
19. }  
20. int smallest(int a[], int n, int i)  
21. {  
22.     int small,pos,j;  
23.     small = a[i];  
24.     pos = i;  
25.     for(j=i+1;j<10;j++)  
26.     {  
27.         if(a[j]<small)  
28.         {  
29.             small = a[j];  
30.             pos=j;  
31.         }  
32.     }  
33.     return pos;  
34. }  

Output:

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

---

C++ Program

1. #include<iostream>  
2. using namespace std;  
3. int smallest(int[],int,int);  
4. int main ()  
5. {  
6.     int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
7.     int i,j,k,pos,temp;  
8.     for(i=0;i<10;i++)  
9.     {  
10.         pos = smallest(a,10,i);  
11.         temp = a[i];  
12.         a[i]=a[pos];  
13.         a[pos] = temp;  
14.     }  
15.     cout<<"\n printing sorted elements...\n";  
16.     for(i=0;i<10;i++)  
17.     {  
18.         cout<<a[i]<<"\n";  
19.     }  
20.     return 0;  
21. }  
22. int smallest(int a[], int n, int i)  
23. {  
24.     int small,pos,j;  
25.     small = a[i];  
26.     pos = i;  
27.     for(j=i+1;j<10;j++)  
28.     {  
29.         if(a[j]<small)  
30.         {  
31.             small = a[j];  
32.             pos=j;  
33.         }  
34.     }  
35.     return pos;  
36. }  

Output:

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

---

Java Program

1. public class SelectionSort {  
2. public static void main(String[] args) {  
3.     int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
4.     int i,j,k,pos,temp;  
5.     for(i=0;i<10;i++)  
6.     {  
7.         pos = smallest(a,10,i);  
8.         temp = a[i];  
9.         a[i]=a[pos];  
10.         a[pos] = temp;  
11.     }  
12.     System.out.println("\nprinting sorted elements...\n");  
13.     for(i=0;i<10;i++)  
14.     {  
15.         System.out.println(a[i]);  
16.     }  
17. }  
18. public static int smallest(int a[], int n, int i)  
19. {  
20.     int small,pos,j;  
21.     small = a[i];  
22.     pos = i;  
23.     for(j=i+1;j<10;j++)  
24.     {  
25.         if(a[j]<small)  
26.         {  
27.             small = a[j];  
28.             pos=j;  
29.         }  
30.     }  
31.     return pos;  
32. }  
33. }  

Output:

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

---

C# Program

1. using System;                 
2. public class Program  
3. {  
4.       
5.       
6. public void Main() {  
7.     int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
8.     int i,pos,temp;  
9.     for(i=0;i<10;i++)  
10.     {  
11.         pos = smallest(a,10,i);  
12.         temp = a[i];  
13.         a[i]=a[pos];  
14.         a[pos] = temp;  
15.     }  
16.     Console.WriteLine("\nprinting sorted elements...\n");  
17.     for(i=0;i<10;i++)  
18.     {  
19.         Console.WriteLine(a[i]);  
20.     }  
21. }  
22. public static int smallest(int[] a, int n, int i)  
23. {  
24.     int small,pos,j;  
25.     small = a[i];  
26.     pos = i;  
27.     for(j=i+1;j<10;j++)  
28.     {  
29.         if(a[j]<small)  
30.         {  
31.             small = a[j];  
32.             pos=j;  
33.         }  
34.     }  
35.     return pos;  
36. }  
37. }  

Output:

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

---

Python Program

1. def smallest(a,i):  
2.     small = a[i]  
3.     pos=i  
4.     for j in range(i+1,10):  
5.         if a[j] < small:  
6.             small = a[j]   
7.             pos = j   
8.     return pos   
9.       
10. a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]  
11. for i in range(0,10):  
12.     pos = smallest(a,i)  
13.     temp = a[i]  
14.     a[i]=a[pos]  
15.     a[pos]=temp  
16. print("printing sorted elements...")  
17. for i in a:  
18.     print(i)  

Output:

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

---

Rust Program

1. fn main ()  
2. {  
3.     let mut a: [i32;10] = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
4.       
5.     for i in 0..10  
6.     {  
7.         let mut small = a[i];  
8.         let mut pos = i;  
9.         for j in (i+1)..10  
10.         {  
11.         if a[j]<small  
12.         {  
13.             small = a[j];  
14.             pos=j;  
15.         }  
16.     }  
17.         let mut temp = a[i];  
18.         a[i]=a[pos];  
19.         a[pos] = temp;  
20.     }  
21.     println!("\nprinting sorted elements...\n");  
22.     for i in &a  
23.     {  
24.         println!("{}",i);  
25.     }  
26. }   

Output:

printing sorted elements...

7
9
10
12
23
23
34
44
78
101

---

JavaScript Program

1. <html>  
2. <head>  
3. <title>   
4.     Selection Sort   
5. </title>   
6.     </head>  
7.     <body>   
8.     <script>  
9. function smallest(a,  n, i)  
10. {  
11.       
12.     var small = a[i];  
13.     var pos = i;  
14.     for(j=i+1;j<10;j++)  
15.     {  
16.         if(a[j]<small)  
17.         {  
18.             small = a[j];  
19.             pos=j;  
20.         }  
21.     }  
22.     return pos;  
23. }  
24. var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];  
25.     for(i=0;i<10;i++)  
26.     {  
27.         pos = smallest(a,10,i);  
28.         temp = a[i];  
29.         a[i]=a[pos];  
30.         a[pos] = temp;  
31.     }  
32.     document.writeln("printing sorted elements ...\n"+"<br>");  
33.     for(i=0;i<10;i++)  
34.     {  
35.         document.writeln(a[i]+"<br>");  
36.     }  
37.         </script>  
38.     </body>  
39. </html>  

Output:

printing sorted elements ...
7
9
10
12
23
23
34
44
78
101

---

PHP Program

1. <html>  
2. <head>  
3. <title>Selection sort</title>  
4. </head>  
5. <body>  
6. <?php  
7. function smallest($a,  $n, $i)  
8. {  
9.       
10.     $small = $a[$i];  
11.     $pos = $i;  
12.     for($j=$i+1;$j<10;$j++)  
13.     {  
14.         if($a[$j]<$small)  
15.         {  
16.             $small = $a[$j];  
17.             $pos=$j;  
18.         }  
19.     }  
20.     return $pos;  
21. }  
22. $a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);  
23.     for($i=0;$i<10;$i++)  
24.     {  
25.         $pos = smallest($a,10,$i);  
26.         $temp = $a[$i];  
27.         $a[$i]=$a[$pos];  
28.         $a[$pos] = $temp;  
29.     }  
30.     echo "printing sorted elements ...\n";  
31.     for($i=0;$i<10;$i++)  
32.     {  
33.         echo $a[$i];  
34.         echo "\n";  
35.     }  
36. ?>  
37. </body>  
38. </html>  

Output:

printing sorted elements ...
7
9
10
12
23
23
34
44
78
101