-
Notifications
You must be signed in to change notification settings - Fork 0
/
101-cocktail_sort_list.c
113 lines (107 loc) · 2.4 KB
/
101-cocktail_sort_list.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
110
111
112
113
#include "sort.h"
/**
* swap_nodes - Swaps two nodes in a doubly linked list.
* @list: A pointer to the head of the linked list.
* @l: The left item to swap.
* @r: The right item to swap.
*/
void swap_nodes(listint_t **list, listint_t *l, listint_t *r)
{
listint_t *tmp0 = NULL, *tmp1 = NULL, *tmp2 = NULL, *tmp3 = NULL;
if ((l == NULL) || (r == NULL) || (list == NULL) || (l == r))
return;
tmp0 = l->prev, tmp1 = l->next, tmp2 = r->prev, tmp3 = r->next;
if (l->prev == r)
{
l->next = r, l->prev = tmp2, r->next = tmp1, r->prev = l;
if (tmp2 != NULL)
tmp2->next = l;
if (tmp1 != NULL)
tmp1->prev = r;
}
else if (l->next == r)
{
l->next = tmp3, l->prev = r, r->next = l, r->prev = tmp0;
if (tmp0 != NULL)
tmp0->next = r;
if (tmp3 != NULL)
tmp3->prev = l;
}
else
{
l->next = tmp3, l->prev = tmp2, r->next = tmp1, r->prev = tmp0;
if (tmp0 != NULL)
tmp0->next = r;
if (tmp1 != NULL)
tmp1->prev = r;
if (tmp2 != NULL)
tmp2->next = l;
if (tmp3 != NULL)
tmp3->prev = l;
}
if (l->prev == NULL)
*list = l;
if (r->prev == NULL)
*list = r;
}
/**
* get_tail - Retrieves the tail node of a doubly linked list.
* @list: A pointer to the head of the linked list.
*
* Return: The tail of the linked list, otherwise NULL.
*/
listint_t *get_tail(listint_t **list)
{
listint_t *node = NULL;
if (list != NULL)
{
node = *list;
while ((node != NULL) && (node->next != NULL))
node = node->next;
}
return (node);
}
/**
* cocktail_sort_list - Sorts a doubly linked list
* using the cocktail shaker sort algorithm.
* @list: The list to be sorted.
*/
void cocktail_sort_list(listint_t **list)
{
char swapped = FALSE;
listint_t *node = NULL, *next = NULL, *tmp;
if (list == NULL)
return;
do {
node = *list;
next = (node == NULL ? NULL : node->next);
swapped = FALSE;
while ((node != NULL) && (next != NULL))
{
tmp = next;
if (node->n > next->n)
{
swap_nodes(list, node, next);
swapped = TRUE;
print_list(*list);
}
node = tmp, next = (node == NULL ? NULL : node->next);
}
if (!swapped)
break;
swapped = FALSE;
next = get_tail(list);
node = next == NULL ? NULL : next->prev;
while ((node != NULL) && (next != NULL))
{
tmp = node;
if (node->n > next->n)
{
swap_nodes(list, node, next);
swapped = TRUE;
print_list(*list);
}
next = tmp, node = next == NULL ? NULL : next->prev;
}
} while (swapped);
}