Підрахунок з приблизним розподілом — найчастіше переизобретаемая сортування

Alex Alex 04 грудня 2019

Підрахунок з приблизним розподілом — найчастіше переизобретаемая сортування

Кількість більш-менш відрізняються один від одного сортувань гарантовано більше сотні. Серед них є підгрупи алгоритмів, мінімально відрізняються один від одного, співпадаючи в якійсь загальній головній ідеї. Фактично в різні роки різними людьми придумуються заново одні і ті ж сортування, розрізняються в не надто принципових деталях.

Частіше інших зустрічається ось така алгоритмічна ідея.

Кожен елемент заноситься приблизно в те місце масиву, де він повинен знаходитися. Виходить майже впорядкований масив. До якого або застосовується сортування вставками (вона найефективніша для обробки майже впорядкованих масивів) або локальні невпорядковані області обробляються рекурсивно цим же алгоритмом.

EDISON Software - web-development
Стаття написана за підтримки компанії EDISON Software, розробляє широкий спектр рішень для різноманітних завдань: від програм для онлайн-примірки одягу мультибрендових магазинів до світлодіодним системи передачі між річковими та морськими суднами.

Ми дуже любимо теорію алгоритмів! ;-)
Щоб оцінити, приблизно куди потрібно поставити елемент, потрібно з'ясувати, наскільки він відрізняється від середньостатистичного елемента масиву. Для цього потрібно знати значення мінімального і максимального елементів, ну і розмір масиву.

Передбачається, що в сортируемом масиві дійсно випадкові дані. Всі винахідники даного методу приходять до однієї і тієї ж формулою:


k — приблизне місце в масиві, де повинен знаходитися елемент A(i)
min, max — значення мінімального і максимального елементів у масиві A
Size — кількість елементів у масиві A

Ось така загальна ідея. Давайте подивимося, в яких варіаціях цей алгоритм народжувався знову і знову.

Сортування царя Соломона :: Solomon sort



Цей спосіб (і його гарна назва) запропонував хабрапользователь V2008n років 5 тому. Всьому свій час, «час розкидати каміння і час збирати каміння» (слова царя Соломона з книги Еклезіяста) — а в алгоритмі, власне, так і відбувається. Спочатку за допомогою формули раскидываем елементів по потрібних місцях масиву. Оскільки формула не дає точне, а приблизне місце, то на деякі позиції претендують відразу декілька елементів, близьких один до одного за значенням. Ці локальні групи елементів сортуються вставками і потім збираються в остаточному порядку.

Сортування інтерполяцією :: Interpolation sort


«Немає нічого нового під сонцем», якщо знову процитувати того ж автора. У Вікіпедії описана сортування інтерполяцією, підозріло нагадує соломона сортування. Кожна купка каміння» — це невеликий додатковий динамічний масив, де перебувають близькі за значенням елементи. Головна відмінність — після «розкидання каміння» ці локальні неотсортированные групи елементів сортуються не вставками, а самій же сортуванням інтерполяцією (рекурсивно або в циклі).

Впорядкований масив являє собою дискретний набір даних, який можна розглядати як кінцеву безліч відомих значень якоїсь невідомої функції. Власне, приблизний розподіл з точки зору обчислювальної математики — це інтерполяція і є.

Сортування інтерполяцією на JavaScript - циклічна версія
Array.prototype.interpolationSort = function() {

var divideSize = new Array();
var end = this.length;
divideSize[0] = end;

while(divideSize.length > 0) 

function divide(A) {

var size = divideSize.pop();
var start = end - size;
var min = A[start];
var max = A[start];
var temp = 0;

for(var i = start + 1; i < end; i++) {
if(A[i] < min) {
min = A[i];
} else {
if(A[i] > max) 
}
}

if(min == max) {

end = end - size;

} else {

var p = 0;
var bucket = new Array(size);

for(var i = 0; i < size; i++) 

for(var i = start; i < end; i++) {
p = Math.floor(((A[i] - min) / (max - min)) * (size - 1));
bucket[p].push(A[i]);
}

for(var i = 0; i < size; i++) {
if(bucket[i].length > 0) {
for(var j = 0; j < bucket[i].length; j++) 
divideSize.push(bucket[i].length);
}
}
}
}
};

Сортування інтерполяцією на JavaScript - рекурсивна версія
Array.prototype.bucketSort = function() {

var start = 0;
var size = this.length;
var min = this[0];
var max = this[0];

for(var i = 1; i < size; i++) {
if (this[i] < min) {
min = this[i];
} else {
if(this[i] > max) 
}
}

if(min != max) {

var bucket = new Array(size);

for(var i = 0; i < size; i++) 

var interpolation = 0;

for(var i = 0; i < size; i++){
interpolation = Math.floor(((this[i] - min) / (max - min)) * (size - 1));
bucket[interpolation].push(this[i]);
}

for(var i = 0; i < size; i++) {
if(bucket[i].length > 1) //Recursion
for(var j = 0; j < bucket[i].length; j++) 
}

}
};

