-
Notifications
You must be signed in to change notification settings - Fork 2.1k
/
LinkedList_Insertion_sort.c
109 lines (99 loc) · 2.32 KB
/
LinkedList_Insertion_sort.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/* author : Akanksha Bhardwaj
Last Updated: 27/10/2016
C implementation of Insertion sort on Linked List
*/
#include <stdio.h>
#include <stdlib.h>
struct node {
int val;
struct node *next ;
struct node *prev;
};
void insert_beg(struct node **head , int val) {
struct node *nn =(struct node *)malloc(sizeof(struct node));
nn->val = val;
nn->prev = NULL;
nn->next = *head;
if(*head == NULL) {
*head = nn;
return;
}
(*head)->prev = nn;
*head = nn;
}
void insert_last(struct node **head , int val) {
struct node *nn =(struct node *)malloc(sizeof(struct node ));
nn->val = val;
nn->next = NULL;
struct node *trav = *head;
while(trav->next != NULL) {
trav = trav->next;
}
trav->next = nn;
nn->prev = trav;
}
void print(struct node *head) {
struct node *trav = head;
while(trav->next != NULL) {
printf("%d->",trav->val);
trav = trav->next;
}
printf("%d\n",trav->val);
}
int size(struct node *head) {
struct node *trav = head;
int c = 0;
while(trav != NULL) {
c++;
trav = trav->next;
}
return c;
}
void insertion_sort(struct node **head) {
struct node * i = *head ;
struct node *trav = *head;
struct node *j ;
int n;
if(*head != NULL && (*head)->next != NULL) {
while(trav->next != NULL) {
trav = trav->next;
}
for(i = *head ; i != trav ; i = i->next) {
n = i->next->val;
for(j = i; j != *head ; j = j->prev) {
if(j->val > n) {
j->next->val = j->val;
}
else {
j->next->val = n;
break;
}
}
if(j == *head ) {
if(j->val < n) {
j->next->val = n;
}
else {
j->next->val = j->val;
(*head)->val = n;
}
}
}
}
}
int main()
{
struct node *head = NULL;
int n, v;
scanf("%d", &n);
while(n--) {
scanf("%d",&v);
if(head == NULL) {
insert_beg(&head,v);
}
else insert_last(&head,v);
}
insertion_sort(&head);
print(head);
return 0;
}