Tuesday, August 12, 2008

Find Nth Largest number in an Array

The below is my implementation of finding the nth largest(whichmax)number in the given array of integers.

This would work for both positive and negative integers. This also  affects the given array by manipulating the values of the source array. Hence if you want an non-manipulative algo, this is NOT the one.

#include "stdafx.h"

class Program
{
public:
int GetNthLargestOptimized(int **intArray,int Length, int whichMax);
};


int Program::GetNthLargestOptimized(int **intArray,int Length, int whichMax)
{

int MaxIndex =0;
int MinIndex =0;
bool minFound = false;

for(int nth=0;nth<whichMax;nth++)
{
for(int index=0;index<Length;index++)
{
if((*intArray)[MaxIndex]< (*intArray)[index])
{

MaxIndex = index;
}
if(!minFound && (*intArray)[MinIndex] > (*intArray)[index])
{

MinIndex = index;
}

}

if(!minFound)
{
minFound = true;
}



if( nth != whichMax -1)
{
(*intArray)[MaxIndex]= (*intArray)[MinIndex];

}

}

return (*intArray)[MaxIndex];

}



int _tmain(int argc, _TCHAR* argv[])
{
Program m;
int intNegativeArray[10]={-1,-2,-3,-4,-5,-6,-7,-8,-9,-10};
int intArray[10]={23,345,345,12,45,23,34,4,6,555};

int *intNegativePtr = intNegativeArray;
printf("4th Largest in Negative array:%d\n",m.GetNthLargestOptimized(&intNegativePtr,10,4));

int *intPtr = intArray;
printf("4th Largest in Positive array:%d\n",m.GetNthLargestOptimized(&intPtr,10,4));

return 0;
}

Thursday, June 19, 2008

FireFox 3.0 and WordPress Just wont Work?

 

Firefox30 I am not able to login to my Wordpress login through Firefox, dont know what fire fox doesn't like about the Wordpress.I recently upgraded the Firefox to 3.0 version from where this problem started :)

Am I All alone or is any one with me?

 

Technorati Tags: ,

Tuesday, June 17, 2008

How to Stop Forced Reboot of Windows Vista After Software Updates

NoForcedReboot Sometimes it would be very frustrating to see our machine rebooted due to software updates. There would be instances when we would have started a long process to start and would have aborted abruptly due to the software updates from the Vista. I found a nice article from How To Geek where he has explained the above process to disable Vista from forcibly rebooting the machine. All we need to do is this:

Open up regedit.exe through the start menu search box or run dialog, and navigate down to the following key, creating new keys if they don't exist.

HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows\WindowsUpdate\AU

Create a new 32-bit DWORD value named NoAutoRebootWithLoggedOnUsers and give it a value of 1 to prevent automatic reboot while users are logged on. Delete the value to put things back to the way they were.

Technorati Tags: ,,,

Zoomii

zoomi

Zoomi, this  one really caught my attention. This is what technology would do as it matures. The shopping experiences would soon become to mature from a 2D to a 3D experience.

This web is a book store who get the books catalogue from Amazon and presents it in a 3D format for a pleasant experience of the user. The user would use the Amazon payment gateway for the payments. Zoomii does not even store the shipping information or any other information about the user except his email address; I guess this one is going to be a sure hit :)

Technorati Tags: ,,

Claiming my blog with Technorati.

I have just signed up with Technorati and the setup process wants me to include the following Technorati Profile Here so that it can crawl and confirm my ownership of this blog :) Lets see how the spiders do the crawling.

Monday, June 16, 2008

Insertion Sort

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 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);
            foreach(int i in nums)
            {
                Console.WriteLine(i);
            }
        }

/// <summary>
        /// This is the function that does the insertion sort
        ///
        /// </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 . . .
         */

    }

}

Express the function n3/1000 - 100n2 - 100n + 3 in terms of Θ-notation.

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.

Selection sort

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



}


}

Saturday, June 14, 2008

Sphenic Number
In Mathematics Sphenic number is a postive integer which is a product of three distinct prime numbers.
All sphenic numbers have exactly eight divisors. If we express the sphenic number as n=p.q.r, where p, q, and r are distinct primes, then the set of divisors of n will be: {1,p,q,r,pq,pr,qr, n}.
Refer to Sphenic Number in Wiki for more details.