Merge Sort and Selection Sort Algorithm For STL vectors in normal and template versions.

• Download source files - 7 Kb

Introduction

The merge sort algorithm and selection sort algorithm are implemented in C++ (both in normal and in template versions).

MergeSort A[1..n]

1. If the input sequence has only one element

– Return

2. Partition the input sequence into two halves

3. Sort the two subsequences using the same algorithm

4. Merge the two sorted subsequences to form the output sequence

Divide and Conquer

• It is an algorithmic design paradigm that contains the following steps

– Divide: Break the problem into smaller

sub-problems

– Recur: Solve each of the sub-problems

recursively

– Conquer: Combine the solutions of each of the sub-problems to form the solution of the problem

Merge Sort – O(N * Log N)

• Assume you are sorting 250,000,000 item

N = 250,000,000

N*Log N = 250,000,000 * 28

Assume you can do 1 operation/nanosecond

7.25 seconds

Merge Sort Analysis

MergeSort(A, left, right) T(n)

if (left < right)             O(1)

    mid := (left + right) / 2;         O(1)

   MergeSort(A, left, mid);         T(n/2)

   MergeSort(A, mid+1, right);         T(n/2)

   Merge(A, left, mid, right);         O(n)


Statement Work

T(n) = O(1) when n = 1,

2T(n/2) + O(n) when n > 1

T(n) = O(1) when n = 1,

2T(n/2) + O(n) when n > 1

Recurrence Equation

Please use the Code below

#include "stdafx.h"

#include "Sorting2.h"
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// The one and only application object

CWinApp theApp;
void SelectionSort(vector<int>& rData)
{
 int nLen = rData.size();
 if (nLen < 2)
  return;

for (int nIndex = 0; (nIndex < (nLen - 1)); nIndex++){

int nKey = rData[nIndex];
int nMatchingIndex = nIndex;
for (int nFindKey = (nIndex + 1); (nFindKey < nLen); nFindKey++){

   int& nData = rData[nFindKey];
   if (nData < nKey)
    nMatchingIndex = nFindKey, nKey = nData;
  }
  if (nMatchingIndex != nIndex)
   swap(rData[nIndex], rData[nMatchingIndex]);
 }
}

template<class _II>
void SelectionSort(_II _F, _II _L)
{
 if (_F == _L)
  return;

for (; (_F != _L); _F++){

_II _K = _F;
_II _X = _F; //Save the matching index...
_II _T = _F;
for (_II _FI = ++_T; (_FI != _L); _FI++){

   if (*_FI < *_K)
    _X = _K = _FI;
  }
  if (_F != _X)
   swap(*_F, *_X);
 }
}
/*
MergeSort(A, left, right)   T(n) 
BEGIN
if (left < right)     O(1)
 mid := (left + right) / 2;  O(1)
 MergeSort(A, left, mid);  T(n/2)
 MergeSort(A, mid+1, right);  T(n/2)
 Merge(A, left, mid, right);  O(n)
END
*/
void Merge(vector<int>& rData, int nLeft, int nMid, int nRight)
{
 //Left  = 0;
 //Mid   = 3;
 //Right = 7;
 int nLeftArrayLen  = (nMid - nLeft) + 1;
 int nRightArrayLen = (nRight - nMid);
 
 vector<int> LeftArray, RightArray;
 LeftArray.resize(nLeftArrayLen);
 RightArray.resize(nRightArrayLen);
 
 vector<int>::iterator itrFirst, itrLast;
 
 //Create the left sub array...
 itrFirst = rData.begin() + nLeft;
 itrLast  = itrFirst + nLeftArrayLen;
 copy(itrFirst, itrLast, LeftArray.begin());
 
 //Create the right sub array...
 itrFirst = rData.begin() + nMid + 1;
 itrLast  = itrFirst + nRightArrayLen;
 copy(itrFirst, itrLast, RightArray.begin());

 int nLIndex = 0;
 int nRIndex = 0;
 int nCopyIndex = nLeft;
 for (; (nCopyIndex <= nRight && 
  nLIndex < nLeftArrayLen && 
  nRIndex < nRightArrayLen);){
 
  if (LeftArray[nLIndex] <= RightArray[nRIndex])
   rData[nCopyIndex++] = LeftArray[nLIndex++];
  else
   rData[nCopyIndex++] = RightArray[nRIndex++];
 }
 //Copy the remaining elements from the left subarray to main array...
 while (nCopyIndex <= nRight && nLIndex < nLeftArrayLen)
  rData[nCopyIndex++] = LeftArray[nLIndex++];
 //Copy the remaining elements from the right subarray to main array...
 while (nCopyIndex <= nRight && nRightArrayLen)
  rData[nCopyIndex++] = RightArray[nRIndex++];
}

