Thread: Help with sorting a Linked List !!

Hey,

I was trying to implement sorting in a linked list. However, when i run the sortList() function the program abruptly terminates.

Here's the complete code

Code:

/*
 * {
 * SingleLinkedList.c
 *
 *  Created on: 28-Nov-2014
 *      Author: bennet
 */
#define NULL 0
#include<stdio.h>
#include<stdlib.h>
struct node {
    int data;
    struct node *link;
}*start;
void menu() {
    printf("1. Insert at End\n");
    printf("2. Insert at head\n");
    printf("3. Display\n");
    printf("4. Delete\n");
    printf("5. Sort Ascending\n");
    printf("6. Build List\n");
}
void sortList(struct node **head_ref) {
    struct node *curr = *head_ref;
    struct node *next;
    while (curr != NULL) {
        {
            next = curr->link;
            if(curr->data < next->data)
            {
                int temp = curr->data;
                curr->data = next->data;
                next->data = temp;
            }
        }
        curr = curr->link;
        }
    }


void add(struct node **head_ref, int data) {
    struct node *temp = (struct node *) malloc(sizeof(struct node));
    struct node *start = *head_ref;
    if (*head_ref == NULL) {
        temp->data = data;
        temp->link = NULL;
        *head_ref = temp;
    } else {
        while (start->link != NULL) {
            start = start->link;
        }
        temp->data = data;
        temp->link = NULL;
        start->link = temp;
    }
    printf("Added the data %d\n", data);
}
void insertAtHead(struct node **head_ref, int value) {


    struct node *temp = (struct node *) malloc(sizeof(struct node));
    temp->data = value;
    temp->link = *head_ref;
    *head_ref = temp;
}
void delete(struct node **start, int delete) {
    struct node *temp = *start;
    while (temp->link != NULL) {
        if (temp->link->data == delete) {
            temp->link = temp->link->link;
            free(temp->link);
            break;
        } else
            temp = temp->link;
    }
}
void display(struct node **head_ref) {
    struct node *temp = *head_ref;
    while (temp != NULL) {
        printf("%d\n", temp->data);
        temp = temp->link;
    }


}
void buildList(struct node **head_ref) {
    int i;
    for (i = 0; i < 10; i++) {
        add(&(*head_ref), i);
    }


}
int main() {
    int choice;
    start = NULL;
    char charInput;
    do {
        menu();
        scanf("%d", &choice);
        switch (choice) {
        case 1: {
            int datas;
            scanf("%d", &datas);
            add(&start, datas);
            break;
        }
        case 3:
            display(&start);
            break;
        case 2: {
            int datas;
            scanf("%d", &datas);
            insertAtHead(&start, datas);
            break;
        }
        case 4: {
            int datas;
            scanf("%d", &datas);
            delete(&start, datas);
            break;
        }
        case 5: {
            sortList(&start);
            break;
        }
        case 6: {
            buildList(&start);
            break;
        }
}
        printf("Want to Continue(y/n)?\n");
        scanf(" %c", &charInput);
    } while (charInput == 'y' || charInput == 'Y');
    return 0;
}

Any suggestion to resolve this will be very helpful . Thanks !!

Your sortList() function doesn't really do anything useful. You can't just pass through the list once comparing adjacent items and swapping them. That is basically a single pass of a bubble sort method which is a naive sorting algorithm.

Look into using merge sort which is ideal for linked lists.

Also: do not cast the return value of malloc(). There is no reason to do it and it just creates additional code to maintain for no reason (and can hide a serious bug if you don't maintain it properly). Your insert and add() functions can do the same job in one function. It's also possible to simplify the insert code to a single branch of code. Similarly true for the delete function as well.

Originally Posted by nonpuz

Your sortList() function doesn't really do anything useful. You can't just pass through the list once comparing adjacent items and swapping them. That is basically a single pass of a bubble sort method which is a naive sorting algorithm.

Look into using merge sort which is ideal for linked lists.

Also: do not cast the return value of malloc(). There is no reason to do it and it just creates additional code to maintain for no reason (and can hide a serious bug if you don't maintain it properly). Your insert and add() functions can do the same job in one function. It's also possible to simplify the insert code to a single branch of code. Similarly true for the delete function as well.

Yes, I shall look into better sorting algorithms. Btw, I updated the sortList() function to this

Code:

void sortList(struct node **head_ref) {
	struct node *curr = *head_ref;
	struct node *next;
	while (curr != NULL) {
		{
			next = curr->link;
			while (next != NULL) {
				if (curr->data < next->data) {
					int temp = curr->data;
					curr->data = next->data;
					next->data = temp;
				}
				next = next->link;
			}
		}
		curr = curr->link;
	}
}

I was so wrong to only check the next values before swapping it. Should have checked one value with all the remaining value