Click here to Skip to main content
12,999,417 members (45,040 online)
Click here to Skip to main content
Add your own
alternative version

Stats

27.6K views
187 downloads
8 bookmarked
Posted 9 Jun 2006

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

Rate this:
Please Sign up or sign in to vote.
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

Please use the Code below


// 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;
  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:

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

sundareswaran.senthilvel
Technical Lead
India India
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

You may also be interested in...

Comments and Discussions

 
-- There are no messages in this forum --
Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170624.1 | Last Updated 9 Jun 2006
Article Copyright 2006 by sundareswaran.senthilvel
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid