Wednesday, June 2, 2010

Merge sort

How it Works;
1) divide the list in half
2) perform mergesort on the left and right parts
3) merge the left and right parts back in order

Properties;
Best, Average and Worst case speed is O(nlog(n)).
Memory is n
It is Stable

//compile with g++
#include <iostream>
#include <iomanip>
using namespace std;

void mergeSort(int* data, int* buffer, int size)
{
  if(size < 2)
    return;

  int mid       = size/2;

  mergeSort(data,       buffer, mid);
  mergeSort(&data[mid], buffer, size - mid);

  int left      = 0;
  int right     = mid;
  int out       = 0;
  while(
 (left  != mid ) &&
 (right != size)
 )
    {
      if(data[right] < data[left]) { buffer[out++] = data[right++]; }
      else                         { buffer[out++] = data[left++];  }
    }

  while(left  != mid  ) { buffer[out++] = data[left++];  }
  while(right != size ) { buffer[out++] = data[right++]; }

  //transfer the buffer back to the main... small size sort so its better then doing mallocs all over the place
  out = 0;
  while(out != size ) { data[out] = buffer[out]; out++; }
}

//test
#define SIZE 20
#define SCRAMBLE(x, y) ((0xa57b & ~y) + ((0x3829 & x) << 1))

bool check(int data[], int size)
{
  for(int i = 1; i < size; i++)
    if(data[i] < data[i-1])
      {
        cout << "FAIL!" << endl;
        return false;
      }
  cout << "PASS" << endl;
  return true;
}

void print(int data[], int size)
{
  for(int i = 0; i < size; i++)
    cout << setw(5) << data[i] << " ";
  cout << endl;
}

bool test(int* data, int* buffer, int size)
{
  print(data, SIZE);
  mergeSort(data, buffer, SIZE);
  print(data, SIZE);
  return check(data, SIZE);
}

int main()
{
  int data[SIZE];
  int buffer[SIZE];
  bool pass = true;

  //easy data
  data[0] = 1;
  for(int i = 0; i < SIZE; i++)
    data[i] = SIZE - i;
  pass &= test(data, buffer, SIZE);

  //semi repeated data
  data[0] = 1;
  for(int i = 1; i < SIZE; i++)
    data[i] = SCRAMBLE(i, data[i-1]);
  pass &= test(data, buffer, SIZE);

  //the sort killer!
  for(int i = 0; i < SIZE; i++)
    data[i] = 5;
  pass &= test(data, buffer, SIZE);

  //and some randoms to catch anything i missed
  srand ( time(NULL) );

  for(int j = 0; j < 100; j++)
    {
      for(int i = 0; i < SIZE; i++)
        data[i] = (int)((float)(j+1)*((float)rand()/(float)RAND_MAX));
      pass &= test(data, buffer, SIZE);
    }

  if(pass)
    cout << "ALL PASSED" << endl;
  else
    cout << "FAILED" << endl;
}

No comments:

Post a Comment