Sorting Magic – Selection Sort

Greetings my fellow sorcerers and sorceresses!

Selection sort magic is probably slightly better than bubble sort magic in certain cases but on this post I’d focus more on describing the mechanism of this magic than the analytic part.

Let’s take an example array,

3    10    5    2    1

Suppose that we want to sort this array in the increasing order. A way to achieve our target can be explained as follows.

  1. Traverse through the array one time and identify what is the maximum number. In  this case it is 10.
  2. Now swap that element with the last element of the list.

Now our array would look like this,

3    1    5    2    10

Now element 10’s position is fixed. Because it is the biggest element of the array it should come the last when sorted in the increasing order. Therefore, we can now think of our array as two sub arrays. One sorted and other unsorted. Sorted array has only one element, which is 10.

To distinguish the sorting part, I’ll place a comma between sorted and unsorted parts. Then the array would look like this,

3    1    5    2  ,  10

Now do the same for the unsorted part,

  1. Traverse through the unsorted part and find the maximum element, which is 5 in this case.
  2. Swap that element with the last element of the unsorted part.

Now the array would look something like this,

3    1    2  ,  5   10

Note that now the sorted part has two elements and unsorted part has less elements than the last time.

Follow the same procedure for the unsorted part again.

  1. Traverse through the unsorted part and find the maximum element, which is 3 in this case.
  2. Swap that element with the last element of the unsorted part.

Now our array looks like this,

2    1  ,  3    5   10

Now the unsorted part has only two elements and sorted part has grown even more.

Do the same drill again.

  1. Traverse through the unsorted part and find the maximum element, which is 2 in this case.
  2. Swap that element with the last element of the unsorted part.

Now the array looks like this,

1  ,  2    3    5   10

Now unsorted part has only one element. But since one element alone is considered sorted, we can extend the sorted part again. Finally our initial array would look like this,

1    2    3    5   10

Yaay!  You’ve successfully sorted the array in increasing order by using Selection Sort.

Selection sort is named that way cos you always ‘select’ the largest element and put it to the right place. If you want to sort the array in the decreasing order, you should pick the least element and put it as the first element of the array and keep on doing until there is no elements in the unsorted part.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s