Sorting rearranges the elements in a list into either ascending or descending order. (we’ll use ascending order.) In this article, we’ll explain the working of Selection sort. Selection Sort divides the array into two parts:  already sorted, and not yet sorted.  On each pass, it finds the smallest of the unsorted elements, and swaps it into its correct place, thereby increasing the number of sorted elements by one. Selection sort has simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Selection Sort Example

Selection Sort: Pass One

Selection Sort: Pass Two

Selection Sort: Pass Three

Selection Sort: Pass Four

Selection Sort: How many comparisons?

The number of comparisons when the array contains N elements is

Sum = (N-1)  +   (N-2)  + .  .  .  +  2  +  1

Although, the number of comparisons are same as bubble sort, however, number of swaps are decreased. Total No. of swaps in Selection sort are:  (N -1) , where N = size of array.

Selection sort implementation in C++

void selectionSort(int arr[], int size)
	for (int i=0; i < size; i++)
		int min = i;
		for (int j=i+1; j < size; j++)
		     if(arr[j] < arr[min] )
			min = j;

		if (min != i)
		     int temp = arr[i];
		     arr[i] = arr[min];
		     arr[min] = temp;
Tagged with: C/C++ languageData structures

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.