Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.2 kB
2
Indexable
Never
// C++ program for Merge Sort
#include <bits/stdc++.h>
#include <fstream>
#include <string>
using namespace std;

// file reading
void fileupload(int arr[], string filename, int len) {
  ifstream is(filename);
  int cnt = 0;
  int x;
  while (cnt < arr[len] && is >> x)
    arr[cnt++] = x;
  is.close();
}

void merge(int array[], int const left, int const mid, int const right) {
  int const subArrayOne = mid - left + 1;
  int const subArrayTwo = right - mid;

  auto *leftArray = new int[subArrayOne], *rightArray = new int[subArrayTwo];

  for (auto i = 0; i < subArrayOne; i++)
    leftArray[i] = array[left + i];
  for (auto j = 0; j < subArrayTwo; j++)
    rightArray[j] = array[mid + 1 + j];

  auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
  int indexOfMergedArray = left;

  while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
    if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
      array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
      indexOfSubArrayOne++;
    } else {
      array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
      indexOfSubArrayTwo++;
    }
    indexOfMergedArray++;
  }

  while (indexOfSubArrayOne < subArrayOne) {
    array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
    indexOfSubArrayOne++;
    indexOfMergedArray++;
  }

  while (indexOfSubArrayTwo < subArrayTwo) {
    array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
    indexOfSubArrayTwo++;
    indexOfMergedArray++;
  }
  delete[] leftArray;
  delete[] rightArray;
}

void mergeSort(int array[], int const begin, int const end) {
  if (begin >= end)
    return;

  int mid = begin + (end - begin) / 2;
  mergeSort(array, begin, mid);
  mergeSort(array, mid + 1, end);
  merge(array, begin, mid, end);
}

void printArray(int A[], int size) {
  for (int i = 0; i < size; i++)
    cout << A[i] << " ";
  cout << endl;
}

int main() {
  int len = 10000;
  int arr[10000];
  string filename = "data1.txt";
  fileupload(arr, filename, len);

  clock_t start, stop;
  double totalTime;
  start = clock();
  mergeSort(arr, 0, len - 1);
  stop = clock();
  totalTime = (stop - start) / (double)CLOCKS_PER_SEC;
  cout << "total time with -i :" << totalTime << endl;