CODEWITHSUNDEEP
clinked-listmergesort
David Adrian
David Adrian

Reputation: 3

Improving my mergesort for linked lists. How?

before I dive into explanations, you should be aware that the following code might be really bad. I started programming about 2 months ago (a few hours there and there). So I'm inexperience, my coding style is very improvable and I still miss practice and lots of (basic) knowledge. This also includes me calling things by the wrong name probably :).

I got interested in algorithms (university) and wanted to practice some pointer handling (had quite some problems with it initially) so I decided to do mergesort with singly linked-lists and see how it performs compared to the mergeSort algorithm of my professor (which sorts arrays). And no this isn't homework (none of my university course (electrical engineering) have homework) - this is me improving in understanding of algorithms, C and simply practicing things.

My code already works. For testing purposes I always created reverse sorted lists. It's still missing something for cases like that the list is NULL.

So before posting the code thats the struct I'm using:

struct list{
  int nbr;
  struct list *next_el;
};
typedef struct list LIST;
typedef LIST *z_LIST;

I got two functions, mergeSort and merge. mergeSort returns the new head of the sorted (sub-)lists and merge returns the head of the merged sequences.

Right now I give mergeSort the current head of the unsorted list and the amount of elements. It then breaks down the list recursively (obviously :)). I'm not sure on how much to say on the following code. If something is unclear I will answer and explain as quick as possible, but

z_LIST mergeSort ( z_LIST head, int length ) {

  int steps;
  int m = 0;
  z_LIST head1 = NULL, head2 = NULL, new_head = NULL;

if( length > 1) {

  m = (length+1)/2;


  head2 = head; 
  for(steps = 0; steps<m; steps++) {
    head2 = head2->next_el;
  }

  head1 = mergeSort(head, m);
  head2 = mergeSort(head2, length-m);

  new_head = merge(head1, head2, m, length-m);

  return new_head;

  } else {
    return head;
  }
}

merge receives the heads of the two sub-lists (which are either one element or the already sorted sequences) and the elements of the first and second list.

z_LIST merge (z_LIST head1, z_LIST head2, int l1, int l2)  {

  int i,j;
  z_LIST part1 = head1, part2 = head2;
  z_LIST temp_head = NULL, head = NULL;

/*First I let it check what the head of the new list is going to 
be and thus initiating the merging process with either i=1/j=0
or i=0/j=1.*/

  if(part1->nbr < part2->nbr){
    head = part1;
    if(part1->next_el != NULL)  {
      part1 = part1->next_el;
    }
    i=1;
    j=0;
  } else {
    head = part2;
    if(part2->next_el != NULL)  { //The last element of the original list points
      part2 = part2->next_el;     //to NULL. If I would then make part2 = NULL,
    }                             //then there wouldn't be part2->nbr ->lots
    i=0;
    j=1;
  }

  temp_head = head;

  while( (i<l1) || (j<l2) ) {
    if( ((part1->nbr < part2->nbr) && i<l1)||( j>=l2 ))  {
      temp_head->next_el = part1;
      part1 = part1->next_el;
      temp_head = temp_head->next_el;
      if (j>=l2)  { //If j>=l2 then I let merge add one more item of list1
       break;       //since list 1 is already sorted and linked correctly.
      }             //Same below. Should shave off some operations/time?
      i++;
    } else {
      temp_head->next_el = part2;
      part2 = part2->next_el;
      temp_head = temp_head->next_el;
      if (i>=l1)  {
        break;
      }
      j++;
    }
  }

  return head;
}

So I'd welcome any comments on what I have done plain stupid, where I didn't think about possible problems, where some input code break code or on how to do it better, I'm sure there are a still quite a bit of possibilities for improvement. Thanks in advance.

Upvotes: 0

Views: 447

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 753930

The 'normal' structure for the merge phase of a sort is:

set output list to empty
while (list1 not empty && list2 not empty)
{
    if (list1->headvalue < list2->headvalue
        move head of list1 to output list
    else
        move head of list2 to output list
}
while (list1 not empty)
    move head of list1 to output list
while (list2 not empty)
    move head of list2 to output list

The 'move' operation includes updating the pointer to the next item in the list.

You have a somewhat different structure in your merge() function.

It is also aconventional to require the lists to be counted. Normally, you determine the end of the list using either 'next is null' or 'next is head' depending on whether the list is purely linear or whether it is a circular list.

Upvotes: 0

Related Questions