void MergeSort(vector<int>& rData, int nLeft, int nRight)
{
 if (nLeft < nRight){

  int nMid = ((nLeft + nRight) / 2);
  MergeSort(rData, nLeft, nMid);
  MergeSort(rData, nMid + 1, nRight);
  Merge(rData, nLeft, nMid, nRight);
 }
}

//This Temlate verion works only for "vectors" of any native and user defined data types
//that supports the <=, =(assign) operators.
//Template merge for vectors...
template<class _Type, class _II>
void Merge(_II _Left, _II _Mid, _II _Right)
{
 //Left  = 0;
 //Mid   = 3;
 //Right = 7;
 size_t nLeftArrayLen  = (_Mid - _Left) + 1;
 size_t nRightArrayLen = (_Right - _Mid);
 
 _Type LeftArray, RightArray;
 LeftArray.resize(nLeftArrayLen);
 RightArray.resize(nRightArrayLen);
 
 _II itrFirst, itrLast;
 
 //Create the left sub array...
 itrFirst = _Left;
 itrLast  = itrFirst + nLeftArrayLen;
 copy(itrFirst, itrLast, LeftArray.begin());
 
 //Create the right sub array...
 itrFirst = (_Mid + 1);
 itrLast  = itrFirst + nRightArrayLen;
 copy(itrFirst, itrLast, RightArray.begin());
 
 DWORD nLIndex = 0;
 DWORD nRIndex = 0;
 _II _CopyIndex = _Left;
 while (nLIndex < nLeftArrayLen && nRIndex < nRightArrayLen && _CopyIndex <= _Right){
  if (LeftArray[nLIndex] <= RightArray[nRIndex])
   *_CopyIndex++ = LeftArray[nLIndex++];
  else
   *_CopyIndex++ = RightArray[nRIndex++];
 }
 //Copy the remaining elements from the left subarray to main array...
 while (nLIndex < nLeftArrayLen && _CopyIndex <= _Right)
  *_CopyIndex++ = LeftArray[nLIndex++];
 //Copy the remaining elements from the right subarray to main array...
 while (nRIndex < nRightArrayLen && _CopyIndex <= _Right)
  *_CopyIndex++ = RightArray[nRIndex++];
}
//Template merge sort for vectors...
template<class _Type, class _II>
void MergeSort(_II _Left, _II _Right)
{
 if (_Left < _Right){
 
  _II _Mid = _Left + ((_Right - _Left) / 2);
  MergeSort<_Type>(_Left, _Mid);
  MergeSort<_Type>(_Mid + 1, _Right);
  Merge<_Type>(_Left, _Mid, _Right);
 }
}

using namespace std;
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
 int nRetCode = 0;
 
 // initialize MFC and print and error on failure
 if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
 {
  // TODO: change error code to suit your needs
  cerr << _T("Fatal Error: MFC initialization failed") << endl;
  nRetCode = 1;
 }
 else
 {
  // TODO: code your application's behavior here.
  CString strHello;
  strHello.LoadString(IDS_HELLO);
  cout << (LPCTSTR)strHello << endl;
 }

#define CONT_TYPE int
#define STL_VECTOR_TYPE vector<CONT_TYPE>

STL_VECTOR_TYPE Data;
typedef STL_VECTOR_TYPE::iterator itrCont;
srand(32);
Data.resize(9999);
/*
Data[0] = 5;
Data[1] = 2;
Data[2] = 6;
Data[3] = 7;
Data[4] = 4;
Data[5] = 3;
Data[6] = 2;
Data[7] = 1;
Data[8] = 1;
*/
generate(Data.begin(), Data.end(), rand);
random_shuffle(Data.begin(), Data.end());

copy(Data.begin(), Data.end(), ostream_iterator<CONT_TYPE>(cerr, " "));
cerr << "\n";

 time_t t1 = 0, t2 = 0;
 time(&t1);
 {
  //SelectionSort(Data);
  
  //Template version
  //SelectionSort(Data.begin(), Data.end());
  
  //MergeSort(Data, 0, Data.size() - 1);
  
  //Template version
  MergeSort<STL_VECTOR_TYPE>(Data.begin(), Data.end() -1);
 }
 time(&t2);
 time_t timediff = difftime(t2, t1);
 copy(Data.begin(), Data.end(), ostream_iterator<CONT_TYPE>(cerr, "\n"));
 
 cerr << "\n\n" << timediff << "\n";
 return nRetCode
}

References:

• Introduction to Computers and programming