Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is this a new sorting algorithm? [with Java and Pseudo-code implementation]

I know this may be a stupid question, maybe the most stupid question today, but I have to ask it: Have I invented this sorting algorithm?

Yesterday, I had a little inspiration about an exchange-based sorting algorithm. Today, I implemented it, and it worked.

It probably already exists, since there are many not-so-popular sorting algorithms out there that has little or none information about, and almost no implementation of them exist.

Description: Basically, this algorithm takes an item, them a pair, then an item again... until the end of the list. For each item/pair, compare EVERY two items at the same radius distance from pair space or item, until a border of the array is reached, and then exchange those items if needed. Repeat this for each pair/item of the list.

An English-based 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 the implementation in Java:

//package sorting;

public class OrbitSort {
    public static void main(String[] args) {
        int[] numbers ={ 15, 8, 6, 3, 11, 1, 2, 0, 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, L, 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 can be shorter, but it's just an early implementation.

It probably runs in O(n^2), but I'm not sure.

So, what do you think? Does it already exists?

like image 725
Josell Avatar asked Jan 05 '13 17:01

Josell


People also ask

Which sorting algorithm is used in Java?

sort uses dual-pivot Quicksort on primitives. It offers O(n log(n)) performance and is typically faster than traditional (one-pivot) Quicksort implementations. However, it uses a stable, adaptive, iterative implementation of mergesort algorithm for Array of Objects.

What is the newest sorting algorithm?

In this paper, we are introducing a new sorting algorithm called RevWay sort in which the two consecutive numbers are compared from left and then from right. This process is repeated ((n/2)+1) times, where n is the total number of elements.

Which is the most efficient sorting algorithm in Java?

Quicksort. Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.

Does Java have a sort method?

Java sort() In Java, the collections framework provides a static method sort() that can be used to sort elements in a collection. The sort() method of the collections framework uses the merge sort algorithm to sort elements of a collection. The merge sort algorithm is based on divide and conquers rule.


2 Answers

To me, it looks like a modified bubble sort algo, which may perform better for certain arrangements of input elements. Altough not necessarily fair, I did a benchmark with warmup cycles using your input array, for comparison of:

  • java.util.Arrays.sort(), which is a merge quick sort implementation
  • BubbleSort.sort(), a java implementation of the bubble sort algo
  • OrbitSort.sort(), your algo

Results:

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, the performance depends on input size and arrangement

Straightforward 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, 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, L, 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;
        }
    }

    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, iterations, startTime, endTime);
        }
    }

    public static void executeBenchmark(int inputSize, ArrayList<Benchmark.Result> results) {
        // final int[] inputArray = { 15, 8, 6, 3, 11, 1, 2, 0, 14, 13, 7, 9, 4,
        // 10, 5, 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()", new Callable<Void>() {
                @Override
                public Void call() throws Exception {
                    int[] temp = Arrays.copyOf(inputArray, inputArray.length);
                    BubbleSort.sort(temp);
                    return null;
                }
            }));
            results.add(Benchmark.executionTimeAutotuned("OrbitSort.sort()", new Callable<Void>() {
                @Override
                public Void call() throws Exception {
                    int[] temp = Arrays.copyOf(inputArray, 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("----------------------------------------------------");
        }

    }
}
like image 143
Sam Avatar answered Nov 15 '22 15:11

Sam


It is O(n^2) (assuming it works, I am not sure about that), as to already exists - maybe - it is not really original, as it can be considered a variation of a trivial sorting implementation, but I doubt if there is any published algorithm which is exactly the same as this one, specifically one with two consecutive inner loops.

I am not saying it is without merit, there can be a use case for which its behavior is uniquely efficient (maybe where reading is much faster than writing, and cache behavior benefits its access pattern).

To see why it is O(n^2), think about the first n/6 outer loop iterations, the inner loops run on O(n) length O(n) times.

like image 39
Ofir Avatar answered Nov 15 '22 16:11

Ofir