Skip to content

Instantly share code, notes, and snippets.

@ajfg93
Last active December 25, 2018 04:07
Show Gist options
  • Save ajfg93/9b55b2f7b1de7f86ed7f9ac5c6c8a56a to your computer and use it in GitHub Desktop.
Save ajfg93/9b55b2f7b1de7f86ed7f9ac5c6c8a56a to your computer and use it in GitHub Desktop.
MergeSortArrayAccessCountTrial
#include <iostream>
#include <vector>
#include <random>
#include <cmath>
#include "mergesortTop.h"
#include "mergesortUp.h"
using namespace std;
random_device rd;
mt19937 e(rd());
uniform_int_distribution<int> dist(INT16_MIN, INT16_MAX);
int main(){
// cout << "i\t" << "access count\t" << "6NlgN" << endl;
for(int i = 1; i <= 512; i++){
vector<int> a(i);
vector<int> aux(i);
unsigned TopDownCnt = 0;
// unsigned BottomUpCnt = 0;
for(int j = 0; j < i ; j++){
a[j] = dist(e);
}
// MergeTopDown::sort(a, aux, TopDownCnt);
MergeBottomUp::sort(a, aux, TopDownCnt);
// cout << i << "\t"
// cout << TopDownCnt << "\t"
cout << static_cast<int>(6*i*log2(i))
<< endl;
}
return 0;
}
#pragma once
#include <vector>
#include <iostream>
class MergeTopDown{
public:
static void sort(std::vector<int> &a, std::vector<int> &aux, unsigned &count){
count = 0;
sort(a, aux, 0, a.size() - 1, count);
}
private:
static void sort(std::vector<int> &a, std::vector<int> &aux, int lo, int hi, unsigned &count){
if(hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid, count);
sort(a, aux, mid+1, hi, count);
merge(a, aux, lo, mid, hi, count);
}
static void merge(std::vector<int> &a, std::vector<int> &aux, int lo, int mid, int hi, unsigned &count){
int i = lo, j = mid+1;
for(int k = lo; k <= hi; k++){
aux[k] = a[k];
count += 2;
}
for(int k = lo; k <= hi; k++){
if(i > mid){
a[k] = aux[j++];
}else if (j > hi){
a[k] = aux[i++];
}else if(aux[i] < aux[j]){
a[k] = aux[i++];
count += 2;
}else{
a[k] = aux[j++];
count += 2;
}
count += 2;
}
}
};
#pragma once
#include <algorithm>
#include <vector>
class MergeBottomUp{
public:
static void sort(std::vector<int> &a, std::vector<int> &aux, int lo, int hi, unsigned &count){
if(hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid, count);
sort(a, aux, mid+1, hi, count);
merge(a, aux, lo, mid, hi, count);
}
static void sort(std::vector<int> &a, std::vector<int> &aux, unsigned &count){
int length = a.size();
for(int sz = 1; sz < length; sz = sz + sz){
for(int lo = 0; lo < length - sz; lo += sz + sz){
merge(a, aux, lo, lo + sz - 1, std::min(lo+sz+sz-1, length-1), count);
}
}
}
static void merge(std::vector<int> &a, std::vector<int> &aux, int lo, int mid, int hi, unsigned &count){
int i = lo, j = mid+1;
for(int k = lo; k <= hi; k++){
aux[k] = a[k];
count += 2;
}
for(int k = lo; k <= hi; k++){
if(i > mid){
a[k] = aux[j++];
}else if (j > hi){
a[k] = aux[i++];
}else if(aux[i] < aux[j]){
a[k] = aux[i++];
count += 2;
}else{
a[k] = aux[j++];
count += 2;
}
count += 2;
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment