forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPatienceSort.java
More file actions
112 lines (100 loc) · 3.75 KB
/
PatienceSort.java
File metadata and controls
112 lines (100 loc) · 3.75 KB
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
package com.thealgorithms.sorts;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
/**
* This class implements the Patience Sort algorithm. Patience Sort is a sorting algorithm that
* is particularly good for sorting sequences that are already partially sorted.
*/
public class PatienceSort implements SortAlgorithm {
/**
* Sorts an array of comparable elements using the Patience Sort algorithm.
*
* @param array the array to be sorted
* @param <T> the type of elements in the array, must be comparable
* @return the sorted array
*/
@Override
public <T extends Comparable<T>> T[] sort(T[] array) {
if (array.length == 0) {
return array;
}
final List<List<T>> piles = formPiles(array);
final PriorityQueue<PileNode<T>> pq = mergePiles(piles);
extractPiles(array, pq);
return array;
}
/**
* Forms piles from the given array. Each pile is a list of elements where
* each element is smaller than the one before it. Binary search is used
* to find the appropriate pile for each element.
*
* @param array the array of elements to be organized into piles
* @param <T> the type of elements in the array, must be comparable
* @return a list of piles
*/
private static <T extends Comparable<T>> List<List<T>> formPiles(final T[] array) {
final List<List<T>> piles = new ArrayList<>();
final List<T> lastElements = new ArrayList<>();
for (T x : array) {
int pos = Collections.binarySearch(lastElements, x);
if (pos < 0) {
pos = -pos - 1;
}
if (pos < piles.size()) {
piles.get(pos).add(x);
lastElements.set(pos, x);
} else {
List<T> newPile = new ArrayList<>();
newPile.add(x);
piles.add(newPile);
lastElements.add(x);
}
}
return piles;
}
/**
* Merges the piles into a priority queue where the smallest elements are
* prioritized.
*
* @param piles the list of piles to be merged
* @param <T> the type of elements in the piles, must be comparable
* @return a priority queue containing the top element of each pile
*/
private static <T extends Comparable<T>> PriorityQueue<PileNode<T>> mergePiles(final Iterable<List<T>> piles) {
PriorityQueue<PileNode<T>> pq = new PriorityQueue<>();
for (List<T> pile : piles) {
pq.add(new PileNode<>(pile.removeLast(), pile));
}
return pq;
}
/**
* Extracts elements from the priority queue to form the sorted array.
*
* @param array the array to be filled with sorted elements
* @param pq the priority queue containing the elements to be extracted
* @param <T> the type of elements in the array, must be comparable
*/
private static <T extends Comparable<T>> void extractPiles(final T[] array, final PriorityQueue<PileNode<T>> pq) {
int index = 0;
while (!pq.isEmpty()) {
PileNode<T> node = pq.poll();
array[index++] = node.value;
if (!node.pile.isEmpty()) {
pq.add(new PileNode<>(node.pile.removeLast(), node.pile));
}
}
}
/**
* A helper record representing a node in the priority queue.
*
* @param <T> the type of elements in the node, must be comparable
*/
private record PileNode<T extends Comparable<T>>(T value, List<T> pile) implements Comparable<PileNode<T>> {
@Override
public int compareTo(PileNode<T> other) {
return this.value.compareTo(other.value);
}
}
}