ChenSort is an improved bucket sort, which is a general-purpose sorting algorithm.
The time complexity is O(n) at best and O(nlogn) at worst, the space complexity is O(n), and it is stable.
Randomly generate [1000,10000000] random numbers in the range [-2^63,2^63-1], average speed is 3 times faster than Quicksort, fastest is 20 times. Traditional bucket sort cannot handle such a large range of values, because the performance is much worse than quicksort due to the huge resource consumption.
All performance data is performed under a single thread, which can easily support multi-threading.
The demos are all built on Flutter.
Dart code:
/// The essence of Chen Sort is an improved bucket sort void chenSort(List<int> list) { if (list.length < 2) { return; } int maxValue = list[0]; int minValue = maxValue; for (final element in list.skip(1)) { if (element > maxValue) { maxValue = element; } if (element < minValue) { minValue = element; } } /// All elements are the same and do not need to be sorted. if (maxValue == minValue) { return; } /// Limit the maximum size of the bucket to ensure the performance of long list /// sorting, which can be adjusted according to the actual situation. /// /// The essential difference between this and bucket sorting is that the size of /// the bucket is only related to the length of the list, not the range of element values. int bucketSize = min(list.length, 50000); int maxBucketIndex = bucketSize - 1; List<List<int>?> buckets = List.filled(bucketSize, null); int slot; /// Calculate the bucket in which the element is located based on the value of the element /// and the maximum and minimum values. /// Overflow detection BigInt range = BigInt.from(maxValue) - BigInt.from(minValue); if (BigInt.from(range.toInt()) == range) { int range = maxValue - minValue; double factor = maxBucketIndex / range; for (final element in list) { // slot = (((element - minValue) / range) * maxBucketIndex).toInt(); slot = ((element - minValue) * factor).toInt(); if (buckets[slot] == null) { buckets[slot] = []; } buckets[slot]!.add(element); } } else { /// Overflowed(positive minus negative) int positiveRange = maxValue; int negativeRange = -minValue; int positiveStartBucketIndex = maxBucketIndex ~/ 2 + 1; int positiveBucketLength = maxBucketIndex - positiveStartBucketIndex; int negativeBucketLength = positiveStartBucketIndex - 1; for (final element in list) { if (element < 0) { slot = negativeBucketLength - ((-element / negativeRange) * negativeBucketLength).toInt(); } else { slot = positiveStartBucketIndex + ((element / positiveRange) * positiveBucketLength).toInt(); } if (buckets[slot] == null) { buckets[slot] = []; } buckets[slot]!.add(element); } } int compare(int left, int right) { return left - right; } int index = 0; for (final bucket in buckets) { if (bucket != null) { if (bucket.length > 1) { if (bucket.length >= 1000) { chenSort(bucket); } else { /// The sort method here represents the fastest comparison-type algorithm (Quick sort, Tim sort, etc.) bucket.sort(compare); } for (final element in bucket) { list[index++] = element; } } else { list[index++] = bucket[0]; } } } }Java code(Multi-thread. The code just shows that this algorithm can easily support multi-threaded sorting, and the actual performance data is performed under a single thread):
static void chenSort(Integer[] list) { int length = list.length; if (length < 2) { return; } Integer maxValue = Integer.MIN_VALUE; Integer minValue = Integer.MAX_VALUE; for (Integer element : list) { if (element > maxValue) { maxValue = element; } if (element < minValue) { minValue = element; } } /// All elements are the same and do not need to be sorted. if (maxValue.equals(minValue)) { return; } /// Limit the maximum size of the bucket to ensure the performance of long list /// sorting, which can be adjusted according to the actual situation. /// /// The essential difference between this and bucket sorting is that the size of /// the bucket is only related to the length of the list, not the range of element values. int bucketSize = Math.min(length, 50000); int maxBucketIndex = bucketSize - 1; ArrayList<Integer>[] buckets = new ArrayList[bucketSize]; int slot; /// Calculate the bucket in which the element is located based on the value of the element /// and the maximum and minimum values. /// Overflow detection BigInteger bigRange = BigInteger.valueOf(maxValue).subtract(BigInteger.valueOf(minValue)); if (BigInteger.valueOf(bigRange.intValue()).equals(bigRange)) { double factor = maxBucketIndex * 1.0 / (maxValue - minValue); for (Integer element : list) { slot = (int) ((element - minValue) * factor); if (buckets[slot] == null) { buckets[slot] = new ArrayList<>(); } buckets[slot].add(element); } } else { /// Overflowed(positive minus negative) double positiveRange = maxValue; double negativeRange = -minValue; int positiveStartBucketIndex = maxBucketIndex / 2 + 1; int positiveBucketLength = maxBucketIndex - positiveStartBucketIndex; int negativeBucketLength = positiveStartBucketIndex - 1; Integer zero = 0; for (Integer element : list) { if (element < zero) { slot = negativeBucketLength - (int) ((-element / negativeRange) * negativeBucketLength); } else { slot = (int) (positiveStartBucketIndex + ((element / positiveRange) * positiveBucketLength)); } if (buckets[slot] == null) { buckets[slot] = new ArrayList<>(); } buckets[slot].add(element); } } Comparator<Integer> comparator = Comparator.comparingInt(left -> left); // Multi-thread sorting between buckets CountDownLatch countDownLatch = new CountDownLatch(buckets.length); for (ArrayList<Integer> bucket : buckets) { if (bucket != null) { if (bucket.size() > 1) { executor.execute(() -> { bucket.sort(comparator); countDownLatch.countDown(); }); } else { countDownLatch.countDown(); } } else { countDownLatch.countDown(); } } try { countDownLatch.await(); } catch (InterruptedException ignored) { } int index = 0; for (ArrayList<Integer> bucket : buckets) { if (bucket != null) { if (bucket.size() > 1) { for (Integer element : bucket) { list[index++] = element; } } else { list[index++] = bucket.get(0); } } } }Performance(10 million random numbers sorted, single thread):
Random random = new Random(); Integer[] arr = new Integer[10000000]; long maxValue = Integer.MAX_VALUE; long minValue = Integer.MIN_VALUE; long range = maxValue - minValue + 1; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (minValue + random.nextLong(range)); } Integer[] copy = new Integer[arr.length]; System.arraycopy(arr, 0, copy, 0, arr.length); long start = System.currentTimeMillis(); chenSort(arr); long chenSortTimeUsage = System.currentTimeMillis() - start; start = System.currentTimeMillis(); Arrays.sort(copy); long quickSortTimeUsage = System.currentTimeMillis() - start;chen sort: 3384 ms, quick sort: 9366 ms, 63.869314541960286%(2.767730496453901x) faster chen sort: 3450 ms, quick sort: 7223 ms, 52.2359130555171%(2.093623188405797x) faster chen sort: 1693 ms, quick sort: 5000 ms, 66.14%(2.9533372711163617x) faster chen sort: 2306 ms, quick sort: 6267 ms, 63.204084889101644%(2.717692974848222x) faster chen sort: 2922 ms, quick sort: 10145 ms, 71.19763430261213%(3.471937029431896x) faster chen sort: 3285 ms, quick sort: 9211 ms, 64.33611985669309%(2.803957382039574x) faster chen sort: 2661 ms, quick sort: 9236 ms, 71.18882633174535%(3.4708756106726795x) faster chen sort: 2538 ms, quick sort: 6422 ms, 60.47960137028963%(2.530338849487786x) faster chen sort: 1749 ms, quick sort: 4928 ms, 64.50892857142857%(2.8176100628930816x) faster chen sort: 1775 ms, quick sort: 5254 ms, 66.21621621621621%(2.96x) faster chen sort: 1626 ms, quick sort: 5155 ms, 68.45780795344326%(3.1703567035670357x) faster chen sort: 2375 ms, quick sort: 4877 ms, 51.302029936436334%(2.0534736842105263x) faster chen sort: 1923 ms, quick sort: 5250 ms, 63.37142857142857%(2.730109204368175x) faster chen sort: 3028 ms, quick sort: 9237 ms, 67.21879398072967%(3.0505284015852046x) faster chen sort: 2692 ms, quick sort: 9030 ms, 70.18826135105205%(3.3543833580980684x) fasterXiSort The slowest sorting algorithm I've developed with the most efficient code execution in the world.
If it helps you a lot, consider sponsoring me a cup of milk tea, or giving a star. Your support is the driving force for me to continue to maintain.
Thanks to the following netizens for their sponsorship.
- 小小鸟 2022.06.08
- 孟焱 2022.06.08