Selection Sort

Selection Sort

Selection sort algorithm is an easy-to-program, but very inefficient sorting algorithm.

[ad code=1]

[ad code=1]

Algorithm

1. 1st iteration selects the smallest element in the array, and swaps it with the first element.
2. 2nd iteration selects the 2nd smallest element (which is the smallest element of the remaining elements) and swaps it with the 2nd element.
3. The algorithm continues until the last iteration selects the 2nd largest element and swaps it with the 2nd last index, leaving the largest element in the last index.

[ad code=1]

[ad code=1]

Block Diagram

[ad code=1]

[ad code=1]

Codes

[ad code=1]
[ad code=1]

Perl

#!/apps/perl/bin/perl -w

&main();

sub main
{
   my @array = (1,7,4,9,4,7,2,3,0,8);

   print "Before Sort:-\n";
   print "@array\n";

   &selectionSort(\@array,);

   print "After Sort:-\n";
   print "@array\n";
} # main

sub selectionSort
{
   my $aref = shift(@_);

   for (my $x=0; $x<@$aref-1; $x++)
   {
      my $smallestIndex = $x;
      for (my $y=$x+1; $y<@$aref; $y++)
      {
         if ( $aref->[$y] < $aref->[$smallestIndex] )
         {
            $smallestIndex = $y;
         }
      } # for $y
      &swap( \$aref->[$x], \$aref->[$smallestIndex] );
   } # for $x
} # selectionSort

sub swap
{
   my ($x, $y) = @_;
   my $tmp = $$x;
   $$x = $$y;
   $$y = $tmp;
} # swap

[ad code=1]
[ad code=1]

Python

#!/swdev/tools/python/2.5.1/linux32/bin/python -d

def main():
   array = [1, 7, 4, 9, 4, 7, 2, 3, 0, 8]
   print("Before sort:-")
   print(array)
   selectionSort(array)
   print("After sort:-")
   print(array)

def selectionSort(array):
   for x in range(0, len(array)-1):
      smallestIndex = x

      for y in range(x+1, len(array)):
         if array[y] < array[smallestIndex]:
            smallestIndex = y

      ### Swap
      array[x], array[smallestIndex] = array[smallestIndex], array[x]

main()

[ad code=1]
[ad code=1]

c++

#include <iostream>
using namespace std;

// prototype
void selectionSort(int * const, const int);
void swap(int * const, int * const);
void printArray(const int * const, const int);

int main()
{
   int size = 10;
   int array[] = {1,7,4,9,4,7,2,3,0,8};

   cout << "Before sort:-" << endl;
   printArray(array, size);

   selectionSort(array, size);

   cout << "After sort:-" << endl;
   printArray(array, size);
} // main

void selectionSort(int * const ap, const int size)
{
   int smallestIndex;
   for (int x=0; x<size-1; x++)
   {
      smallestIndex = x;
      for (int y=x+1; y<size; y++)
      {
         if ( ap[y] < ap[smallestIndex] )
            smallestIndex = y;
      } // for y
      swap( &ap[x], &ap[smallestIndex] );
   } // for x
} // selectionSort

void swap(int * const x, int * const y)
{
   int tmp;
   tmp = *x;
   *x = *y;
   *y = tmp;
} // swap

void printArray( const int * const array, const int size)
{
   for (int i=0; i<size; i++)
   {
      cout << array[i] << " ";
   } // for
   cout << endl;
} // printArray

[ad code=1]

[ad code=1]

Recommended Reading

Didn't find what you are looking for?