Skip to content

Instantly share code, notes, and snippets.

@azat

azat/main.c

Forked from barrysteyn/main.c
Created March 30, 2013 16:27
Show Gist options
  • Save azat/5277336 to your computer and use it in GitHub Desktop.
Save azat/5277336 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
main.c
#include<iostream>
#include "mergesort.c"
using namespace std;
int main(int argc, char** argv) {
int num;
cout << "How many numbers do you want to sort: ";
cin >> num;
int a[num];
for (int i = 0; i < num; i++) {
cout << (i + 1) << ": ";
cin >> a[i];
}
// Start merge sort
mergeSort(a, num);
// Print the sorted array
cout << endl;
for (int i = 0; i < num; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
Raw
merge-sort-with-split-inversion-count.c
void merge(int *arr, int size1, int size2, int *inversions) {
int temp[size1+size2];
int ptr1=0, ptr2=0;
while (ptr1+ptr2 < size1+size2) {
if (ptr1 < size1 && arr[ptr1] <= arr[size1+ptr2] || ptr1 < size1 && ptr2 >= size2)
temp[ptr1+ptr2] = arr[ptr1++];
if (ptr2 < size2 && arr[size1+ptr2] < arr[ptr1] || ptr2 < size2 && ptr1 >= size1) {
temp[ptr1+ptr2] = arr[size1+ptr2++];
*inversions += size1-ptr1;
}
}
for (int i=0; i < size1+size2; i++)
arr[i] = temp[i];
}
void mergeSort(int *arr, int size, int* inversions) {
if (size == 1)
return;
int size1 = size/2, size2 = size-size1;
mergeSort(arr, size1, inversions);
mergeSort(arr+size1, size2, inversions);
merge(arr, size1, size2, inversions);
}
Raw
mergesort.c
void merge(int *arr, int size1, int size2) {
int temp[size1+size2];
int ptr1=0, ptr2=0;
while (ptr1+ptr2 < size1+size2) {
if (ptr1 < size1 && arr[ptr1] <= arr[size1+ptr2] || ptr1 < size1 && ptr2 >= size2)
temp[ptr1+ptr2] = arr[ptr1++];
if (ptr2 < size2 && arr[size1+ptr2] < arr[ptr1] || ptr2 < size2 && ptr1 >= size1)
temp[ptr1+ptr2] = arr[size1+ptr2++];
}
for (int i=0; i < size1+size2; i++)
arr[i] = temp[i];
}
void mergeSort(int *arr, int size) {
if (size == 1)
return;
int size1 = size/2, size2 = size-size1;
mergeSort(arr, size1);
mergeSort(arr+size1, size2);
merge(arr, size1, size2);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment