-
Notifications
You must be signed in to change notification settings - Fork 0
/
SortV1.txt
80 lines (76 loc) · 2 KB
/
SortV1.txt
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
//SortV1()
template <typename TData> void LinkedList<TData>::SortV1(SortOrder SortBy){
if (SortBy == Unordered){
return;
}
if (_firstNode == NULL){ //Zero Items?
return;
}
if (_firstNode -> Next() == NULL){ //1 Item?
return;
}
int length = Length();
ListNode<TData> *previous, *current, *next;
bool swapped;
for (int i = 0; i < length; i++){
swapped = false;
previous = NULL;
current = _firstNode;
//By the ith time the list is traversed, the last i items will already be in place.
//So we don't have to traverse the whole list again.
for (int j = 0; j < length-i-1; j++){
next = current -> Next();
if (next == NULL){ //With the length-i-1 check above, this should not occur. But written here, just in case.
break;
}
if (
(SortBy == Ascending && ((int) current->Data() > (int) next->Data()))
||
(SortBy == Descending && ((int) current->Data() < (int) next->Data()))
){
//Swap
swapped = true;
if (current == _firstNode){
_firstNode = next;
}
else{
previous -> SetNext(next);
}
if (next -> Next() == NULL){
//End of the list reached
current -> SetNext(NULL);
}
else{
current -> SetNext(next -> Next());
}
//After swapping, keep the current pointer pointing to the same node. Then check values of this node and the new Next node
previous = next;
next -> SetNext(current);
}
else{
previous = current;
current = current -> Next();
}
if (current == NULL){
break; //With the length-i-1 check above, this should not occur. But written here, just in case.
}
}
/*
Debugging Purposes
*/
//current = _firstNode;
//for (int j = 0; j < length; j++){
// cout << (int) current->Data() << " ";
// current = current -> Next();
//}
//cout << "Length: " << length << " i: " << i <<endl;
/*
End debugging
*/
if (swapped == false){
break;
}
}
_SortStatus = SortBy;
Rewind();
}