blob: cbe6a02d5813d7a845f5cb1aaecfb0b6fdb03bef (
plain) (
blame)
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
|
#include <iostream>
template <typename T>
struct DLListElem {
T data;
DLListElem<T> *next, *prev;
DLListElem(const T& data, DLListElem<T>* next = nullptr, DLListElem<T>* prev = nullptr) : data(data), next(next), prev(prev) {}
};
template <typename T>
void freeList(DLListElem<T>* l) {
DLListElem<T>* temp;
while (l != nullptr) {
temp = l;
l = l->next;
delete temp;
}
}
// A <-> i <-> j <-> D
template <typename T>
void swap(DLListElem<T>* i, DLListElem<T>* j) {
if (i == j) return;
if (i->prev != nullptr) i->prev->next = j;
if (j->next != nullptr) j->next->prev = i;
DLListElem<T>* iPrev = i->prev;
i->next = j->next;
i->prev = j;
j->next = i;
j->prev = iPrev;
}
template <typename T>
void swapNext(DLListElem<T>* i, DLListElem<T>* j) {
if (i == j) return;
if (i->prev != nullptr) i->prev->next = j;
i->next = j->next;
j->next = i;
}
// O(n^2) time complexity
template <typename T>
void sortDescending(DLListElem<T>* start, DLListElem<T>* end) {
for (DLListElem<T>* i = end; i != start && i != nullptr; i = i->prev) {
DLListElem<T>* toSwap = i;
for (DLListElem<T>* j = i->prev; j != start && j != nullptr; j = j->prev) {
if (j->data < toSwap->data) toSwap = j;
}
//swap(i, toSwap);
swapNext(i, toSwap);
}
// TODO: update prevs
}
int main() {
DLListElem<int>* l1 = new DLListElem<int>(1);
DLListElem<int>* l2 = new DLListElem<int>(2);
DLListElem<int>* l3 = new DLListElem<int>(3);
DLListElem<int>* l4 = new DLListElem<int>(4);
DLListElem<int>* l5 = new DLListElem<int>(5);
DLListElem<int>* l6 = new DLListElem<int>(6);
DLListElem<int>* l7 = new DLListElem<int>(7);
DLListElem<int>* l8 = new DLListElem<int>(8);
// 8 7 2 5 6 1 4 3
l8->next = l7;
l7->prev = l8; l7->next = l2;
l2->prev = l7; l2->next = l5;
l5->prev = l2; l5->next = l6;
l6->prev = l5; l6->next = l1;
l1->prev = l6; l1->next = l4;
l4->prev = l1; l4->next = l3;
l3->prev = l4;
sortDescending(l8, l3);
for (DLListElem<int>* i = l8; i != nullptr; i = i->next)
std::cout << i->data << ", ";
std::cout << std::endl;
freeList(l1);
}
|
