Блог

Я начинающий программист, и я придумал алгоритм сортировки (DexSort), который обычно работает намного быстрее, чем стандартная быстрая сортировка. Предполагается, что количество ВСЕХ ВОЗМОЖНЫХ значений в наборе / массиве меньше N ^ 2, где N — количество элементов, которые я пытаюсь отсортировать. Я пытаюсь найти способ оптимизировать его, чтобы он не обязательно зависел от ВСЕХ ВОЗМОЖНЫХ ЗНАЧЕНИЙ и только от подмножества значений, которые имеют отношение.

Например …. скажем, у меня есть массив случайных чисел, где array.length = 10 миллионов. Мой алгоритм работает только быстрее, чем быстрая сортировка (в среднем), когда общее количество всех возможных значений меньше N ^ 2 (т. е. 10^7 * 10^7 = 10 ^ 14). Теперь, скажем, есть 10 ^ 14 фактических значений, которые можно найти в массиве. В этот момент мой алгоритм будет выполняться примерно со скоростью O (10 ^ 14). Может кто-нибудь придумать способ, где я мог бы уменьшить это?

Вот мой код на Java:

 package sort;

import java.util.*;

public class DexSort {

public static Comparable[] dexSort(Comparable[] c, int max){
    //The variable int max is the maximum number of possible values
    //E.g.  If you are trying to sort 7-digit phone numbers, max = Math.pow(10,8) - 1, or 10^8 - 1

    int size = c.length;
    Comparable[] sorted = new Comparable[size];
    int[] array = new int[max 1];

    for (int i = 0; i < size; i  ){
        int val = (int) c[i];
        int count = array[val];
        count  ;
        array[val] = count;
    }

    int next = 0;
    while (next < size){
        for (int i = 0; i <= max; i  ){
            int count = array[i];
            if (count > 0){
                for (int j = 0; j < count; j  ){
                    sorted[next] = i;
                    next  ;
                }
            }
        }
    }
    return sorted;
}

public static void main(String[] args){

    Random r = new Random(7);

    for (double n = 4; n < 8; n  ){

        double size = Math.pow(10, n);
        System.out.println("---------------------------------------------");
        System.out.println("Filling array size: 10^"   n);
        System.out.println("---------------------------------------------n");

        Comparable[] array = fillArray((int)size, r);   //Create array of random numbers of specified size
        System.out.println("Array filled");         //Tests different array sizes by incrementing a power of 10
        System.out.println("---------------------------------------------n");

        double max = size;  //Arbitrarily set the maximum value possible as the array size
                            //Runtime will depend heavily on max if max>>>> size (See dexSort method)
                            //Overall, runtime will be O(max) when max >>>>> size

        double t0 = System.nanoTime();
        array = dexSort(array, (int) max);
        double tF = System.nanoTime();

        double nanoSecs = tF - t0;
        double secs = nanoSecs/Math.pow(10, 9);

        System.out.println("DEX sort complete");
        System.out.println("It took "   String.format("%.3f", secs)   " seconds to sort an array of size 10^"   n);

        //printArray(array);  //Uncomment this line to print sorted array to console
        System.out.println();
        System.out.println("---------------------------------------------");
        System.out.println("---------------------------------------------nn");
    }
}

public static Comparable[] fillArray(int size, Random r){
    Comparable[] c = new Comparable[size];
    for (int i = 0; i < size; i  ){
        /*if ((i 1)000000 == 0){
            System.out.println(((i 1)/1000000)   " million filled");
        }*/
        c[i] = r.nextInt(size) 1;
    }
    return c;
}


public static void printArray(Comparable[] c){
    for (int i = 0; i < c.length; i  ){
        if (i == 0){
            System.out.println();
        }
        System.out.print(c[i]   "t");
    }
}

}