[ogmios]

Hello everyone,
I'm in a "Systems Programming" class that uses C exclusively. Not having the background in C that is expected (due to transfering colleges) makes things a little bit harder for me. This assignment has us first implementing a sort on an integer array using pointers, which wasn't too bad. However, we then have to use a linked list struct and do the same sorting. My code *almost* works, but the first number of the output is never sorted - it's always just the first number, and it's never "supposed" to be in the same position. Any help would be greatly appreciated, as it was tough for me to get this far, and I've been banging my head against the wall far too long trying to solve this last remaining issue.

Here's my code:

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

#define ARRAY_SIZE 10

typedef struct llist { //linked list struct
  int data;
  struct llist *next;
} node;

void part3Sort(node *head) { //Bubble sort for int array.
  int i,j;
  node *a, *b, *c, *curr;
  for(i=1; i <=ARRAY_SIZE; i++) {
    a = head;
    b = head->next;
    c = b->next;
    for(j=1; j <(ARRAY_SIZE-(i)); j++) {
      if(b->data > c->data) {
        b->next = c->next;
        c->next = b;
        a->next = c;
        a = c;
        c = b->next;
      }
      else {
        a = b;
        b = c;
        c = c->next;
      }
    }
  }
  printf("Sorted array:\n"); //Print out the sorted array.
  curr = a;
  while(curr) {
    printf("%d\n", curr->data);
    curr = curr->next;
  }
}


void part1() { //Create *int/malloc array/assignment/free().
  node* head, *curr; //Define an int* pointer variable.
  int i;
  head = NULL;
  unsigned int iseed = (unsigned int)time(NULL); //Use random #'s.
  srand (iseed);
  printf("Initial array:\n");
  for (i=1; i<=ARRAY_SIZE; i++) { // Assign values to array and print them.
    curr = (node*) malloc(sizeof(node));
    curr->data = rand() % 100 + 1;
    curr->next = head;
    head = curr;
  }
  curr = head;
  while(curr!=NULL) {
    printf("%d\n", curr->data);
    curr = curr->next;
  }
  part3Sort(head);
}

main(int argc,char **argv)
{
  part1();

}

Sample (wrong) output below:

Initial array:
35
86
76
66
12
36
14
92
55
81
Sorted array:
[b]35[/b]
12
14
36
55
66
76
81
86
92

This being my first ever stab at C, I'm sure I'm doing some strange things here... Also, any reference to arrays is there because we first created a program to sort arrays then had to modify it. Thanks again for any insight.

[Munawwar]

Do you have to restructure the linked list? It would be much easier to swap the data between nodes, rather than messing with linked list structure.

[baavgai]

Would also be easier with a real bubble sort... I'm not sure the point of having a linked list if you're going to have a globally declared ARRAY_SIZE.

a = head;
/* you start comparing here */
b = head->next; 
c = b->next;

Basically, you're skipping a. Or, the head.

This post has been edited by baavgai: 29 June 2011 - 12:00 PM

[cyclop]

baavgai, on 29 June 2011 - 11:59 AM, said:

Would also be easier with a real bubble sort... I'm not sure the point of having a linked list if you're going to have a globally declared ARRAY_SIZE.

a = head;
/* you start comparing here */
b = head->next; 
c = b->next;

Basically, you're skipping a. Or, the head.

For my assignment I have to bubble sort a linked list and I have implemented more or less the same code but in C++. I get a bit confused when you say /*start comparing here*/ so I would appreciate it if you elaborate a little more on what you mean by that.

Thanks in advance.

[ogmios]

Hey Cyclop,

Got your pm a day or two ago. Have been doing co-op for the past six months so haven't been here for quite a while. Anyway, I never did quite figure this out, but I was also on a tight deadline with plenty of other stuff to do.

From a quick glance at my code. I'd say that baavgai is correct, I'm just completely skipping over the first element, since I'm setting the "a" node, then comparing b and c. Looks like it could be fixed easily enough. Looking back over my stuff here, it's almost funny how much my skills have improved by working in the real world for a few months.

Hope your assignment goes well.