13,403,102 members (52,484 online)
Article
alternative version

#### Stats

28.6K views
8 bookmarked
Posted 9 Jun 2006

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

Merge Sort

## 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

// Sorting2.cpp : Defines the entry point for the console application.
//
`#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;
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:

## Share

I'm Sundareswaran Senthilvel from India
Interested in the following...

C++11,
C++/CX
C++ AMP
Concurrency
Graphics Programming
Artificial Intelligence
Machine Learning
Data Mining