/***************************************************************************
 *  Columbia University Introduction to Computer Programming in C COMS 1003
 *  Sorting routines
 *
 *  Copyright (C) 2005 Michael E. Locasto
 *
 *  All rights reserved.
 *
 * $Id: sorts.c,v 1.2 2005/11/17 23:24:18 locasto Exp $
 **************************************************************************/

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

/**
 * Three other better sorts are quicksort, heapsort, mergesort
 * These are recursive sorting routines with complexity n lg n
 * and are known as 'divide and conquer' algorithms 
 */


void        swap(int*, int*);

void        selection_sort(int [], int);

void        bucket_sort(int [], int);

void        bubble_sort(int [], int);

void swap(int *x, int *y)
{
   int temp = *x;
   *x = *y;
   *y = temp;
}

void bubble_sort(int data[], int length)
{
  int i = 0;
  int j = 0;

  for(i=length-1;i>=0;i--)
  {
     for(j=1;j<=i;j++)
     {
        if(data[j-1]<data[j])
        {
           swap(&data[j-1], &data[j]);
        }
     }
  }
}

void selection_sort(int data[], int length)
{
   int i = 0;
   int j = 0;
   int max = 0;

   for(i=0;i<length-1;i++)
   {
      max = i;
      for(j=i+1;j<length;j++)
      {
         if(data[j]>data[max])
         {
            max = j;
         }
         //swap(&data[i], &data[max]);
      }
      swap(&data[i], &data[max]);
   }
}

void bucket_sort(int data[], int length)
{
   int i = 0;
   int j = 0;

   for(i=0;i<length;i++)
   {
      for(j=i+1;j<length;j++)
      {
         if(data[i]<data[j])
         {
            swap(&data[i], &data[j]);
         }
      }
   }
}

void fill(int data[], int length)
{
   int i = 0;
   srand(time(NULL));
   for(i=0;i<length;i++)
   {
      data[i]=rand()%100;
   }
}

void print(int data[], int length)
{
   int i = 0;
   for(i=0;i<length;i++)
   {
      printf("data[%2d] = %3d\n",i, data[i]);
   }
}

/**
 * 
 *
 * 
 */
int main(int argc, char* argv[])
{
   int data[25];
   int i = 0;

   //fill(data,25);
   srand(time(NULL));
   for(i=0;i<25;i++)
   {
      data[i]=rand()%100;
   }

   print(data,25);

   //bucket_sort(data, 25);
   selection_sort(data, 25);
   //bubble_sort(data, 25);

   print(data,25);


   return 0;
}