Selection
Sort Algorithm
The
selection sort is making a pass through all the elements and selecting,
the shortest one. This shortest element is then swapped with the element on the
left end of the line, at position 0. Now the leftmost element is sorted and won’t
need to be moved again. The sorted elements accumulate on the left (lower
indices), whereas in the bubble sort they accumulated on the right.
The
next time we pass down the row of elements, we start at position 1, and,
finding
the
minimum, swap with position 1. This process continues until all the elements
are
sorted.
If there are n elements to be sorted then, the
process mentioned above should be repeated n-1 times to get required result.
Working of selection sort algorithm.
Sort
Algorithm
public void selectionSort()
{
int out, in, min;
for(out=0; out<nElems-1; out++) // outer loop
{
min = out; // minimum
for(in=out+1; in<nElems; in++) // inner loop
if(a[in] < a[min] ) // if min greater,
min = in; // we have a new min
swap(out, min); // swap them
} // end for(out)
} // end selectionSort()
The
outer loop, with loop variable out, starts at the beginning of the array (index
0)
and
proceeds toward higher indices. The inner loop, with loop variable in, begins
at
out
and likewise proceeds to the right.
At
each new position of in, the elements a[in] and a[min] are compared. If a[in] is
smaller,
then min is given the value of in. At the end of the inner loop, min points to
the
minimum value, and the array elements pointed to by out and min are swapped.
Efficiency
of the Selection Sort
The
selection sort performs N*(N-1)/2 number
of comparisons. For large values of N, the comparison times for the selection is O(N2) time, it is faster because
there are so few swaps. For smaller
values of N, the selection sort may in fact be considerably faster, especially
if the swap times are much larger than the comparison times.
No comments:
Post a Comment