Is this a new sort algorithm? [implemented in Java and pseudocode]
I know this may be a stupid question, perhaps the stupidest question today, but I have to ask: did I invent this sort algorithm?
Yesterday I had some inspiration for the sorting algorithm based on exchange Today, I realized it, its work
It may already exist because there are many unpopular sorting algorithms here with little or no information and almost no implementation
Description: basically, this algorithm needs one item, one pair, and another item until the end of the list For each item / pair, compare two items that are the same distance from the pairing space or the radius of the item until they reach the boundary of the array, and then exchange these items as needed Repeat for each pair / item in the list
An English pseudo code:
FOR i index to last index of Array (starting from 0) L index is i - 1 R index is i + 1 //Odd case,where i is the center WHILE (L is in array range and R is in array range) IF item Array[L] is greater than Array[R] EXCHANGE item Array[L] with Array[R] END-IF ADD 1 to R REST 1 to L END-WHILE //Even case,where i is not the center L index is Now i R index in Now i + 1 WHILE (L is in array range and R is in array range) IF item Array[L] is greater than Array[R] EXCHANGE Array[L] with Array[R] END-IF ADD 1 to R REST 1 to L END-WHILE END FOR
This is an implementation in Java:
//package sorting; public class OrbitSort { public static void main(String[] args) { int[] numbers ={ 15,8,6,3,11,1,2,14,13,7,9,4,10,5,12 }; System.out.println("Original list:"); display(numbers); sort(numbers); System.out.println("\nSorted list:"); display(numbers); } //Sorting algorithm public static void sort(int[] array) { for(int i = 0; i < array.length; i++){ int L = i - 1; int R = i + 1; //Odd case (with a central item) while(L >= 0 && R < array.length){ if(array[L] > array[R]) swap(array,L,R); L--; R++; } //Even case (with no central item) L = i; R = i + 1; while(L >= 0 && R < array.length) { if(array[L] > array[R]) swap(array,R); L--; R++; } } } //Swap two items in array. public static void swap(int[] array,int x,int y) { int temp = array[x]; array[x] = array[y]; array[y] = temp; } //Display items public static void display(int[] numbers){ for(int i: numbers) System.out.print(" " + i); System.out.println(); } }
I know it can be shorter, but this is only an early implementation
It may run in O (n ^ 2), but I'm not sure
So what do you think? Does it already exist?
Solution
To me, it looks like an improved bubble sorting algorithm, which may be better for some permutations of input elements
> java. util. Arrays. Sort (), which is a merge quicksort implementation > BubbleSort Sort (), a bubble sorting algorithm implemented in Java > orbitsort Sort (), your algorithm
result:
input size: 8192 warmup iterations: 32 Arrays.sort() iterations : 10000 total time : 4940.0ms avg time : 0.494ms BubbleSort.sort() iterations : 100 total time : 8360.0ms avg time : 83.6ms OrbitSort.sort() iterations : 100 total time : 8820.0ms avg time : 88.2ms
Of course, performance depends on the size and layout of the input
Direct code:
package com.sam.tests; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.ArrayList; import java.util.Arrays; import java.util.Random; import java.util.concurrent.Callable; public class SortBenchmark { public static class OrbitSort { // Sorting algorithm public static void sort(int[] array) { for (int i = 0; i < array.length; i++) { int L = i - 1; int R = i + 1; // Odd case (with a central item) while (L >= 0 && R < array.length) { if (array[L] > array[R]) swap(array,R); L--; R++; } // Even case (with no central item) L = i; R = i + 1; while (L >= 0 && R < array.length) { if (array[L] > array[R]) swap(array,R); L--; R++; } } } // Swap two items in array. public static void swap(int[] array,int y) { int temp = array[x]; array[x] = array[y]; array[y] = temp; } } public static class BubbleSort { public static void sort(int[] numbers) { boolean swapped = true; for (int i = numbers.length - 1; i > 0 && swapped; i--) { swapped = false; for (int j = 0; j < i; j++) { if (numbers[j] > numbers[j + 1]) { int temp = numbers[j]; numbers[j] = numbers[j + 1]; numbers[j + 1] = temp; swapped = true; } } } } } public static class TestDataFactory { public static enum ElementOrder { Ascending,Descending,Random } public static int[] createIntArray(final int size,final ElementOrder elementOrder) { int[] array = new int[size]; switch (elementOrder) { case Ascending: for (int i = 0; i < size; ++i) array[i] = i; break; case Descending: for (int i = 0; i < size; ++i) array[i] = size - i - 1; break; case Random: default: Random rg = new Random(System.nanoTime()); for (int i = 0; i < size; ++i) array[i] = rg.nextInt(size); break; } return array; } } public static class Benchmark { // misc constants public static final int NANOS_PER_MSEC = 1000000; // config constants public static final int BIGDECIMAL_PRECISION = 6; // constant defaults public static final long AUTOTUNING_MIN_ITERATIONS_DEFAULT = 1; public static final long AUTOTUNING_MIN_DURATION_DEFAULT = 125; public static final long BENCHMARK_MIN_ITERATIONS_DEFAULT = 1; public static final long BENCHMARK_MAX_ITERATIONS_DEFAULT = Integer.MAX_VALUE; public static final long BENCHMARK_TARGET_DURATION_DEFAULT = 125; // private static final ThreadMXBean threadBean = // ManagementFactory.getThreadMXBean(); public static final long getNanoTime() { // return threadBean.getCurrentThreadcpuTime();// not good,runs at // some time slice resolution return System.nanoTime(); } public static class Result { public String name; public long iterations; public long totalTime; // nanoseconds public Result(String name,long iterations,long startTime,long endTime) { this.name = name; this.iterations = iterations; this.totalTime = endTime - startTime; } @Override public String toString() { final double totalTimeMSecs = ((double) totalTime) / NANOS_PER_MSEC; final BigDecimal avgTimeMsecs = new BigDecimal(this.totalTime).divide(new BigDecimal(this.iterations).multiply(new BigDecimal(NANOS_PER_MSEC)),BIGDECIMAL_PRECISION,RoundingMode.HALF_UP); final String newLine = System.getProperty("line.separator"); StringBuilder sb = new StringBuilder(); sb.append(name).append(newLine); sb.append(" ").append("iterations : ").append(iterations).append(newLine); sb.append(" ").append("total time : ").append(totalTimeMSecs).append(" ms").append(newLine); sb.append(" ").append("avg time : ").append(avgTimeMsecs).append(" ms").append(newLine); return sb.toString(); } } public static <T> Result executionTime(final String name,final long iterations,final long warmupIterations,final Callable<T> test) throws Exception { // vars @SuppressWarnings("unused") T ret; long startTime; long endTime; // warmup for (long i = 0; i < warmupIterations; ++i) ret = test.call(); // actual benchmark iterations { startTime = getNanoTime(); for (long i = 0; i < iterations; ++i) ret = test.call(); endTime = getNanoTime(); } // return result return new Result(name,iterations,startTime,endTime); } /** * Auto tuned execution time measurement for test callbacks with steady * execution time * * @param name * @param test * @return * @throws Exception */ public static <T> Result executionTimeAutotuned(final String name,final Callable<T> test) throws Exception { final long autoTuningMinIterations = AUTOTUNING_MIN_ITERATIONS_DEFAULT; final long autoTuningMinDuration = AUTOTUNING_MIN_DURATION_DEFAULT; final long benchmarkTargetDuration = BENCHMARK_TARGET_DURATION_DEFAULT; final long benchmarkMinIterations = BENCHMARK_MIN_ITERATIONS_DEFAULT; final long benchmarkMaxIterations = BENCHMARK_MAX_ITERATIONS_DEFAULT; // vars @SuppressWarnings("unused") T ret; final int prevThreadPriority; long warmupIterations = 0; long autoTuningDuration = 0; long iterations = benchmarkMinIterations; long startTime; long endTime; // store current thread priority and set it to max prevThreadPriority = Thread.currentThread().getPriority(); Thread.currentThread().setPriority(Thread.MAX_PRIORITY); // warmup and iteration count tuning { final long autoTuningMinTimeNanos = autoTuningMinDuration * NANOS_PER_MSEC; long autoTuningConsecutiveLoops = 1; double avgExecutionTime = 0; do { { startTime = getNanoTime(); for (long i = 0; i < autoTuningConsecutiveLoops; ++i,++warmupIterations) { ret = test.call(); } endTime = getNanoTime(); autoTuningDuration += (endTime - startTime); } avgExecutionTime = ((double) autoTuningDuration) / ((double) (warmupIterations)); if ((autoTuningDuration >= autoTuningMinTimeNanos) && (warmupIterations >= autoTuningMinIterations)) { break; } else { final double remainingAutotuningIterations = ((double) (autoTuningMinTimeNanos - autoTuningDuration)) / avgExecutionTime; autoTuningConsecutiveLoops = Math.max(1,Math.min(Integer.MAX_VALUE,(long) Math.ceil(remainingAutotuningIterations))); } } while (warmupIterations < Integer.MAX_VALUE); final double requiredIterations = ((double) benchmarkTargetDuration * NANOS_PER_MSEC) / avgExecutionTime; iterations = Math.max(1,Math.min(benchmarkMaxIterations,(long) Math.ceil(requiredIterations))); } // actual benchmark iterations { startTime = getNanoTime(); for (long i = 0; i < iterations; ++i) ret = test.call(); endTime = getNanoTime(); } // restore prevIoUs thread priority Thread.currentThread().setPriority(prevThreadPriority); // return result return new Result(name,endTime); } } public static void executeBenchmark(int inputSize,ArrayList<Benchmark.Result> results) { // final int[] inputArray = { 15,// 10,12 }; final int[] inputArray = TestDataFactory.createIntArray(inputSize,TestDataFactory.ElementOrder.Random); try { // compare against Arrays.sort() { final int[] ref = inputArray.clone(); Arrays.sort(ref); { int[] temp = inputArray.clone(); BubbleSort.sort(temp); if (!Arrays.equals(temp,ref)) throw new Exception("BubbleSort.sort() Failed"); } { int[] temp = inputArray.clone(); OrbitSort.sort(temp); if (!Arrays.equals(temp,ref)) throw new Exception("OrbitSort.sort() Failed"); } } results.add(Benchmark.executionTimeAutotuned("Arrays.sort()",new Callable<Void>() { @Override public Void call() throws Exception { int[] temp = Arrays.copyOf(inputArray,inputArray.length); Arrays.sort(temp); return null; } })); results.add(Benchmark.executionTimeAutotuned("BubbleSort.sort()",inputArray.length); BubbleSort.sort(temp); return null; } })); results.add(Benchmark.executionTimeAutotuned("OrbitSort.sort()",inputArray.length); OrbitSort.sort(temp); return null; } })); } catch (Exception e) { e.printStackTrace(); } } public static void main(String[] args) { ArrayList<Benchmark.Result> results = new ArrayList<Benchmark.Result>(); for (int i = 16; i <= 16384; i <<= 1) { results.clear(); executeBenchmark(i,results); System.out.println("input size : " + i); System.out.println(""); for (Benchmark.Result result : results) { System.out.print(result.toString()); } System.out.println("----------------------------------------------------"); } } }