Thread: multiple values in #define(?) & counter placement

Newbie needing help -- I am writing a program to implement sorting alogrithms and think what I have is correct (feel free to double check me!). Where I am have problems is as part of the assignment the random input needs to be of sizes 300, 900, 1200, 2400, 6000, 9000, & 9900. I am currently using #define for the size of 300-- can I use the #define for multiple values? If so, what syntax for it? If not I am lost on what I need to do. Any suggestions? Also, to do an performance analysis on each algorithm I must implement a simple counter to increment by 1 unit in every iteration & measure the time taken by each algoritm. Can anyone help me on where to place the counters??
Any assistance/suggestions would be appreciated. Thanks!

Code:

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

#define NUM_ITEMS 300

void insertionSort(int numbers[], int array_size);
void heapSort(int numbers[], int array_size);
void siftDown(int numbers[], int root, int bottom);
void quickSort(int numbers[], int array_size);
void q_sort(int numbers[], int left, int right);
void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);

int temp[NUM_ITEMS];
int numbers[NUM_ITEMS];


int main()
{
  int i;

  //seed random number generator
  srand(getpid());

  //fill array with random integers
  for (i = 0; i < NUM_ITEMS; i++)
    numbers[i] = 1000 + rand()%24000;

  //perform insertion sort on array
  insertionSort(numbers, NUM_ITEMS);

  printf("Done with insertion sort.\n");

  heapSort(numbers, NUM_ITEMS);

  printf("Done with heap sort.\n");

  //perform quick sort on array
  quickSort(numbers, NUM_ITEMS);

  printf("Done with quick sort.\n");

//perform merge sort on array
  mergeSort(numbers, temp, NUM_ITEMS);

  printf("Done with merge sort.\n");


   for (i = 0; i < NUM_ITEMS; i++)
    printf("%i\n", numbers[i]);
  

}


void insertionSort(int numbers[], int array_size)
{
  int i, j, index, counter;
  counter = 0;
 
  for (i=1; i < array_size; i++)
  {
    index = numbers[i];
    j = i;
    while ((j > 0) && (numbers[j-1] > index))
    {
	  counter++;
      numbers[j] = numbers[j-1];
      j = j - 1;
    }
    numbers[j] = index;
	
  }
printf("insertion sort counter= %i \n",counter);
}



void heapSort(int numbers[], int array_size)
{
  int i, temp;
  for (i = (array_size / 2)-1; i >= 0; i--)
    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)
  {
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(numbers, 0, i-1);
  }
}


void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;
    
  done = 0;
  while ((root*2 <= bottom) && (!done))
  { 

    if (root*2 == bottom)
      maxChild = root * 2;
    else if (numbers[root * 2] > numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])
    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }

}


void quickSort(int numbers[], int array_size)
{ 
  q_sort(numbers, 0, array_size - 1);

}



void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;
  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
 
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    { 
      numbers[right] = numbers[left];
      right--;
    }
 
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
  
 
}



void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}



void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;

  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);

    merge(numbers, temp, left, mid+1, right);
  }
}


void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }

  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }

  for (i=0; i <= num_elements; i++)
  {
    numbers[right] = temp[right];
    right = right - 1;
  }
}

Code:

int temp[NUM_ITEMS];
int numbers[NUM_ITEMS];


int main()
{
  int i;

  //seed random number generator
  srand(getpid());

  //fill array with random integers
  for (i = 0; i < NUM_ITEMS; i++)
    numbers[i] = 1000 + rand()%24000;

  //perform insertion sort on array
  insertionSort(numbers, NUM_ITEMS);

  printf("Done with insertion sort.\n");

  heapSort(numbers, NUM_ITEMS);

  printf("Done with heap sort.\n");

  //perform quick sort on array
  quickSort(numbers, NUM_ITEMS);

  printf("Done with quick sort.\n");

//perform merge sort on array
  mergeSort(numbers, temp, NUM_ITEMS);

  printf("Done with merge sort.\n");


   for (i = 0; i < NUM_ITEMS; i++)
    printf("%i\n", numbers[i]);
  

}

Look in to dynamic array allocation. Also look in to taking the code that you have used with the NUM_ITEMS variable and replacing NUM_ITEMS with an actual variable, such as:

Code:

int num_items;

Which you could either set via user input or use a nifty array trick:

Code:

int testSizes[] = {300, 900, 1200 };
for(int a=0;a<sizeof(testSizes)/sizeof(int);a++)
{
  int num_items = testSizes[a];
// .. All code from main goes here, replacing NUM_ITEMS with num_items
}

> Newbie needing help -- I am writing a program to implement sorting alogrithms and think what I have is correct (feel free to double check me!). Where I am have problems is as part of the assignment the random input needs to be of sizes 300, 900, 1200, 2400, 6000, 9000, & 9900.

Those are too small values ( like 9900).

I used the function time. To measure the time for every alogrithm.

Notice, After the first alogrithm the array is already sorted !!! so
it will work much faster than unsorted array.

Here are some of my results ( I tried "insertionSort" with
unsorted and sorted array ) :

Number of items 50000
Done with "heap" sort.Time 0[sec]
Done with "quick" sort.Time 0[sec]
Done with "merge" sort.Time 0[sec]
Done with "insertion not sorted" sort.Time 8[sec]
Done with "insertion already sorted" sort.Time 0[sec]



Number of items 80000
Done with "heap" sort.Time 0[sec]
Done with "quick" sort.Time 0[sec]
Done with "merge" sort.Time 0[sec]
Done with "insertion not sorted" sort.Time 22[sec]
Done with "insertion already sorted" sort.Time 0[sec]




Here are some of my results ( with out "insertion" sort) :



Number of items 3500000
Done with "heap" sort.Time 10[sec]
Done with "quick" sort.Time 2[sec]
Done with "merge" sort.Time 3[sec]
Done with "insertion already sorted" sort.Time 0[sec]


Which gives you an idea which one is faster.