Библиотечная сортировка




    Возьмём реверсно упорядоченный массив и применим к нему сортировку простыми вставками.



    Смотрите, с каким скрипом происходит вставка в нужное место очередного элемента. Для него нужно освободить место вставки, из-за чего приходится сдвигать все раннее вставленные элементы.

    А как было бы хорошо, если бы между раннее вставленными элементами были свободные места! Тогда не пришлось бы перетаскивать вереницы элементов только ради вставки одного.

    В 2004 году трое специалистов по computer science — Майкл Бендер, Мартин Фарах-Колтон и Мигель Мостейро — решили именно так и модифицировать сортировку простыми вставками. Они предложили формировать упорядоченную часть массива, оставляя зазоры между вставленными элементами.
    Библиотекарю необходимо, чтобы книги были расставлены по алфавиту на длинной полке: начиная слева от буквы «А», книги стоят впритык друг к другу до самой «Я». Если в библиотеку поступила новая книга, относящуюся к разделу «Б», то чтобы поставить её на полку в нужное место, придётся переместить каждую книгу, начиная где-то с середины раздела «Б» вплоть до последней «Я». Это сортировка простыми вставками. Однако, если бы библиотекарь резервировал свободное пространство в каждой секции, ему достаточно перемещать всего несколько книг, чтобы освобождать места для книжных новинок. Это основной принцип библиотечной сортировки.

    Алгоритм




    • 1. Создаём пустой вспомогательный массив, в несколько раз больший чем основной.
    • 2. Для очередного элемента ищем место вставки во вспомогательном массиве.
      • 2.1. Если нашли место для вставки, то переносим элемент и возвращаемся в пункт 2.
      • 2.2. Если места для вставки не нашлось, производим перебалансировку вспомогательного массива и возвращаемся в пункт 2.
    • 3. После обработки всех элементов переносим их обратно в основной массив.

    На первый взгляд кажется, что так сортировать легко и просто. Чтобы развеять эту иллюзию, ключевые пункты алгоритма рассмотрим подробнее.

    Размер вспомогательного массива


    Пока нет устоявшегося мнения, во сколько раз вспомогательный массив должен быть больше основного.

    Если взять слишком много — то между элементами будет достаточно много места, однако поиск места вставки и перебалансировка будут выполняться медленнее, ввиду больших расстояний между элементами. Перебалансировки будут случаться реже, но затрачивать ресурсы на них придётся больше. Если взять слишком мало, то поиск и перебалансировка будут обходиться дешевле, но переформатировать массив придётся чаще. В общем, тут ещё надо тестировать с разными значениями и методом научного тыка определить оптимальный вариант.

    Если мы определились, во сколько раз вспомогательный массив больше основного, то формула для определения точного количества элементов для него выглядит так:

    NewSize = ε × (Size + 1) − 1

    NewSize — количество элементов во вспомогательном массиве
    ε — во сколько раз вспомогательный массив больше основного
    Size — количество элементов в основном массиве


    Если мы просто умножим размер на коэффициент: NewSize = Size × ε, то для равномерного распределения нам не хватит ячеек в количестве ε − 1 штук. То есть, расположить то их равномерно удаётся, но или первая заполненная ячейка или последняя будут находиться впритык к краю вспомогательного массива. А нам нужно, чтобы пустые места у заполненных ячеек были зарезервированы со всех сторон — в том числе и перед первым элементом и после последнего.



    Вроде бы пустяк, но на самом деле это важно для перебалансировки, чтобы гарантировать свободные места для вставки в любом месте, в том числе и при обработке последних элементов основного массива.

    Поиск места вставки во вспомогательном массиве


    Разумеется, тут нужен бинарный поиск. Однако классическая реализация нам не подойдёт.

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

    Во-вторых, не забываем о краях. Если нужно вставить минимальный или максимальный элемент, то бинарный поиск среди раннее вставленных ни к чему не приведёт. Поэтому стоит предусмотреть граничные случаи — сначала проверить, не надо ли поставить элемент возле левой или правой границы массива и если нет, то уж тогда применять бинарный поиск.

    В-третьих, учитывая специфику применения, стоит внести дополнительные поправки, чтобы минимизировать количество перебалансировок массива. Если вставляемый элемент равен значению на одном из концов отрезка, то, пожалуй, не стоит вставлять в середину отрезка. Логичнее поставить рядом с равным ему по значению элементом. Это позволит эффективнее заполнять пустое пространство вспомогательного массива.

    Можно придумать в-четвёртых, в-пятых и так далее. Качество поиска места вставки прямо влияет на скорость сортировки, так как выбор неудачных мест для вставки приводит к лишним перебалансировкам. Например, может стоит делить отрезки не точно посередине, а ближе к левому или правому краю отрезка, в зависимости от того, к какому краю ближе по значению вставляемый элемент?

    Алгоритм бинарного поиска сам по себе таит подводные камни, а с учётом вышеозначенных дополнительных нюансов окончательно становится отнюдь нетривиальной задачей.

    Перебалансировка массива


    Бинарный поиск — не самое тяжкое, что нужно реализовать в этой сортировке. Есть ещё перебалансировка.

    Когда места для вставки нет (близкие по значению элементы найдены, но между ними не оказалось свободных ячеек) необходимо перетряхнуть вспомогательный массив так, чтобы место вставки освободилось. Это встряхивание массива и есть перебалансировка.

    Причём, перебалансировка бывает локальной или полной.

    Локальная перебалансировка


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

    Тут возможны нюансы. Например, в какой стороне искать ближайшее вакантное место? Чтобы избежать ситуации когда сдвиг невозможен (то есть, если в какую-то из сторон все ячейки заняты до самого края массива), можно ориентироваться на положение места вставки относительно середины массива. Если нужно вставить в левой части массива, то сдвигать вправо, если в правой — влево. Если ε ≥ 2, то такой подход исключает ситуацию, при которой сдвиг невозможен (ибо в половине вспомогательного массива хватает с лихвой места для всех элементов).

    В авторской интерпретации алгоритма подразумевается именно локальная перебалансировка.

    Полная перебалансировка


    Интересной альтернативой локальной является полная перебалансировка. То есть, во вспомогательном массиве сдвинуть все имеющиеся элементы таким образом, чтобы между ними были (почти) одинаковые промежутки.



    Я попробовал оба варианта и пока что наблюдаю, что при локальной перебалансировке алгоритм работает в 1,5-2 раза быстрее чем при полной. Впрочем, от полной перебалансировки всё равно может быть толк. Например, если локальную перебалансировку приходится делать чересчур часто, то это означает, что в массиве на отдельных участках накопилось много «тромбов», тормозящих весь процесс. Полная перебалансировка, проведённая разово, позволяет одним махом избавиться от всех локальных заторов.

    Разберём, как именно производить полную перебалансировку.

    Для начала нужно вычислить, сколько максимально ячеек мы можем выделить на каждый элемент во вспомогательном массиве. При этом нужно помнить, что пустые ячейки должны быть как перед первой, так и после последней заполненной ячейки. Формула такая:



    M — количество ячеек, которое можно выделить на каждый элемент
    NewSize — размер вспомогательного массива
    Count — текущее количество непустых элементов во вспомогательном массиве


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

    Зная M, мы легко получаем точную позицию для каждого непустого элемента во вспомогательном массиве, на котором он должен находиться после завершения перебалансировки.

    NewPos = Number × M

    NewPos — новая позиция элемента после перебалансировки
    Number — какой это по счёту непустой элемент во вспомогательном массиве (1 ≤ Number ≤ Count)
    M — количество ячеек, которое выделено на каждый элемент


    Новые позиции известны, можно просто во вспомогательном массиве перебрать непустые элементы и их перенести на другие места? О, нет, не спешите. Надо не просто попереносить элементы, важно сохранить их очерёдность. А в результате бинарного поиска и вставки элементы могут оказаться как сильно левее так и сильно правее той позиции, в которой они должны быть после перебалансировки. И на месте, куда нужно перенести, может стоять другой элемент, который тоже нужно куда-то пристроить. Кроме того, нельзя переносить элемент, если между его старой и новой позицией во вспомогательном массиве есть другие элементы — иначе элементы перемешаются, а нам крайне важно не перепутать порядок.

    Поэтому для перебалансировки недостаточно будет пройтись обычным циклом и просто переложить каждый элемент из одного кармана в другой. Придётся ещё задействовать рекурсию. Если элемент нельзя перенести на новое место (между его старой и новой позициями оказались другие элементы), то сначала нужно разобраться (рекурсивно) с этими непрошенными гостями. И тогда всё расставится правильно.

    Вырожденный случай


    Для большинства сортировок вставками реверсно упорядоченный массив — наихудшая ситуация. И сортировка библиотекаря, увы, не исключение.



    Элементы стремятся к левому краю вспомогательного массива, в результате чего свободные места быстро заканчиваются. Приходится очень часто делать перебалансировку массива.

    Кстати, если взять почти упорядоченный массив (наилучший случай для сортировки простыми вставками), то получим ту же проблему. Вновь поступающие элементы будут забивать не левую, а правую часть вспомогательного массива, что также приведёт к слишком частым перебалансировкам.

    Library sort эффективно обрабатывает наборы случайных данных. Частичная упорядоченность (как прямая, так и обратная) ухудшает скоростные показатели.

    Алгоритмическая сложность


    На больших наборах случайных данных алгоритм даёт временну́ю сложность O(n log n). Совсем неплохо!

    На наборах случайных уникальных (или в основном уникальных) данных при правильном подборе коэффициента ε и удачной реализации бинарного поиска количество перебалансировок можно свести к минимуму, а то и избежать их вовсе. Можно утверждать, что алгоритм имеет лучшую временную сложность O(n).

    Большой процент повторяющихся по значению данных, а также наличие в массиве упорядоченных (в прямом или обратном порядке) подпоследовательностей приводит к частым перебалансировкам вспомогательного массива и, как следствие, — к деградации временно́й сложности до O(n2) в наиболее неблагоприятных случаях.

    Минус алгоритма, конечно, в том, что на вспомогательный массив требуется O(n) дополнительной памяти.

    Возможные пути улучшения


    Хотя алгоритм сам по себе поучителен и эффективен на рандомных данных, за полтора десятилетия практически мало кто проявил к нему интерес.

    Если погуглить по запросу «library sort», то найдёте беглую статью в английской Википедии, авторский PDF (из которого мало что понятно) и редкий перепостинг этих скудных сведений. Плюс есть неплохая визуализация в Ютубе, где оригинально совместили основной и вспомогательный массивы. Все ссылки — в конце статьи.

    С поиском по запросу «библиотечная сортировка» ещё веселее — в выборке узнаете по разные сортировки, входящие в различные библиотеки, однако к аутентичной библиотечной сортировке эти алгоритмы не будут иметь отношения.

    А улучшать есть что:

    1. Эмпирический подбор оптимального коэффициента ε.
    2. Модификация (с учётом специфики общего алгоритма) бинарного поиска для максимально эффективного определения точки вставки.
    3. Минимизация расходов на перебалансировки.

    Если отшлифовать эти места, то, может, library sort по скорости даже сравняется с quick sort?

    Исходный код


    Реализацию на Python подготовить не успел, есть работающая версия на PHP.

    Основной алгоритм
    function LibrarySort($arr) {
    		
    	global $arr_new;//Вспомогательный массив
    		
    	$e = 3;//Во сколько раз увеличиваем массив
    	$rebalance_local = true;//Локальная (true) или полная (false) перебалансировка
    	
    	//Создаём вспомогательный массив
    	$newSize = $e * (count($arr) + 1) - 1;
    	$arr_new = array_fill(0, $newSize, null);
    		
    	//Первый элемент переносим в середину вспомогательного массива
    	$arr_new[LibrarySort_Pos(1, 1, $newSize)] = $arr[0];
    		
    	//Начиная со второго элемента - ищем место вставки 
    	//и переносим во вспомогательный массив
    	$start = 0; $finish = $newSize - 1;	$i = 1;
    	//Перебираем по порядку элементы основного массива
        while($i < count($arr)) {
    		//Бинарным поиском ищем место вставки в дополнительном массиве
            $pos = LibrarySort_BinarySearch($arr[$i], $start, $finish, $newSize);
            if($pos === false) {//Точка вставки не обнаружена ни в каком виде
    			//Полная перебалансировка вспомогательного массива
    			LibrarySort_Rebalance_Total($i, $newSize);
    		} else {//Точки вставки нашлась, но надо проверить, свободна ли она
    			if($arr_new[$pos] !== null) {//Точка вставки занята
    				if($rebalance_local) {//Локальная перебалансировка (+ вставка)
    					LibrarySort_Rebalance_Local($arr[$i++], $pos, $newSize);
    				} else {//Полная перебалансировка
    					LibrarySort_Rebalance_Total($i, $newSize);
    				}
    			} else {//Нашли свободную точку вставки, просто вставляем
    				$arr_new[$pos] = $arr[$i++];
    			}
    		}
    	}
    		
    	//Переносим из дополнительного массива в основной
        $pos = 0;
        for($i = 0; $i <= $newSize - 1; $i++) {
            if($arr_new[$i] !== null) $arr[$pos++] = $arr_new[$i];
        }	
    		
    	return $arr;
    }

    Новая позиция элемента в дополнительном массиве после полной перебалансировки
    //Позиция $number-го элемента из имеющихся $count
    //во вспомогательном массиве после перебалансировки
    //$number - какой по счёту в массиве (с начала) элемент
    //$count - сколько на данный момент перенесено элементов
    //$newSize - полный размер вспомогательного массива
    //$number <= $count <= count($arr) <= $newSize)
    function LibrarySort_Pos($number, $count, $newSize) {
    	return $number * floor(($newSize + 1) / ($count + 1)) - 1;
    }

    Бинарный поиск места вставки во вспомогательном массиве
    //Бинарный поиск места вставки во вспомогательном массиве
    //$search - значение элемента из основного массива, который нужно перенести во вспомогательный
    //($start, $finish) - крайние индексы диапазона, в котором происходит поиск
    //$newSize - полный размер вспомогательного массива
    function LibrarySort_BinarySearch($search, $start, $finish, $newSize) {
    	
    	global $arr_new;//Вспомогательный массив
    
        //Сначала разберёмся с левой границей диапазона
    
        //На левой границе диапазона должен находиться элемент, а не пустая ячейка
        //Сужаем слева диапазон, если на левом краю пустые элементы
        while($arr_new[$start] === null && $start < $newSize - 1) {
            ++$start;
        }
    
        //Если на границе такого же значения элемент что и искомый,
    	//то нужно вставить сразу за ним или перед ним
        if($search == $arr_new[$start]) {
            return LibrarySort_PosNearby($start, $newSize);
        //Может встретиться случай, когда искомый элемент меньше чем левая граница
        } elseif($search < $arr_new[$start]) {
            //Тогда искомому элементу место между левой 
    		//границей и началом дополнительного массива
    		if($start > 0) {//Перед $start есть свободное место
    			$finish = $start;
    			$start = 0;
    			return floor(($start + $finish) / 2);
    		} else {//$start == 0, перед ним ничего не вставить
    			return $start;//Если не нашли пустую ячейку, возвращаем тогда непустую
    		}
        }
    
        //На правой границе диапазона должен находиться элемент, а не пустая ячейка
        //Сужаем справа диапазон, если на левом краю пустые элементы
        while($arr_new[$finish] === null && $finish > 0) {
            --$finish;
        }
    
        //Если на границе такого же значения элемент что и искомый,
    	//то нужно вставить сразу за ним или перед ним
        if($search == $arr_new[$finish]) {
            return LibrarySort_PosNearby($finish, $newSize);
        //Может встретиться случай, когда искомый элемент больше чем правая граница
        } elseif($search > $arr_new[$finish]) {
            //Тогда искомому элементу место между правой 
    		//границей и концом дополнительного массива
    		if($finish < $newSize - 1) {//После $finish есть свободное место
    			$start = $finish;
    			$finish = $newSize - 1;
    			return ceil(($start + $finish) / 2);
    		} else {//$finish == $newSize - 1, после него ничего не вставить
    			return $finish;//Если не нашли пустую ячейку, возвращаем тогда непустую
    		}
        }
    
    	//Искомый элемент не совпадает с краями, 
    	//значит, его нужно вставить где-то внутри диапазона
    	//При этом нужно проверить, есть ли внутри диапазона ещё элементы
    	If($finish - $start > 1) {//Делить диапазон имеет смысл, если там минимум 3 элемента
    		$middle = ceil(($start + $finish) / 2); //Индекс середины диапазона
            $middle_Pos = 0; //Непустую "середину" диапазона пока не нашли
            $offset = 0; //Будем сдивгаться от точной середины в поисках непустого элемента
    
    		//Итак, сдигаемся от середины влево/вправо, пока не обнаружим непустой элемент
            while($middle - $offset > $start && $middle_Pos == 0){
                if($arr_new[$middle - $offset] !== null) {
                    $middle_Pos = $middle - $offset;
                } elseif($middle + $offset < $finish &&  $arr_new[$middle + $offset] !== null) {
                    $middle_Pos = $middle + $offset;
                }
                ++$offset;
            }
    	
            //Если внутри нашли непустой элемент, то, в зависимости от его значения, 
    		//или ищем место возле него или рекурсивно применяем к левой или правой части диапазона
            If($middle_Pos) {
                if($arr_new[$middle_Pos] == $search) {
    				return LibrarySort_PosNearby($middle_Pos, $newSize);
                } else {
    				if($arr_new[$middle_Pos] > $search) {
    					$finish = $middle_Pos;
    				} else {//$arr_new[$middle_Pos] < $search
    					$start = $middle_Pos;
    				}
                    return LibrarySort_BinarySearch($search, $start, $finish, $newSize);
                }
            } else {//$middle_Pos == 0 - внутри диапазона (не считая его границ) не найдены непустые элементы
                return $middle;//Середина такого диапазона - место, куда можно вставить элемент
            }
    
        } else {//Нашли минимальный отрезок, но свободного места в нём нет
    		return floor(($start + $finish) / 2);
    	}
    	
    	return false;//Если сюда добрались, значит бинарный поиск ничего не дал
    
    }

    Если при поиске элемент равен одному из концов отрезка
    //Если элемент равен концу отрезка, то ставим его рядом слева или справа
    //$start - позиция, на которой уже стоит элемент равный искомому
    //$newSize - полный размер вспомогательного массива
    function LibrarySort_PosNearby($start, $newSize) {
    	global $arr_new;//Вспомогательный массив
        //Сначала попытаемся найти свободное место перед элементом
        for($left = $start - 1; $left >= 0; $left--) {
            if($arr_new[$left] === null) {//Пустая ячейка
                return $left;//Сюда и вставим
            } elseif($arr_new[$left] <> $arr_new[$start]) {//Встретился элемент с другим значением
                break; //Слева ничего не поставишь, можно дальше влево не искать
            }
        }
    	//Если не нашли свободного места слева, попробуем поискать справа
    	for($right = $start + 1; $right <= $newSize - 1; $right++) {
            if($arr_new[$right] === null) {//Пустая ячейка
                return $right; //Сюда и вставим
            } elseif($arr_new[$right] <> $arr_new[$start]) {//Встретился элемент с другим значением
                break; //Справа ничего не поставишь, можно дальше вправо не искать
    		}
        }
    	return $start; //Ни слева ни справа от конца отрезка не нашли места вставки. Но мы возвращаем хотя бы точку, с которой начали поиск
    }

    Локальная перебалансировка дополнительного массива
    //Местная перебалансировка вспомогательного массива
    //$insert - значение, которое надо вставить
    //$pos - начиная с какого элемента нужно сдвинуть несколько штук влево или вправо
    //$newSize - полный размер вспомогательного массива
    function LibrarySort_Rebalance_Local($insert, $pos, $newSize) {
    	global $arr_new;//Вспомогательный массива
    	//Уточняем $pos для $insert, иногда надо чуть левее или правее
    	while($pos - 1 >= 0 && $arr_new[$pos - 1] !== null && $arr_new[$pos - 1] > $insert) {--$pos;}
    	while($pos + 1 <= $newSize - 1 && $arr_new[$pos + 1] !== null && $arr_new[$pos + 1] < $insert) {++$pos;}
    	$middle = (integer) $newSize / 2;//Середина массива
    	if($pos <= $middle) {//Точка вставки в левой части массива
    		if($arr_new[$pos] !== null && $arr_new[$pos] < $insert) ++$pos;
    		//Сдвигаем вправо
    		$right = $pos;
    		while($arr_new[++$right] !== null) {}
    		for($i = $right; $i > $pos; $i--) {
    			$arr_new[$i] = $arr_new[$i - 1];
    		}
    	} else {//Точка вставки в правой части массива	
    		if($arr_new[$pos] !== null && $insert < $arr_new[$pos]) --$pos;
    		//Сдвигаем влево
    		$left = $pos;
    		while($arr_new[--$left] !== null) {}
    		for($i = $left; $i < $pos; $i++) {
    			$arr_new[$i] = $arr_new[$i + 1];
    		}		
    	}
    	$arr_new[$pos] = $insert;
    }

    Полная перебалансировка дополнительного массива
    //Полная перебалансировка вспомогательного массива
    //$count - сколько элементов на данный момент в массиве
    //$newSize - полный размер вспомогательного массива
    function LibrarySort_Rebalance_Total($count, $newSize) {
        
    	global $arr_new;//Вспомогательный массив
    	global $library_Number;//Какой по счёту элемент переносим
    	global $library_LeftPos;//Самая левая позиция при которой влево переносили элементы
    	
        $library_Number = $count; //Начинаем переносить последние с конца по счёту элементы
        $library_LeftPos = $newSize - 1;//Пока неизвестна, поэтому максимально правое значение
            
        //Проходим элементы в дополнительном массиве от последнего к началу
        $i = $newSize - 1;
        while($i >= 0) {
            if($arr_new[$i] !== null) {//Очередной непустой элемент
    			$pos = LibrarySort_Pos($library_Number, $count, $newSize);//Его надо перенести сюдаnewSize=$newSize");
                if($i == $pos) {//Элемент уже стоит на своём месте
                    --$i;//Переходим дальше влево по дополнительному массиву
    			} elseif($i < $pos) {//Элемент нужно перенести вправо
    				$arr_new[$pos] = $arr_new[$i];
    				$arr_new[$i] = null;
    				--$i;//Переходим дальше влево по дополнительному массиву
                } else {//$i > $pos - элемент нужно перенести влево
                    //Рекурсивная процедура для переноса элемента влево
                    LibrarySort_RemoveLeft($i, $pos, $count, $newSize);
    				$i = ($i > $library_LeftPos) ? $library_LeftPos - 1 : --$i;
    			}
    			--$library_Number;//Переносимых элементов стало на одного меньше
    		} else {//Пустая клетка, нечего переносить
    			--$i;//Переходим дальше влево по дополнительному массиву
    		}
        }    
    }

    Перенос элемента левее при полной перебалансировке
    //Перенос элемента левее в перебалансируемом массиве. 
    //Этому могут мешать другие элементы, находящиеся слева
    //$i - в какой ячейке находится элемент, который нужно перенести
    //$pos - в какую ячейку нужно перенести элемент
    //$count - сколько всего сейчас элементов во вспомогательном массиве
    //$newSize - полный размер вспомогательного массива
    function LibrarySort_RemoveLeft($i, $pos, $count, $newSize) {
    
    	global $arr_new;//Вспомогательный массив
    	global $library_Number;//Какой по счёту элемент переносим
    	global $library_LeftPos;//Самая левая позиция при которой влево переносили элементы
    	
        $left = false; $left_Pos = false;//Пока ближайший сосед слева не найден
        $j = $i;//Начинаем перебирать сразу от переносимого элемента
        //Нужно выяснить ближайшего соседа слева
        while($j > 0 && $left === false) {//Пока в пределах вспомогательного массива и пока не найден ближайший сосед слева
            --$j; //Продолжаем влево поиск ближайшего соседа
            if($arr_new[$j] !== null) $left = $j;//Ближайший сосед слева обнаружен
        }
        if($left === false || $left < $pos) {//Ближайший сосед слева (если он найден) не мешает переносу
            //Ничего дополнительно предпринимать не нужно
        } else { //$left >= $pos, сосед слева мешает переносу
            --$library_Number;//Значит, левее нужно перенести мешающего соседа слева
            $left_Pos = LibrarySort_Pos($library_Number, $count, $newSize);//Соседа слева надо перенести сюда
            //Рекурсивно переносим соседа слева на его правильную позицию
            LibrarySort_RemoveLeft($left, $left_Pos, $count, $newSize);
            //Сосед слева отодвинут, теперь можно перенести элемент
        }
    	//С соседом слева всё нормально, переносим элемент
    	$arr_new[$pos] = $arr_new[$i];
    	$arr_new[$i] = null;
        //Уточняем, был ли это самый влево перенесённый из соседей
        if($pos < $library_LeftPos) $library_LeftPos = $pos;
    }

    Пришлось с нуля кодить самому, опираясь на общее описание метода. Скорости, близкой к быстрой сортировке я не увидел, мой вариант library sort сортирует в 10-20 раз медленнее чем quick sort. Но причина, конечно, в том, что моя реализация слишком сырая, многое не учтено.

    Хотелось бы увидеть версию от создателей алгоритма. Напишу сегодня авторам (и скину им ссылку на эту хабрастатью), вдруг ответят. Хотя… Помнится, я пытался связаться с Алленом Бичиком (ABC-сортировка) и Джейсоном Моррисоном (J-сортировка), но результат был такой же, как если бы я писал в Спортлото.

    UPD. Мартин Фарах-Колтон ответил мне, что реализацию они никогда не делали:
    I’m afraid we never implemented that algorithms.
    Главное — Идея :)

    Характеристики алгоритма

    Название Библиотечная сортировка, Сортировка библиотекаря, Library sort
    Другое название Сортировка вставками с разрывами, Gapped Insertion sort
    Авторы Майкл Бендер (Michael A. Bender), Мартин Фарах-Колтон (Martín Farach-Colton), Мигель Мостейро (Miguel Mosteiro)
    Год 2004
    Класс Сортировки вставками
    Сравнения Есть
    Временна́я сложность лучшая O(n)
    средняя O(n log n)
    худшая O(n2)
    Сложность по дополнительной памяти O(n)

    Ссылки


    Library sort

    Library Sort algorithm visualization

    Insertion sort is O(n log n)

    Авторы алгоритма:



    Майкл А. Бендер
    Мартин Фарах-Колтон
    Мигель Мостейро



    Статьи серии:





    Сортировка добавлена в AlgoLab. Так что можете поэксперементировать с небольшими наборами данных.

    При этом Вы можете сами решить, во сколько раз вспомогательный массив больше основного. Чтобы выбрать коэффициент ε можно щёлкнуть правой кнопкой мыши по ячейке с «Библиотечной сортировкой» и выбрать пункт «Изменить примечание». А в примечании аккуратно поставить целое значение для e от 2 до 5. Если вместо этих чисел введёте что-то иное, то будет использовано значение по умолчанию = 2.

    Также можно выбрать тип перебалансировки. Если поставить local=1, то будет использована локальная перебалансировка. Если local=0 — полная.

    И не забудьте перед запуском визуализации установить оптимальный масштаб для листа process, иначе вспомогательный массив не поместится на экране.

    Поделиться публикацией

    Похожие публикации

    Комментарии 7
      +1

      Жду статьи об оптимизации bogosort.
      [irony]

        +2
        И она будет :)
        0
        Непонятно, для чего выдумывать настолько бесполезный алгоритм. Только чтобы был алгоритм имени тебя? Сортировка вставками для маленьких списков будет столь же эффективна (учитывая необходимое для библ. сортировки копирование данных в конце выполнения), а для больших списков с quicksort'ом ему тягаться не получится. Есть ли для него хоть какое-то применение?
          +3
          Лично я алгоритмы разбираю just for fun. Реализация модифицированного бинарного поиска и полной перебалансировки массива доставили мне некоторое удовольствие.

          Что касается мотивов, которыми руководствовались авторы сортировки — спросите у них. Я привёл персональные странички профессоров на сайтах их университетов, там есть электронные адреса.
            +2

            (offtopic)
            Для just for fun — алгоритм вычисления "бегущего максимума" (Sliding window minimum/maximum algorithm) знаете? Ну, который обрабатывает массив длины n за O(n) независимо от длины окна?
            Интересен тем, что до него додумались довольно поздно, где-то в 80-х.


            Если не знаете — вам повезло, можете попробовать додуматься до него самостоятельно.

              0
              Спасибо, я погляжу. И даже посмотрю, можно ли этот метод использовать для сортировки. Если да, то отлично: после сортировок вставками будут сортировки выбором, и этот алгоритм органично впишется в этот класс.
          +1
          Вообще, использовать этот алгоритм можно для реализации различных SortedList, когда данные добавляются и удаляются и каждый раз перестраивать массив накладно, поэтому нужны специальные дырки для заполнения.
          Правда, имхо, гораздо более эффективно в этом случае использовать B-Tree

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое