jump to navigation

Selection Sort June 10, 2008

Posted by Thinker in Algorithms.
Tags: , ,
add a comment

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

The following is my implementation of the selection sort in C# programming language 🙂

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n – 1 elements of A.
using System;
using System.Collections.Generic;
using System.Text;

namespace Sorting
{
    class Sort
    {
        static void Main(string[] args)
        {
            List<Int32> nums = new List<int>();
            nums.Add(30);
            nums.Add(10);
            nums.Add(20);
            nums.Add(40);
            nums.Add(5);
            nums.Add(8);
            nums.Add(3);
            Sort sort = new Sort();
            //sort.DoInsertionSort(ref nums);
            sort.DoSelectionSort(ref nums);
           
            foreach(int i in nums)
            {
                Console.WriteLine(i);
            }
           
        }

        /// <summary>
        /// Selection sort algorithm involves primarily, traversing the list
        /// and then finding the least element in the array.
        /// Swapping that element with the first element of the array.
        /// We continue this process untill we hit the pen-ultimate element
        /// of the array.
        /// </summary>
        /// <param name=”numbersToBeSorted”></param>
        public void DoSelectionSort(ref List<Int32> numbersToBeSorted)
        {
            for (int index = 0; index < numbersToBeSorted.Count-1; index++)
            {
                int min = index;

                for (int secondSearch = index + 1; secondSearch < numbersToBeSorted.Count; secondSearch++)
                {
                    if (numbersToBeSorted[secondSearch] < numbersToBeSorted[min])
                    {
                        min = secondSearch;
                    }
                }
                //simple swapping of the least element with appropriate
                //key element.
                int temp = numbersToBeSorted[index];
                numbersToBeSorted[index] = numbersToBeSorted[min];
                numbersToBeSorted[min] = temp;

            }
        }
}

 /*
         *
         *  Out put would be:
            3
            5
            8
            10
            20
            30
            40
            Press any key to continue . . .
         */