Сортировка вставкой в хэш-таблицу

Предлагаю вашему вниманию новый (как я думаю) алгоритм сортировки. Пытался искать похожее, но аналогов не увидел. Дайте знать, если видели что-то подобное.
Суть сортировки в том, что хэш-функция и разрешение коллизий построены таким образом, что в хэш-таблице данные оказываются уже в отсортированном виде. Остаётся только пробежаться по массиву хэш-таблицы и собрать непустые отсортированные данные.

Кому интересно – прошу под кат.

Итак, алгоритм работает следующим образом:

1. На первом проходе находим минимальное и максимальное значения исходных данных для подсчёта коэффициента хэш-функции проецирования значений в диапазон индексов хэш-таблицы (A_min, A_max).
2. На втором проходе вставляем исходные значения в хэш-таблицу, вычисляя индекс с помощью хэш-функции index=(int)(k*(A_i-A_min)*TMPLEN/(A_max-A_min)).
3. На третьем проходе идём по хэш-таблице и копируем отсортированные данные в исходный массив.

Для разрешения коллизий используется пропуск занятых ячеек (если вставляемое значение <= записанного в таблицу) и сдвиг вправо части таблицы (до первой свободной ячейки), если надо вставить на место, где значение больше.

Временный массив для хэш-таблицы в 2-3 раза больше, чем исходный массив. Благодаря этому можно оптимизировать разрешение коллизий и использовать только сдвиг вправо.

Алгоритм относится к классу устойчивых сортировок, с комбинированием сравнения и вычисления.

Вычислительная сложность – от O(n*log n) (как я понял при сравнении с быстрой сортировкой, встроенной в Java) до O(n*n) в худшем случае. Если вы владеете матаппаратом, то сможете вывести это формально. Я уже всё позабыл. Жду ваших соображений в комментариях.

При равномерном распределении обнаружил, что алгоритм работает на 20-25% быстрее быстрой сортировки!

Затраты памяти – O(n).

Сравнивая с быстрой сортировкой я обнаружил, что при малом количестве значений исходных данных алгоритм сильно деградирует, так как приходится разрешать очень много коллизий.
Однако, комбинируя со слиянием (сортируя блоками по 500 значений), я добился производительности, соизмеримой с быстрой сортировкой, и большей, чем с чистым слиянием.

Преимущества:

• хорошо параллелится (при использовании нерекурсивного слияния блоков);
• производительность соизмерима с быстрой сортировкой;
• если известно распределение, то можно подкорректировать хэш-функцию для оптимизации заполнения хэш-таблицы.

Недостатки:

• многовато памяти требует;
• в малом диапазоне значений или при сильно неравномерном распределении производительность деградирует.

Не знаю, пригодится ли этот алгоритм на практике, но для академического изучения точно не помешает.

Мой исходный код для тестирования на Java.

Играя параметрами можно потестировать в разных режимах. Например, если установить SORTBLOCK=SOURCELEN, то будет применён чистый хэширующий алгоритм. С помощью MIN_VAL и MAX_VAL можно задать диапазон значений для генерации случайных чисел.

При SOURCELEN<300 отсортированные данные выводятся в консоль. За пустое значение в массиве я выбрал ноль, поэтому не стоит включать его в диапазон.

А понимаю, что измерение производительности не совсем корректно. Но для предварительной оценки вполне сгодится. Когда будет время — попробую на специальном фреймворке, как коллеги советуют.

import java.util.Arrays;
import java.util.Date;
import java.util.Random;

public class HashSort {

    // Размер массива исходных данных
    static int SOURCELEN = 1000000;
    int source[] = new int[SOURCELEN];
    
    // Копия исходных данных для сравнения с быстрой сортировкой
    int quick[] = new int[SOURCELEN];
    
    // Размер блока для хэширующей сортировки
    static int SORTBLOCK = 500;
    static int k = 3;
    
    // Временный массив
    static int TMPLEN = (SOURCELEN < SORTBLOCK * k) ? SORTBLOCK * k : SOURCELEN;
    int tmp[] = new int[TMPLEN];
    
    // Диапазон значений исходных данных
    static int MIN_VAL = 10;
    static int MAX_VAL = 1000000;

    int minValue = 0;
    int maxValue = 0;    
    double hashKoef = 0;
    
    long finishTime = 0;
    long startTime = 0;
    long finishTimeQuick = 0;
    long startTimeQuick = 0;
    
    // Заполнение массива исходных данных случайными значениями
    public void randomize() {
        int i;
        Random rnd = new Random();
        for(i=0; i<SOURCELEN; i++) {
            int rndValue = MIN_VAL + ((int)(rnd.nextDouble()*((double)MAX_VAL-MIN_VAL))); 
            source[i] = rndValue;
        }
    }

    // Поиск минимального и максимального значений плюс вычисление коэффициента для хэш-функции
    public void findMinMax(int startIndex, int endIndex) {
        int i;
        minValue = source[startIndex];
        maxValue = source[startIndex];
        for(i=startIndex+1; i<=endIndex; i++) {
            if( source[i] > maxValue) {
                maxValue = source[i];
            }
            if( source[i] < minValue) {
                minValue = source[i];
            }            
        }
        hashKoef = ((double)(k-1)*0.9)*((double)(endIndex-startIndex)/((double)maxValue-(double)minValue));
    }    
    
