top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration

Facebook Login
Site Registration

c: Selection sort on a linklist?

+2 votes
97 views

I have a data-structure as linklist which has elements as integer. I want to sort this linklist using selection sort, can someone help me.

posted Oct 15, 2014 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote
 
Best answer

Selection short first finds the smallest element in the array and exchanges
it with the element in the first position, then find the second smallest
element and exchange it with the element in the second position, and
continues in this way until the entire array is sorted.

Apply the same on link list, where we have to compare each link list
element, and have to swap the link list elements.

Here is my code (tested) :)

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

typedef struct link_list {
   int data;
   struct link_list *next;
}Node;

void creat_list(Node **head, int num);
void display(Node *head);
void selection_sort(Node *head);
void swap(Node *x, Node *y);
void free_node(Node *head);

int main()
{
   Node *head = NULL;
   int num, num_elem, i;

   printf("Enter number of elements: ");
   scanf("%d", &num_elem);

   printf("Enter %d number one by one:\n", num_elem);
   for (i = 0; i < num_elem; i++) {
       scanf("%d", &num);
       creat_list(&head, num);
   }

   printf("Displaying link list before sorting :\n");
   display(head);

   selection_sort(head);

   printf("Displaying link list after sorting :\n");
   display(head);

   free_node(head);

   return 0;
}

// Function to create node
void creat_list(Node **head, int num)
{
    Node *front, *tail;

    tail = malloc(sizeof(Node));
    if (tail == NULL) {
        printf("Malloc fails ...\n");
        return;
    }

    tail->data = num;
    tail->next = NULL;

    if (*head == NULL) {
        *head = tail;
    } else {
        front = *head;
        while (front->next != NULL)
            front = front->next;

        front->next = tail;
    }
}

// Swaping of data between two nodes. 
void swap(Node *x, Node *y)
{
    int temp;

    temp = x->data;
    x->data = y->data;
    y->data = temp;
}

//    Performing selection sort
void selection_sort(Node *head)
{
    Node  *i, *j, *min;

    for (i = head; i != NULL && i->next != NULL; i = i->next) {
        min = i;

        for (j = i->next; j != NULL; j = j->next) {
            if (j->data < min->data) {
                min = j;
            }
        }

        if (min != i) { // Ignore swaping at the same list.
            swap(min, i);
        }
    }
}

// Display link list content
void display(Node *head)
{
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Freeing up the allocated node.
void free_node(Node *head)
{
    Node *temp;
    while(head) {
        temp = head;
        head = head->next;
        free(temp);
    }
}
answer Oct 15, 2014 by Arshad Khan
Similar Questions
0 votes

Can some one explain merge sort using linked list in java with code.

+2 votes

Can someone share the C code for selection or bubble sort for string. String comparison should be based on dictionary comparison.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...