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 . . .
         */

Advertisements

Express the function n3/1000 – 100n2 – 100n + 3 in terms of Θ-notation. June 10, 2008

Posted by Thinker in Algorithms.
Tags: ,
3 comments

I guess the answer is Θ(n^3). We always mention the highest order of the equation and we ignore the constants associated with the equation.

Insertion Sort June 10, 2008

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

I wanted to write on Algorithms for a long time and here i got a chance to write on them; Today I am going to post on Insertion sort.

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort

While implementing the insertion sort, we would try to main the following rules:

1. While we begin sorting we would sort from the second array position.
2. We keep traversing the array and take the next element in the array and position it such that it is in the sorted order.
 
The implementation of the insertion sort in C# language is as follows:

using System;
using System.Collections.Generic;
using System.Text;

namespace Sorting
{
    class InsertionSort
    {
        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);
            InsertionSort sort = new InsertionSort();
            sort.DoInsertionSort(ref nums);
           
            foreach(int i in nums)
            {
                Console.WriteLine(i);
            }
           
        }
        /// <summary>
        ///
        /// </summary>
        /// <param name=”numbersToBeSorted”>
        /// The array of integers which needs to be sorted.
        /// </param>
        public void DoInsertionSort(ref List<Int32> numbersToBeSorted)
        {
            for (int j = 1; j < numbersToBeSorted.Count; j++)
            {
                //The key is the one which we would compare with each of
                //the element and insert it appropriately.
                int key = numbersToBeSorted[j];

                //We just need to compare it with the previous element.         
                int i = j – 1;
                //THE AWESOME TRICK:
                // Since our state is we would always have the previous
                //elements in sorted order, we would just traverse back
                //and insert the key where the its most appropriate.
                while (i > -1 && numbersToBeSorted[i] > key)
                {
                    numbersToBeSorted[i + 1] = numbersToBeSorted[i];
                    i = i – 1;
                }
                numbersToBeSorted[i + 1] = key;
            }
        }

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

    }
}

 

Rabin-Karp string search algorithm – Wikipedia, the free encyclopedia March 5, 2008

Posted by Thinker in Algorithms, Technical.
1 comment so far

Rabin-Karp string search algorithm – Wikipedia, the free encyclopedia

I was looking at the Rabin-Karp string search algorithm. How simple he has solved the time complexity of this problem. I really like this solution. Hashing helps us in so many ways:) Long live algos.