Гистограмная сортування :: Histogram sort


Це оптимізація сортування інтерполяцією, в якій підраховується кількість елементів, що належать до локальним неотсортированным групам. Цей підрахунок дозволяє вставляти неотсортированные предмети безпосередньо в підсумковий масив (замість групування за окремим невеликим масивів).

Гистограмная сортування на JavaScript
Array.prototype.histogramSort = function() {

var end = this.length;
var sortedArray = new Array(end);
var interpolation = new Array(end);
var hitCount = new Array(end);
var divideSize = new Array();

divideSize[0] = end;

while(divideSize.length > 0) 

function distribute(A) {

var size = divideSize.pop();
var start = end - size;
var min = A[start];
var max = A[start];

for(var i = start + 1; i < end; i++) {
if (A[i] < min) {
min = A[i];
} else {
if (A[i] > max) 
}
}

if (min == max) {

end = end - size;

} else {

for(var i = start; i < end; i++)

for(var i = start; i < end; i++) {
interpolation[i] = start + Math.floor(((A[i] - min) / (max - min)) * (size - 1));
hitCount[interpolation[i]]++;
}

for(var i = start; i < end; i++) {
if(hitCount[i] > 0)
}
hitCount[end - 1] = end - hitCount[end - 1];

for(var i = end - 1; i > start; i--) {
hitCount[i - 1] = hitCount[i] - hitCount[i - 1];
}

for(var i = start; i < end; i++) {
sortedArray[hitCount[interpolation[i]]] = A[i];
hitCount[interpolation[i]]++;
}

for(var i = start; i < end; i++) 

}
}
};

Сортування інтерполяцією з мітками


Щоб ще більше оптимізувати накладні витрати, тут пропонується запам'ятовувати не кількість близьких за значенням елементів в неотсортированных групах, а просто позначити прапорцями True/False початок цих груп. True означає що підгрупа вже відсортована, а False — що ще немає.

Сортування інтерполяцією з мітками на JavaScript
Array.prototype.InterpolaionTagSort = function() {

var end = this.length; 
if(end > 1) { 
var start = 0 ; 
var Tag = new Array(end); //Algorithm step-1 
for(var i = 0; i < end; i++) 
Divide(this); 
}

//Algorithm step-2
while(end > 1) {
while(Tag[--start] == false){} //Find the next bucket's start
Divide(this); 
} 

function Divide(A) { 

var min = A[start]; 
var max = A[start];

for(var i = start + 1; i < end; i++) { 
if(A[i] < min) {
min = A[i];
} else {
if(A[i] > max ) 
}
}

if(min == max) {

end = start;

} else {

//Algorithm step-3 Start to be the next bucket's end 
var interpolation = 0; 
var size = end - start; 
var Bucket = new Array(size);//Algorithm step-4 

for(var i = 0; i < size; i++) 

for(var i = start; i < end; i++) { 
interpolation = Math.floor(((A[i] - min) / (max - min)) * (size - 1));
Bucket[interpolation].push(A[i]); 
} 

for(var i = 0; i < size; i++) {
if(Bucket[i].length > 0) {//Algorithm step-5 
Tag[start] = true; 
for(var j = 0; j < Bucket[i].length; j++) 
} 
} 
}
}//Algorithm step-6 
};

Сортування інтерполяцією з мітками (на місці)


Якщо значення елементів у масиві не повторюються і рівномірно розподілені (грубо кажучи — якщо дані у відсортованому вигляді представляють із себе щось на зразок арифметичної прогресії), то можна відсортувати в один прохід, сортуючи прямо на місці, не переміщаючи елементи в проміжні масиви.

Сортування інтерполяцією з мітками (на місці) на JavaScript
Array.prototype.InPlaceTagSort = function() {

var n = this.length;
var Tag = new Array(n);

for(i = 0; i < n; i++) 

var min = this[0];
var max = this[0];

for(i = 1; i < n; i++) {
if(this[i] < min) {
min = this[i];
} else {
if(this[i] > max) 
}
} 

var p = 0;
var temp = 0;

for(i = 0; i < n; i++) {
while(Tag[i] == false) { 
p = Math.floor(((this[i] - min) / (max - min)) * (n - 1));
temp = this[i];
this[i] = this[p]; 
this[p] = temp;
Tag[p] = true;
} 
} 
};

Флеш-сортування :: Flashsort