    // Склеивание двух смежных отсортированных частей массива
    public void stickParts(int startIndex, int mediana, int endIndex) {
        int i=startIndex;
        int j=mediana+1;
        int k=0;
        while(i<=mediana && j<=endIndex) {
            if(source[i]<source[j]) {
                tmp[k] = source[i];
                i++;
            } else {
                tmp[k] = source[j];
                j++;
            }
            k++;
        }
        
        if( i>mediana ) {
            while(j<=endIndex) {
                tmp[k] = source[j];
                j++;
                k++;
            }
        }
        if(j>endIndex) {
            while(i<=mediana) {
                tmp[k] = source[i];
                i++;
                k++;
            }
        }
        
        System.arraycopy(tmp, 0, source, startIndex, endIndex-startIndex+1);
    }
    
    // Сдвиг вправо во временном массиве для разрешения коллизий
    boolean shiftRight(int index) {
        
        int endpos = index;
        while( tmp[endpos] != 0) {
            endpos++;
            if(endpos == TMPLEN) return false;
        }
        
        while(endpos != index ) {
            tmp[endpos] = tmp[endpos-1];
            endpos--;
        }
               
        tmp[endpos] = 0;
        
        return true;
    }    

    // хэш-функция для хэширующей сортировки
    public int hash(int value) {
        return (int)(((double)value - (double)minValue)*hashKoef);
    }
    
    // вставка значений во временный массив с разрешением коллизий
    public void insertValue(int index, int value) {
        int _index = index;
        while(tmp[_index] != 0 && tmp[_index] <= value) { _index++; }
        if( tmp[_index] != 0) {
            shiftRight(_index);
        }
        tmp[_index] = value;
    }
    
    // копирование отсортированных данных из временного массива в исходный
    public void extract(int startIndex, int endIndex) {
        int j=startIndex;
        for(int i=0; i<(SORTBLOCK*k); i++) {
            if(tmp[i] != 0) {
                source[j] = tmp[i];
                j++;
            }
        }
    }    
    
    public void clearTMP() {
        
        if( tmp.length < SORTBLOCK*k) {
            Arrays.fill(tmp, 0);
        } else {
            Arrays.fill(tmp, 0, SORTBLOCK*k, 0);
        }
    }
    
    // Хэширующая сортировка
    public void hashingSort(int startIndex, int endIndex) {
        
        // 1. Поиск минимального и максимального значения с вычислением хэширующего коэффициента
        findMinMax(startIndex, endIndex);
        
        // 2. Очистка временного массива
        clearTMP();
        
        // 3. Вставка во временный массив с использованием хэш-функции
        for(int i=startIndex; i<=endIndex; i++) {
            insertValue(hash(source[i]), source[i]);
        }
        
        // 4. Перемещение отсортированных данных из временного массива в исходный
        extract(startIndex, endIndex);
    }
    
    // Рекурсивный спуск с дихотомией до уровня блока хэширующей сортировки 
    public void sortPart(int startIndex, int endIndex) {
        if( (endIndex - startIndex) <= SORTBLOCK ) {
           hashingSort(startIndex, endIndex);
           return;
        }
        
        int mediana = startIndex + (endIndex - startIndex) / 2;
        sortPart(startIndex, mediana);
        sortPart(mediana+1, endIndex);
        stickParts(startIndex, mediana, endIndex);
    }
    
    public void sort() {
        sortPart(0, SOURCELEN-1);
    }
    
    // Отображение результатов
    public String toString() {
        int i;
        String res = "";
        
        res += "Source:";
        if( SOURCELEN < 300) {
            for(i=0; i<SOURCELEN; i++) {
                res += " " + source[i];
            }
        }
        
        res += "n";

        res += "Quick: ";
        if( SOURCELEN < 300) {
            for(i=0; i<SOURCELEN; i++) {
                res += " " + quick[i];
            }
        }
        
        res += "n";
        
        res += "len: " + SOURCELEN + "n";
        
        res += "hashing&merge sort time: " + (finishTime - startTime) + "n";
        
        res += "quick sort time: " + (finishTimeQuick - startTimeQuick) + "n";
        
        return res;
    }        
    
    // Копирование исходных данных для сравнения с быстрой сортировкой
    public void copyToQuick() {
        System.arraycopy(source, 0, quick, 0, source.length);
    }
    
    public static void main(String[] args) {

        HashSort hs = new HashSort();
        
        hs.randomize();
        hs.copyToQuick();
        
        hs.startTime = (new Date()).getTime();
        hs.sort();
        hs.finishTime = (new Date()).getTime();
        
       
        hs.startTimeQuick = (new Date()).getTime();
        Arrays.sort(hs.quick);
        hs.finishTimeQuick = (new Date()).getTime();
        
        System.out.println(hs.toString());
    }

}

Автор: bobbyKdas

Источник ^[1]