/
Quick_Sort_on_Linked_List.java
97 lines (82 loc) · 1.88 KB
/
Quick_Sort_on_Linked_List.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
// { Driver Code Starts
import java.util.*;
import java.lang.*;
class Node {
int data;
Node next;
Node(int key) {
data = key;
next = null;
}
}
class SortLL {
static Node head;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int a1 = sc.nextInt();
Node head = new Node(a1);
addToTheLast(head);
for (int i = 1; i < n; i++) {
int a = sc.nextInt();
addToTheLast(new Node(a));
}
GfG gfg = new GfG();
Node node = gfg.quickSort(head);
printList(node);
System.out.println();
}
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
public static void addToTheLast(Node node) {
if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = node;
}
}
}
class GfG {
static Node partition(Node head, Node tail) {
Node prev = head, cur = head.next;
Node pivot = head;
int data = 0;
while (cur != tail.next) {
if (cur.data < pivot.data) {
data = prev.next.data;
prev.next.data = cur.data;
cur.data = data;
prev = prev.next;
}
cur = cur.next;
}
data = pivot.data;
pivot.data = prev.data;
prev.data = data;
return prev;
}
static void quickSortrec(Node head, Node tail) {
if (head == tail || tail == null || head == null)
return;
Node pivot = partition(head, tail);
quickSortrec(head, pivot);
quickSortrec(pivot.next, tail);
}
public static Node quickSort(Node node) {
Node tail = node, head = node;
while (tail.next != null)
tail = tail.next;
quickSortrec(head, tail);
return node;
}
}