Давним-давно я вже писав про сортування, яку придумав професор біофізики Нойберт в 1998 році.

Професор запропонував розподілити елементи з кількома окремими класами (приналежність до класу визначається розміром елемента). З урахуванням цього формула виглядає так:


Замість Size (розмір масиву) у формулі зазначено m — кількість класів, за яким розподіляємо елементи масиву. Формула обчислює не ключ в масиві, куди треба перекинути елемент, а номер класу, до якого елемент відноситься.

Ця сортування непогана тим, що більш ощадливо ставиться до додаткової пам'яті. Перерозподіл елементів відбувається на місці. Окремо зберігаються тільки локалізації класів (ну, якщо подивитися під іншим ракурсом — окремо зберігаються кількості елементів, що належать до того чи іншого класу).

Ну, а в іншому — та ж сама пісня.


Flash-сортування на Java
/**
* FlashSort.java - integer version 
* Translation of Karl-Dietrich Neubert's algorithm into Java by 
* Rosanne Zhang
*/

class FlashSort {

static int n;
static int m;
static int[] a;
static int[] l;

/* constructor 
@param size of the array to be sorted */
public static void flashSort(int size) {

n = size;
generateRandomArray();

long start = System.currentTimeMillis();
partialFlashSort();
long mid = System.currentTimeMillis();
insertionSort();
long end = System.currentTimeMillis();

// print the time result
System.out.println("Partial flash sort time :" + (mid - start));
System.out.println("Straight insertion sort time:" + (end - mid));
}

/* Entry point */
public static void main(String[] args) {

int size = 0;

if (args.length == 0) {
usage();
System.exit(1);
}

try {
size = Integer.parseInt(args[0]); 
}

catch (NumberFormatException nfe) {
usage();
System.exit(1);
}

FlashSort.flashSort(size);
}

/* Print usage */

private static void usage() {
System.out.println();
System.out.println("Usage: java FlashSort n ");
System.out.println(" n is size of array to sort");
}

/* Generate the random array */
private static void generateRandomArray() {

a = new int[n];
for(int i=0; i < n; i++) {
a[i] = (int)(Math.random() * 5 * n);
}

m = n / 20;

l = new int[m]; 
}

/* Partial flash sort */

private static void partialFlashSort() {

int i = 0, j = 0, k = 0;
int anmin = a[0];
int nmax = 0;

for(i=1; i < n; i++) {
if (a[i] < anmin) anmin=a[i];
if (a[i] > a[nmax]) nmax=i; 
}

if(anmin == a[nmax]) return;

double c1 = ((double)m - 1) / (a[nmax] - anmin);

for(i=0; i < n; i++) {
k= (int) (c1 * (a[i] - anmin));
l[k]++;
}

for(k=1; k < m; k++) {
l[k] += l[k - 1];
}

int hold = a[nmax];
a[nmax] = a[0];
a[0] = hold;

int nmove = 0;
int flash;
j = 0;
k = m - 1;

while(nmove < n - 1) {

while(j > (l[k] - 1)) {
j++;
k = (int) (c1 * (a[j] - anmin));
}

flash = a[j];

while(!(j == l[k])) {

k = (int) (c1 * (flash - anmin));

hold = a[l[k] - 1];
a[l[k] - 1] = flash;
flash = hold;

l[k]--;
nmove++;

}
}
}

/* Straight insertion sort */
private static void insertionSort() {

int i, j, hold;

for(i = a.length - 3; i >= 0; i--) {

if(a[i + 1] < a[i]) {

hold = a[i];
j = i;

while (a[j + 1] < hold) {
a[j] = a[j + 1];
j++;
}

a[j] = hold;
}
}
}

/* For checking sorting result and the distribution */
private static void printArray(int[] ary) {

for(int i=0; i < ary.length; i++) {

if((i + 1) % 10 ==0) {
System.out.println(ary[i]);
} else {
System.out.print(ary[i] + " ");
}

System.out.println();
}
}
}

Сортування апроксимацією :: Proxmap sort


Ця сортування найдавніша тут згадуються, її в 1980 році представив професор Томас Стендіш з Університету Каліфорнії. З вигляду вона начебто суттєво відрізняється, однак, якщо придивитися, все те ж саме.

Алгоритм оперує таким поняттям як хіт — деяке число, близьке за значенням до деяких елементом масиву.
Щоб визначити, чи належить елемент масиву до хіту, до елемента застосовується апроксимирующая функція.

У професора Стендиша сортувалися масиви, що складаються з дійсних чисел. Апроксимирующей функцією було округлення дійсних чисел в меншу сторону до цілого числа.
Тобто, наприклад, якщо в масиві є елементи 2.8, 2, 2.1, 2.6 і т. п. то хітом саме для цих чисел буде двійка.



