Contents of page >
- Diagram of Selection sort in java >
- Logic explanation of Selection Sort in java >
- Full Program/SourceCode/Example of Selection Sort in java >
- Complexity of Selection Sort in java >
- Explanation of complexity of Selection Sort in java>
- Complexity of Selection Sort in graph >
Selection sort offers better performance as compared to Bubble Sort.
Complexity offered by Selection sort is O(n2) but later on in post we will see how Selection Sort is better than Bubble Sort.
We can use Bubble Sort, Insertion Sort, merge Sort, quick Sort which may offer better time complexity.
Diagram of Selection sort in java >
Let’s see diagram below where we are going to arrange these people in ascending order of their heights using Selection Sort.
Logic explanation of Selection Sort in java >
Start comparing these persons.
Start at position 1, and finding the minimum, swap it with position 1.
Continue this process until all the men’s become sorted.
In first pass, Swap the shortest person with the player on the 0th position or extreme left. You have now
sorted one person and made N-1 comparisons, but number of swaps done are only one.
In the next pass, follow exactly same process you did in first pass, ignore the person on the 0th position as we have already sorted that person in first pass. Thus, the algorithm starts the second pass at position 1, instead of 0.
With each succeeding pass, one more person becomes sorted and placed on the left, and one less person needs to be considered when finding out the new minimum.
Full Program/SourceCode/Example of Selection Sort in java >
/**
* This class holds reference of array,
* which has to be sorted.
* And performs Selection sorting in java
*/
class SelectionSortArray {
private int[] ar;
private int index; //holds current position of array, by default it is initialized with 0
/**
* Constructor for initializing Array
*/
public SelectionSortArray(int maxSize)
{
ar = new int[maxSize]; // creation of array
index = 0;
}
/**
* This method inserts elements in Array.
*/
public void insert(int value)
{
ar[index++] = value; // increment the current index
}
/**
* This method Sort Array using Selection Sort in java
*/
public void selectionSort() {
int outer, inner, minimum;
for (outer = 0; outer < index - 1; outer++) // outer loop
{
minimum = outer;
for (inner = outer + 1; inner < index; inner++)// inner loop
if (ar[inner] < ar[minimum]) // if minimum greater,
minimum = inner; // we have a new minimum
swap(outer, minimum); // swap them
}
}
/**
* This method swaps two elements in Array
*/
private void swap(int pos1, int pos2) {
int temp = ar[pos1];
ar[pos1] = ar[pos2];
ar[pos2] = temp;
}
/**
* This method Display Array
*/
public void display()
{
for (int i = 0; i < index; i++)
System.out.print(ar[i] + " ");
System.out.println("");
}
}
/**
* Main class - Which will call SelectionSorting class
*/
public class SelectionSortAlgorithmExample {
public static void main(String[] args) {
int maxSize = 10; // initial size of Array
SelectionSortArray selectionSortArray;
selectionSortArray = new SelectionSortArray(maxSize); // creation of array
selectionSortArray.insert(21);
selectionSortArray.insert(1);
selectionSortArray.insert(31);
selectionSortArray.insert(51);
selectionSortArray.insert(41);
selectionSortArray.insert(91);
selectionSortArray.insert(61);
selectionSortArray.insert(32);
selectionSortArray.insert(36);
selectionSortArray.insert(93);
System.out.print("Display Array elements before Selection sorting: ");
selectionSortArray.display(); // display Array elements before sorting
selectionSortArray.selectionSort(); // Selection sort the array
System.out.print("Display Array elements after Selection sorting: ");
selectionSortArray.display(); // display Array elements after sorting
}
}
/* OUTPUT
Display Array elements before Selection sorting: 21 1 31 51 41 91 61 32 36 93
Display Array elements after Selection sorting: 1 21 31 32 36 41 51 61 91 93
*/
|
So, we wrote program to do Selection Sort of array in java.
Complexity of Selection Sort in java >
Best,average and worst case of Selection Sort>
Best Case : O(n2)
Average Case : O(n2).
Worst Case : The worst case too is O(n2), even though the code inside the if statement will not get executed in this case. The quadratic complexity is due to the fact that the two for loops will execute completely in all the three cases irrespective of the content of the list.
>No. of comparisons : O(n2) in best/average/worst case
>No. of swaps : O(n) in average/worst case
& 0 in best case(When array is already sorted).
Explanation of complexity of Selection Sort in java>
The number of comparisons made in selection sort are same as made in Bubble sort:
Total number of comparisons in first pass=N-1 comparisons
Total number of comparisons in first pass=N-2 comparisons
Total number of comparisons in first pass=N-3 comparisons
and so on…
So we can calculate complexity by using following formula. The formula for the sum of such a
series is
(N–1) + (N–2) + (N–3) + ... + 1 = N*(N–1)/2
N*(N–1)/2 is 45 (10*9/2) when N is 10.
Thus, comparisons made by algorithm are about n2⁄2.
But number of swaps made are few(as compared to Bubble Sort)>
In case we have 10 elements- we may have to make 10 or even less than 10 swaps.
Therefore we can say that Selection sort runs in O(n2) time.
Undoubtedly, Selection Sort is far more better than Bubble sort.
Complexity of Selection Sort in graph >
Summary >
So in this data structure tutorial we learned diagram of Selection sort in java. Logic explanation of Selection Sort in java. Full Program/Example of Selection Sort in java >
Complexity of Selection Sort in java. Explanation of complexity of Selection Sort in java. Complexity of Selection Sort in graph.
Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.
RELATED LINKS>
1) Sorting in java
2) Searching in java
3) Advanced Sorting in java
4) More sorting types in java
5) Algorithms in java>