Created
January 22, 2025 01:12
-
-
Save edwingustafson/fa9b9413e79d24bd9172c95772462476 to your computer and use it in GitHub Desktop.
Quicksort in just a few lines of Java
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/java --source 21 | |
import java.util.ArrayList; | |
import java.util.Collections; | |
import java.util.List; | |
import java.util.logging.Level; | |
import java.util.logging.Logger; | |
import java.util.stream.Collectors; | |
import java.util.stream.IntStream; | |
import java.util.stream.Stream; | |
public class Qsort { | |
private static final Logger logger = Logger.getLogger(Qsort.class.getName()); | |
private static final List<Integer> digits = IntStream.range(0, 100).boxed().collect(Collectors.toList()); | |
public static void main(final String[] args) { | |
Collections.shuffle(digits); | |
logger.log(Level.INFO, "Original digits: {0}", digits); | |
logger.log(Level.INFO, "Sorted digits: {0}", Qsort.sort(digits)); | |
} | |
public static List<Integer> sort(final List<Integer> list) { | |
if ( list.isEmpty() ) { | |
return list; | |
} | |
final int pivot = list.get(0); | |
final var less = list.stream().skip(1).filter(i -> i <= pivot).toList(); | |
final var greater = list.stream().skip(1).filter(i -> i > pivot).toList(); | |
final var result = new ArrayList<Integer>(list.size()); | |
result.addAll(sort(less)); | |
result.add(pivot); | |
result.addAll(sort(greater)); | |
return result; | |
} | |
} | |
/* | |
Output: | |
Jan 21, 2025 8:08:16 PM Qsort main | |
INFO: Original digits: [19, 14, 9, 2, 37, 12, 3, 35, 11, 36, 16, 31, 44, 45, 80, 20, 76, 55, 73, 46, 1, 86, 64, 87, 61, 85, 66, 90, 26, 62, 0, 38, 89, 69, 67, 34, 21, 33, 17, 50, 59, 72, 23, 27, 60, 70, 65, 57, 4, 40, 77, 39, 43, 68, 24, 81, 95, 47, 18, 28, 15, 42, 53, 30, 74, 13, 75, 58, 97, 88, 29, 78, 82, 94, 41, 8, 79, 52, 91, 56, 54, 22, 63, 93, 83, 84, 71, 32, 10, 92, 49, 7, 6, 51, 99, 5, 98, 96, 48, 25] | |
Jan 21, 2025 8:08:16 PM Qsort main | |
INFO: Sorted digits: [0, 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] | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment