Selection Sort | Running time O(n2) and Memory O(1)
This algorithm works as follows: find the smallest
(or largest) element using a linear scan and move it to the front. Then find
the next smallest (or next largest) element, and move it, and so on.
If we have to sort an array of n elements,
- This algorithm makes n-1 passes of the array
- In every pass, it finds (selects) the smallest (or
largest) element in the unsorted part of array, and moves it to the front.
Algorithm
//selection sort in descending order i.e. largest to
smallest
for ( i=0; i< n-1; i++ ) //i controls the number of passes
{ int
index=i;
/* Find the largest element
*/
for( j=i+1; j<n ; j++ )
{ if( a[j] > a[index]) //use < to change sort order
{ index = j;
}
}
/* Move
this element to the front (swapping) */
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
Example: We will sort an array in descending order
using selection sort.
Selection sort is the easiest sorting technique.
Also, since each pass requires a maximum of one swap, there will be a maximum
of n swaps during the sorting. Therefore, it is a better technique than bubble
sort. However, a time complexity of O(n2)
makes it an inefficient technique for large lists.
No comments:
Post a Comment