Загальний порядок дій:

  1. Застосовуємо апроксимує функцію до кожного елементу, визначаючи, яким хіту відповідає черговий елемент.
  2. Таким чином для кожного хіта можемо підрахувати кількість елементів, відповідних даним хіту.
  3. Знаючи кількості елементів для всіх хітів, визначаємо локалізації хітів (кордону ліворуч) у масиві.
  4. Знаючи локалізації хітів, визначаємо локалізацію кожного елемента.
  5. Визначивши локалізацію елемента, намагаємося вставити його на своє місце в масиві. Якщо місце вже зайняте, то або зрушуємо сусідів праворуч (якщо елемент менше їх), щоб звільнити місце для елемента. Або правіше вставляємо сам елемент (якщо він більше сусідів).

В якості апроксимуючої функції можна призначити яку завгодно, виходячи із загального характеру даних у масиві. В сучасних реалізаціях цієї сортування хіти зазвичай визначаються не шляхом відкушування дробової частини, а з допомогою нашої улюбленої формули.

Сортування апроксимацією на JavaScript
Array.prototype.ProxmapSort = function() {

var start = 0;
var end = this.length;
var A2 = new Array(end);
var MapKey = new Array(end);
var hitCount = new Array(end);

for(var i = start; i < end; i++) 

var min = this[start];
var max = this[start];
for (var i = start+1; i < end; i++){
if (this[i] < min) {
min = this[i];
} else {
if(this[i] > max) 
}
}

//Optimization 1.Save the MapKey[i].
for (var i = start; i < end; i++) {
MapKey[i] = Math.floor(((this[i] - min ) / (max - min)) * (end - 1));
hitCount[MapKey[i]]++;
}

//Optimization 2.ProxMaps store in the hitCount.
hitCount[end-1] = end - hitCount[end - 1];
for(var i = end-1; i > start; i--){
hitCount[i-1] = hitCount[i] - hitCount[i - 1];
}

//insert A[i]=this[i] to A2 correct position
var insertIndex = 0;
var insertStart = 0;
for(var i = start; i < end; i++){
insertIndex = hitCount[MapKey[i]];
insertStart = insertIndex;
while(A2[insertIndex] != null) 
while(insertIndex > insertStart && this[i] < A2[insertIndex - 1]) {
A2[insertIndex] = A2[insertIndex - 1];
insertIndex--;
}
A2[insertIndex] = this[i];
}
for(var i = start; i < end; i++) 
};

Сортування вставкою у хеш-таблицю :: Hash sort


Ну і закінчимо наш огляд алгоритмом, який запропонував хабраюзер bobbyKdas 6 років тому. Це гібридний алгоритм, який крім розподілу і вставок додано також злиття.

  1. Масив рекурсивно ділиться навпіл, поки на якомусь кроці розміри половинок-подмассивов не досягнуть мінімального розміру (у автора це не більше 500 елементів).
  2. На самому нижньому рівні рекурсії до кожній половинці-подмассиву застосовується знайомий алгоритм — з допомогою все тієї ж формули всередині подмассива відбувається приблизний розподіл, з сортуванням вставками локальних неотсортированных ділянок.
  3. Після упорядкування двох половинок-подмассивов відбувається їх злиття.
  4. Пункт 3 (злиття відсортованих половинок-подмассивов) повторюється при підйомі по рівням рекурсії до самого верху, коли з двох половинок об'єднується вихідний масив.

Сортування вставкою у хеш-таблицю на Java
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;

//Заповнення масиву випадковими значеннями вихідних даних
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) {

//Якщо розмір подмассива менше 500, то безпосередньо хеш-сортуємо
if((endIndex - startIndex) <= SORTBLOCK ) {
hashingSort(startIndex, endIndex);
return;
}

//Якщо розмір > 500 то ділимо навпіл і рекурсія до кожній половинці
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 static void main(String[] args) {
HashSort hs = new HashSort();
hs.randomize();
hs.sort();
}

}

Сама формула тут називається хеш-функцією, а допоміжний масив для приблизного розподілу — хеш-таблицею.

Посилання


Interpolation & Histogram, Flash, Proxmap

Соломон, Хеш-таблиця, Флеш

Статті серії:


В Excel-додаток AlgoLab з'явилася сортування апроксимацією (при цьому в початковому неотсортированном масиві до цілим числам дописується рандомная дробова частина). Соломон і Флеш там вже давно, а ось інтерполяцію, хеш та гістограму поки не реалізував.

Source: habr.com

Коментарі (0)

    Ще немає коментарів

Щоб залишити коментар необхідно авторизуватися.