top of page
Caută
  • Poza scriitoruluioanaunciuleanu

Merge Sort Algorithm in C++


Merge Sort is a Divide and Conquer Algorithm. It continuously divides in 2 the array, and then each divided part and so on until we have all the values separated, and then starts grouping the values, and sorting them in small groups. This means that the problem is divided into small parts, and those small parts are solved and then merged.



// Merge Sort

#include <iostream>
using namespace std;

void mergeElements(int arrayOfNumbers[], int left, int middle, int right)
{
    int noElemLeftAray = middle - left + 1;
    int noElemRightAray =  right - middle;

    // Temporary arrays of halves
    int leftArray[noElemLeftAray], rightArray[noElemRightAray];

    // Copy the values in the 2 new arrays
    for (int i = 0; i < noElemLeftAray; i++)
    {
        leftArray[i] = arrayOfNumbers[left + i];
    }

    for (int j = 0; j < noElemRightAray; j++)
    {
        rightArray[j] = arrayOfNumbers[middle + 1 + j];
    }


    // Merge the arrays back
    int indexLeftSubArray = 0;
    int indexRightSubArray = 0;
    int indexMergedSubarray = left;
    while (indexLeftSubArray < noElemLeftAray && indexRightSubArray < noElemRightAray)
    {
        if (leftArray[indexLeftSubArray] <= rightArray[indexRightSubArray])
        {
            arrayOfNumbers[indexMergedSubarray] = leftArray[indexLeftSubArray];
            indexLeftSubArray++;
        }
        else
        {
            arrayOfNumbers[indexMergedSubarray] = rightArray[indexRightSubArray];
            indexRightSubArray++;
        }
        indexMergedSubarray++;
    }

    // Copy the remaining elements in the left array
    while (indexLeftSubArray < noElemLeftAray)
    {
        arrayOfNumbers[indexMergedSubarray] = leftArray[indexLeftSubArray];
        indexLeftSubArray++;
        indexMergedSubarray++;
    }

    // Copy the remaining elements in the right array
    while (indexRightSubArray < noElemRightAray)
    {
        arrayOfNumbers[indexMergedSubarray] = rightArray[indexRightSubArray];
        indexRightSubArray++;
        indexMergedSubarray++;
    }
}

void mergeSort(int arrayOfNumbers[], int left, int right)
{
    if (left < right)
    {
        int middle = left + (right - left) / 2;

        // Sort and merge the first and second halves
        mergeSort(arrayOfNumbers, left, middle);
        mergeSort(arrayOfNumbers, middle + 1, right);

        mergeElements(arrayOfNumbers, left, middle, right);
    }
}

void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
  for (int i = 0; i < numberOfElements; ++i)
  {
    cout << arrayOfNumbers[i] << " ";
  }
  cout << endl;
}

int main(void)
{
  int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
  int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
  int startIndex = 0;
  int lastIndex = numberOfElements - 1;

  mergeSort(arrayOfNumbers, startIndex, lastIndex);
  cout<<"The sorted array is: \n";
  printElementsOfArray(arrayOfNumbers, numberOfElements);
}

14 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no overlapping, in order to obtain the maximum profit. Solution: 1. static

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed vertically 2 x 1 or horizontally as 1 x 2. Solution: 1. static

bottom of page