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;
}

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

    }

}

Technorati Tags: Insertion Sort,Sort,Algorithms,CLRS

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


       
    }


}