I'm trying to improve my knowledge on Algorithms and Data Structures, so for the last 5-6 days I've been trying to implement different algorithms on different data structures. I've the basic knowledge on singly,doubly, and circular linked lists, and I can implement an insertion sort algorithm with arrays.
However, implementing an insertion sort algorithm with a singly linked list turned out be much more problematic than I initally was expecting. I do not like looking at other people's code and copying them to understand a concept. I really like to try to do it myself first. So, I've written some lines:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node node;
struct Node{
int num;
node *next;
};
void printLinkedList(node *ptr);
void insertionSortLinkedList(node *p,node *head,int sizeOfList);
/* Driver program applying Insertion Sort to a Singly Linked List */
int main(int argc,char *argv[]){
int i, sizeOfList=argc-1;
node *head,*ptr;
ptr=(node*)malloc(sizeOfList*sizeof(node));
for(i=0;i<sizeOfList;i++){
(ptr+i)->num=atoi(argv[i+1]);
(ptr+i)->next=(ptr+i+1);
}
(ptr + sizeOfList-1)->next=NULL;
head=ptr;
printLinkedList(head);
insertionSortLinkedList(ptr,head,sizeOfList);
return 0;
}
void printLinkedList(node *ptr) {
while (ptr != NULL) {
printf("%d ", ptr->num);
ptr=ptr->next;
}
printf("\n\n");
}
void insertionSortLinkedList(node *p,node *head,int sizeOfList){
int i=0;
int N=1;
int flag;
node *temp;
while(N<sizeOfList){
flag=0;
/* node N > node i */
if((p+N)->num>(p+i)->num){
i++;
}
/* node i >= node N */
else{
/* node i = node N */
if((p+N)->num==(p+i)->num){ // FIRST ERROR HERE. DOES NOT ENTER HERE FOR 2 1 3 1 5 4 3 WHEN 1(i) 2 3 1(N) 5 4 3
/* i = N */
if(i==N){
flag=1;
}
/* i != N */
else{
temp=(p+N);
(p+N-1)->next=(p+N)->next;
temp->next=(p+i)->next;
(p+i)->next=temp;
flag=1;
}
}
/* node i > node N */
else{
/* i = 0 and Head needs to change */
if(i==0){
temp=(p+N);
(p+N-1)->next=(p+N)->next;
temp->next=(p+i);
head=temp;
flag=1;
}
/* i != 0 and Head needs to change */
else{
temp=(p+N);
(p+N-1)->next=(p+N)->next;
temp->next=(p+i);
(p+i-1)->next=temp;
flag=1;
}
}
}
/* Increase N and set i equal zero */
if(flag==1){
i=0;
N++;
}
}
printf("Our ordered values in the LinkedList: ");
printLinkedList(head);
}
My code seems to be working fine up to a specific point. For example if I enter to terminal:
./a.out 2 1 3 1 5 4 3
The first "pivot" works fine and algorithm swaps the "2" and "1". Thus we get:
1 2 3 1 5 4 3
Then the next pivot also works fine and algorithm compares first "1" and "3", then "2" and "3" and it decides to do nothing, just incrementing the "pivot". So we get:
1 2 3 1 5 4 3
At this point my algorithm goes crazy and it compares "1" and "1" decides that "1(of first node)" is greater than "1(of pivot)". The rest of the algorithm does not work. And as the final result, the so called "sorted" array printed out is:
1 4
I've seen on the other websites problems related to insertion sort with linked lists, however they follow a different approach then what my code tries to do. If possible, I just would like to solve the bug behind this algorithm. If not, then I would probably give up and implement the code like the others. I would much appreciate if anyone could direct me in the correct mindset to solve this problem or tell me why this code is not working probably. Also if something about this, is fundamentally wrong, please do tell me...
Thanks to @Mykola 's directions I was able to implement the insertion sort in linked lists correctly. I've realized that one of my biggest problems was not handling the pointers of my nodes carefully. Passing their reference instead, was a big help. Also I've realized I was not traversing the linked list correctly. Due to these correction I had to change my code a little bit. Also I've tried to make my code clearer and I've added a push() function.
I'm going to include my code below, so that if anyone finds themselves in a situation similar to mine, they can check it as a reference:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node node;
struct Node{
int data;
node* next;
};
void printList(node* head);
void push(node** head_ref,int data);
void insertionSort(node** head_ref);
void insertIntoSorted(node** sorted_ref,node* new_node);
/* Driver program that applies insertion sort to singly linked lists */
int main(int argc, char* argv[]){
int i, sizeOfList;
sizeOfList=argc-1;
node *head;
head=NULL;
for(i=sizeOfList;i>0;i--){
push(&head,atoi(argv[i]));
}
/* Print the linked list before the insertion sort */
printf("Your list before the insertion sort is: ");
printList(head);
/* insertion sort function */
insertionSort(&head);
/* Print the linked list after the insertion sort */
printf("Your list after the sort is: ");
printList(head);
return EXIT_SUCCESS;
}
/* Utility function that inserts a new node at the beginning of a linked list */
void push(node** head_ref,int data){
//allocate node and fill
node* new_node;
new_node=(node*)malloc(sizeof(node));
new_node->data=data;
//link
new_node->next=*head_ref;
*head_ref=new_node;
}
/* Utility function to print a linked list */
void printList(node* head){
node* temp;
temp=head;
while(temp!=NULL){
printf("%d ",temp->data);
temp=temp->next;
}
printf("\n");
}
/* Function to sort a singly linked list using insertion sort */
void insertionSort(node** head_ref){
/* Initialize the sorted linked list */
node* sorted;
sorted=NULL;
/* Traverse the given linked list and insert every node to "sorted" */
node* current;
current=*head_ref;
while(current!=NULL){
/* Store "next" for next iteration */
node* next;
next=current->next;
/*Insert "current" into the "sorted" linked list */
insertIntoSorted(&sorted, current);
/* Update "current" to the next node */
current=next;
}
*head_ref=sorted;
}
/* Function to insert a given node in the "sorted" linked list. Where
* the insertion sort actually occurs.
*/
void insertIntoSorted(node** sorted_ref,node* new_node){
node* current;
/* Special case for the head end of the "sorted" */
if ((*sorted_ref == NULL) || ((*sorted_ref)->data >= new_node->data))
{
new_node->next = *sorted_ref;
*sorted_ref = new_node;
}
/* Locate the node before the point of insertion */
else
{
current = *sorted_ref;
while ((current->next!=NULL) && (current->next->data < new_node->data)){
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}