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






1.92/5 (4 votes)
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: