Tag Archives: Algorithms

C++ Templated QuickSort Algorithm

It has been over a month since I posted. I’ve been really busy with all of my classes.

So, instead of going too in depth with anything, I’m just going to share some code we’ve written. This is a QuickSort Algorithm that we adapted from the MIT Intro to Algorithms book. We just finished it last night (less than 12 hours ago), so it’s not fully tested.

#ifndef _QUICKSORT_H
#define _QUICKSORT_H
#include <vector>
using namespace std;

namespace QuickSort
{
/* 
    QuickSort Algorithm using Templates

    Algorithm was adapted from:
        Introduction to Algorithms
        By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
        Contributor Thomas H. Cormen
        Edition: 2, illustrated
        Published by MIT Press, 2001
        ISBN 0262032937, 9780262032933
        1180 pages
    Accessed March 2009
    via http://books.google.com/books?id=NLngYyWFl_YC
    See pages 145-147

*/
    template<class T>
    class QuickSort
    {
    public:
        vector<T> *sortingArray;
        int left;
        int right;
 
        // Constructors
        QuickSort();
        QuickSort(vector<T> *sortArray);
        QuickSort(vector<T> *sortArray, int startIndex, int endIndex);
 
        /**********************************************************************
        * Partition and Swap Functions
        **********************************************************************/
        int Partition(vector<T> *sortArray, int startIndex, int endIndex);
        void Swap(int l, int k);
 
    };
 
    template<class T>
    QuickSort<T>::QuickSort()
    {
        sortingArray = new vector<T>();
        left = 0;
        right = 0;
    }
 
    template<class T>
    QuickSort<T>::QuickSort(vector<T> *sortArray)
    {
        int startIndex = 0;
        int endIndex = 0;
 
        endIndex = (int)(*sortArray).size() - 1;
 
        QuickSort(sortArray, startIndex, endIndex);
    }
 
    template<class T>
    QuickSort<T>::QuickSort(vector<T> *sortArray, int startIndex, int endIndex)
    {
        if(startIndex >= endIndex)
        {
            return;
        }
 
        // *initialize* the array
        sortingArray = sortArray;
 
        // For instance: 1..n
        left = startIndex;
        right = endIndex;
 
        if(left < right)
        {
            // get pivot
            int pivot = Partition(sortingArray, left, right);
 
            // sort left side
            QuickSort(sortingArray, left, (pivot-1));
 
            // sort right side
            QuickSort(sortingArray, (pivot+1), right);
        }
    }
 
    template<class T>
    int QuickSort<T>::Partition(vector<T> *sortArray, int startIndex, int endIndex)
    {        
        // initially this start - 1 when startIndex is 0.
        int l = startIndex - 1;
         int k = endIndex;
  
         for(int i = startIndex; i <= k - 1; i++)
         {
             // Go until you find a value smaller than the last value.
             if((*sortArray)[i] <= (*sortArray)[k])
             {
                 // increment l
                 l++;
  
                 // swap i and j
                 // NOTE: this is supposed to swap j with itself the first time.
                 Swap(l, i);        
             }
         }    
         
         // when loop is finished, swap 
         Swap(l + 1, k);
  
         return l + 1;
     }
  
     template<class T>
     void QuickSort<T>::Swap(int l, int k)
     {
         // create temp variable
         T tmp;
         
         // store first element in temp
         tmp =(*sortingArray)[l];
  
         // swap second element to first element
         (*sortingArray)[l] = (*sortingArray)[k];
  
         // put temp variable in second element
         (*sortingArray)[k] = tmp;
     }
  
 }
  
 #endif
 

Flattr this!

C# Insertion Sorting algorithm

Here is a console application to test an Insertion Sorting algorithm adapted from chapter 2 of MIT’s Introduction to Algorithms. I thought this might come in handy for any beginners, as well as a fun way to test your computer’s performance.

My desktop averages about 24.9 seconds, which, of course, depends on how scattered the integers are in the array.

 using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
  
 namespace InsertionSorting
 {
     class Program
     {
          static void Main(string[] args)
          {
              // int[] A = {5, 2, 4, 6, 1, 3};
              int initializer = 100000;
              int[] A = new int[initializer];
   
              for (int c = 0; c < A.Length; c++)
              {
                  A = c;
              }
   
              // Random shuffle
              Random rand = new Random();
              for (int d = 0; d < A.Length; d++)
              {
                  int firstInt = A[d];
                  int swapIndex = rand.Next(initializer);
                  int secondInt = A[swapIndex];
   
                  A[d] = secondInt;
                  A[swapIndex] = firstInt;
              }
              
              //Console.Write("Array before sorting: ");
              //foreach (int number in A)
              //{
              //    Console.Write("{0} ", number);
              //}
              //Console.WriteLine("");
   
              int key;
              int i;
              int j;
   
              Console.Write("Insertion Sorting array of {0} numbers, please wait...", initializer);
              
              DateTime start = DateTime.Now;
              for (j = 1; j < A.Length; j++)
              {
                  key = A[j];
                  i = j;
   
                  while (i > 0 && A[i - 1] > key)
                  {                    
                      A[i] = A[i-1];
                      i--;
                  };
                  
                  A[i] = key;
              }
              DateTime finish = DateTime.Now;
              
              //Console.Write("Array after sorting: ");
              //foreach (int number in A)
              //{
              //    Console.Write("{0} ", number);
              //}
   
              Console.WriteLine("");
              Console.WriteLine("Duration: {0} seconds", (finish - start).ToString());
          }
      }
  }

Flattr this!

C# Insertion Sorting alrgorithm.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace InsertionSorting
{
    class Program
    {
         static void Main(string[] args)
         {
             // int[] A = {5, 2, 4, 6, 1, 3};
             int initializer = 100000;
             int[] A = new int[initializer];
  
             for (int my = 0; my < A.Length; my++)
             {
                 A[my] = my;
             }
  
             // Random shuffle
             Random rand = new Random();
             for (int k = 0; k < A.Length; k++)
             {
                 int firstInt = A[k];
                 int swapIndex = rand.Next(initializer);
                 int secondInt = A[swapIndex];
  
                 A[k] = secondInt;
                 A[swapIndex] = firstInt;
             }
             
             //Console.Write("Array before sorting: ");
             //foreach (int number in A)
             //{
             //    Console.Write("{0} ", number);
             //}
             //Console.WriteLine("");
  
             int index;
             int j;
             int i;
  
             Console.Write("Insertion Sorting array of {0} numbers, please wait...", initializer);
             
             DateTime start = DateTime.Now;
             for (i = 1; i < A.Length; i++)
             {
                 index = A[i];
                 j = i;
  
                 while (j > 0 && A[j - 1] > index)
                 {                    
                     A[j] = A[j-1];
                     j--;
                 };
                 
                 A[j] = index;
             }
             DateTime finish = DateTime.Now;
             
             //Console.Write("Array after sorting: ");
             //foreach (int number in A)
             //{
             //    Console.Write("{0} ", number);
             //}
  
             Console.WriteLine("");
             Console.WriteLine("Duration: {0} seconds", (finish - start).ToString());
         }
     }
 }

Flattr this!