Selection sort is a in-place sorting algorithm. Works well small files.It starts by comparing the
entire list for the lowest item and moves it to the #1 position. It then
compares the rest of the list for the next-lowest item and places it in the #2
position and so on until all items are in the required order.
Steps to perform selection sort:
Compare all the card from 7 to 3 (step)
Find the smallest shorted card (step 4) i.e., 2
So we swap this card with the first unsorted card i.e., 2 is swap with 7
|2 8 5 7 4 6 3
Similarly, we repeat the step
Find the smallest unsorted card i.e., 3 and replace with first unsorted card 8
Find the smallest unsorted card i.e., 4 and replace with first unsorted card 5
2 3|4 7 5 6 8
Move the marker
2 3 4|7 5 6 8
Find the smallest unsorted card i.e., 5 and replace with first unsorted card 7
2 3 4|5 7 6 8
Move the marker
2 3 4 5|7 6 8
Find the smallest unsorted card i.e., 6 and replace with first unsorted card 7
2 3 4 5|6 7 8
Move the marker
2 3 4 5 6|7 8
Steps to perform selection sort:
- Get a hand of unsorted card.
- Set a marker for unsorted section at the front of hand
- Repeat 4 to 7 steps until one card is left in the unsorted selection
- Compare all unsorted card
- Select the smallest unsorted card
- Swap this card with the first card in the unsorted section
- Move the marker.
- Stop
Let take a deck of unsorted card
(step 1).
7 8 5 2 4 6 3
Now set a marker at the front of unsorted card
(step 2).
|7 8 5 2 4
6 3
Compare all the card from 7 to 3 (step)
Find the smallest shorted card (step 4) i.e., 2
So we swap this card with the first unsorted card i.e., 2 is swap with 7
|2 8 5 7 4 6 3
Move the marker (step 8)
2|8 5 7 4 6 3
Similarly, we repeat the step
Find the smallest unsorted card i.e., 3 and replace with first unsorted card 8
2|3 5 7 4 6 8
Move the marker
2 3|5 7 4 6 8
Move the marker
2 3|5 7 4 6 8
Find the smallest unsorted card i.e., 4 and replace with first unsorted card 5
2 3|4 7 5 6 8
Move the marker
2 3 4|7 5 6 8
Find the smallest unsorted card i.e., 5 and replace with first unsorted card 7
2 3 4|5 7 6 8
Move the marker
2 3 4 5|7 6 8
Find the smallest unsorted card i.e., 6 and replace with first unsorted card 7
2 3 4 5|6 7 8
Move the marker
2 3 4 5 6|7 8
Find the smallest unsorted card i.e., 7 and replace with
first unsorted card 7
2 3 4 5 6|7 8
Move the marker
2 3 4 5 6 7|8
Now we have one unsorted card means algorithm is complete.
Move the marker
2 3 4 5 6 7|8
Now we have one unsorted card means algorithm is complete.
Demo:
Performance :
- Worst Case Complexity : O(n^2)
- Average Case Complexity : O(n^2)
- Best Case Complexity : O(n^2)
If you know anyone who has started learning Java, why not help them out! Just share this post with them.
Thanks for studying today!...
Thanks for studying today!...
Hey.. Entire code is erfect. The only things that can be added here to escape from unwanted swap for same element, i.e., don't need to do swapping when no element is found
ReplyDeletestatic int[] selectionSort( int[] array){
System.out.println("array.length="+ array.length);
for (int i = 0; i < array.length - 1; i++) {
System.out.println("******************");
boolean flag = false;
int pos = i;
for (int j = i+1; j < array.length; j++) {
if( array[pos] > array[j]){
pos = j;
flag = true;
}
}
if( flag ){
int temp = array[i];
array[i] = array[pos];
array[pos] = temp;
}
System.out.println(Arrays.toString(array));
}
return array;
}