List mergeSort (C)

We are based on the list found here. About merge sort, we were based here, but we implemented a more efficient algorithm for sortList.c.

sortList.c

#include <stdlib.h>
#include <string.h>
#include "list.h"
/* min function */
#include "minMax.h"

void bottomUpMerge(Listptr* , int , int , int , Listptr*);
/* We won't use this approach */
void copyList(Listptr *, Listptr *, const int);

#define strLength 15

/* List listToSort has the items to sort; List workerList is a work list */
Listptr bottomUpSort(Listptr listToSort, Listptr workerList,const int n)
{
  int width;
 
  /* Each 1-element run in listToSort is already "sorted". */
 
  /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole listToSort is sorted. */
  for(width = 1; width < n; width = 2 * width)
  {
      int i;
 
      /* listToSort is full of runs of length width. */
      for(i = 0; i < n; i = i + 2 * width)
      {
          /* Imagine the lists as arrays : */
          /* Merge two runs: listToSort[i:i+width-1] and listToSort[i+width:i+2*width-1] to workerList[] */
          /* or copy listToSort[i:n-1] to workerList[] ( if(i+width >= n) ) */
          bottomUpMerge(&listToSort, i, min(i+width, n), min(i+2*width, n), &workerList);
      }
      /* Now workerList is full of runs of length 2*width. */
      /* Copy workerList to listToSort for next iteration. */
      
      //copyArray(&listToSort, &workerList, n);
      
      /* A more efficient implementation would swap the roles of listToSort and workerList */
      /* So, we just delete the listToSort, because workerList contains the last updated   */
      /* order. Then, we set the pointer of listToSort to the workerList. Last, we set     */
      /* workerList to NULL                                                                */
      free_list(&listToSort);
      listToSort = workerList;
      workerList = NULL;
      /* Now listToSort is full of runs of length 2*width. */
    }
    return listToSort;
}

/* Helper function for the mergeSort */
void bottomUpMerge(Listptr* listToSort, int iLeft, int iRight, int iEnd, Listptr* workerList)
{
  int i0 = iLeft;
  int i1 = iRight;
  char i0str[strLength], i1str[strLength];
  int j;
 
  /* While there are elements in the left or right lists */
  for(j = iLeft; j < iEnd; j++)
  {
      /* Notice that values of (i0+1) and (i1+1) can exceed,  */
      /* the length of the list, but n_th function won't find */
      /* the specified position, thus the string arrays will  */
      /* valid data                                           */
      n_th(*listToSort, i0+1, i0str, strLength);
      n_th(*listToSort, i1+1, i1str, strLength);
      
      /* If left list head exists and is <= existing right list head */
      if (i0 < iRight && (i1 >= iEnd || strcmp(i0str, i1str) <= 0))
      {
          insert_at(workerList, j, i0str);
          i0++;
      }
      else
      {
          insert_at(workerList, j, i1str);
          i1++;
      }
  }
}

/* Copy list B to list A. Delete previous state of A and delete B */
void copyList(Listptr *A, Listptr *B,const int n)
{
    int i;
    char Bstr[strLength];
    
    free_list(A);
    for(i = 0 ; i < n ; i++)
    {
        n_th(*B, i+1, Bstr, strLength);
        insert_at(A, i, Bstr);
    }
    free_list(B);
}

/* Test Main */
int main(void)
{ Listptr list = NULL;
  Listptr helperList = NULL;
  int listSize = 19;
  
#define testOne
#ifdef testOne
  insert_at(&list, 0, "W");
  insert_at(&list, 1, "C");
  insert_at(&list, 2, "Z");
  insert_at(&list, 3, "E");
  insert_at(&list, 4, "F");
  insert_at(&list, 5, "G");
  insert_at(&list, 6, "D");
  insert_at(&list, 7, "B");
  insert_at(&list, 8, "A");
#endif
#define testTwo
#ifdef testTwo
  insert_at(&list, 0, "A");
  insert_at(&list, 1, "B");
  insert_at(&list, 2, "C");
  insert_at(&list, 3, "D");
  insert_at(&list, 4, "E");
  insert_at(&list, 5, "F");
  insert_at_end(&list, "Samaras");
  insert_at(&list, 6, "G");
  insert_at(&list, 7, "W");
  insert_at(&list, 8, "Z");
#endif
  
  printf("List is : "); print(list);
  
  list = bottomUpSort(list, helperList, listSize);
  
  printf("List is : "); print(list);
 
  free_list(&list);
  free_list(&helperList);
  return 0;
}

This code was developed by me, G. Samaras.

Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s