/
QuickSortLinkedList.java
170 lines (161 loc) · 6.26 KB
/
QuickSortLinkedList.java
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
package com.thealgorithms.datastructures.lists;
/*
*
* @aurthor - Prabhat-Kumar-42
* @github - https://github.com/Prabhat-Kumar-42
*
* Problem :
* QuickSort on Linked List
*
* Note: Taking head as pivot in current implementation.
* N represents NULL node
* Example:
*
* -> Given Linked List :
* 5 -> 3 -> 8 -> 1 -> 10 -> 2 -> 7 -> 4 -> 9 -> 6
*
* -> How Sorting will work according to the QuickSort Algo written below
*
* current pivot : 5
* List lessThanPivot : 3 -> 1 -> 2 -> 4
* List greaterThanPivot : 5 -> 8 -> 10 -> 7 -> 9 -> 6
*
* -> reccur for lessThanPivot and greaterThanPivot
*
* lessThanPivot :
* current pivot : 3
* lessThanPivot : 1 -> 2
* greaterThanPivot : 4
*
* greaterThanPivot:
* current pivot : 5
* lessThanPivot : null
* greaterThanPivot : 8 -> 10 -> 7 -> 9 -> 6
*
* By following the above pattern, reccuring tree will form like below :
*
* List-> 5 -> 3 -> 8 -> 1 -> 10 -> 2 -> 7 -> 4 -> 9 -> 6
*
* Pivot : 5
* /\
* / \
* / \
* / \
* / \
* List: (3 -> 1 -> 2 -> 4) (5 -> 8 -> 10 -> 7 -> 9 -> 6)
* Pivot : 3 5
* /\ /\
* / \ / \
* / \ / \
* / \ / \
* List: (1 -> 2) (4) (N) (8 -> 10 -> 7 -> 9 -> 6)
* Pivot: 1 4 8
* /\ /\ /\
* / \ / \ / \
* / \ / \ / \
* List: (N) (2) (N) (N) (6 -> 7) (9 -> 10)
* Pivot: 2 6 9
* /\ /\ /\
* / \ / \ / \
* / \ / \ / \
* List: (N) (N) (N) (7) (N) (10)
* Pivot: 7 10
* /\ /\
* / \ / \
* / \ / \
* (N) (N) (N) (N)
*
*
* -> After this the tree will reccur back (or backtrack)
* and the returning list from left and right subtree will attach
* themselves around pivot.
* i.e. ,
* (listFromLeftSubTree) -> (Pivot) -> (listFromRightSubtree)
*
* This will continue until whole list is merged back
*
* eg :
* Megring the above Tree back we get :
*
* List: (1 -> 2) (4) (6 -> 7) (9 -> 10)
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* \ / \ /
* Pivot: 3 8
* List: (1 -> 2 -> 3 -> 4) (6 -> 7 -> 8 -> 9 -> 10)
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \ /
* \/
* Pivot: 5
* List: (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10)
*
*
* -> This will result in a sorted Linked List
*/
public class QuickSortLinkedList {
private SinglyLinkedList list = null; // Linked list
private Node head = null; // head of the list
// Counstructor
public QuickSortLinkedList(SinglyLinkedList list) {
this.list = list;
this.head = list.getHead();
}
// Function to sort a linked list using the Quick Sort algorithm
public void sortList() {
head = sortList(head);
list.setHead(head);
}
// helper function to apply QuickSort to the stored list
public Node sortList(Node head) {
if (head == null || head.next == null) {
return head;
}
// Choose the first element as the pivot
Node pivot = head;
head = head.next;
pivot.next = null;
Node lessHead = new Node(); // stores the nodes cantaining data less than pivot node
Node lessTail = lessHead; // tail of lessHead
Node greaterHead = new Node(); // stores the nodes cantaining data greater than pivot node
Node greaterTail = greaterHead; // tail of greaterHead
// Partition the list around the pivot
while (head != null) {
if (head.value < pivot.value) {
lessTail.next = head;
lessTail = lessTail.next;
} else {
greaterTail.next = head;
greaterTail = greaterTail.next;
}
head = head.next;
}
// Seperating lessHead and greaterHead to form two seperate linkedList
lessTail.next = null;
greaterTail.next = null;
// Recursively sort the sublists
Node sortedLess = sortList(lessHead.next);
Node sortedGreater = sortList(greaterHead.next);
// Combine the sorted sublists and pivot
if (sortedLess == null) {
pivot.next = sortedGreater;
return pivot;
} else {
Node current = sortedLess;
while (current.next != null) {
current = current.next;
}
current.next = pivot;
pivot.next = sortedGreater;
return sortedLess;
}
}
}