Интерполяционная сортировка

Сортировка тегов интерполяции на месте
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность
Лучшая производительность
Средняя производительность
Наихудшая пространственная сложность
Оптимальный

Интерполяционная сортировка тегов
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность
Лучшая производительность
Средняя производительность
Наихудшая пространственная сложность
Оптимальный

Интерполяционная сортировка
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность
Лучшая производительность
Средняя производительность
Наихудшая пространственная сложность
Оптимальный

Интерполяционная сортировка — это алгоритм сортировки , который является своего рода сортировкой по сегментам . Он использует формулу интерполяции для назначения данных в сегмент. Общая формула интерполяции:

Интерполяция = INT(((Array[i] - min) / (max - min)) * (ArraySize - 1))

Алгоритм

Интерполяционная сортировка (или сортировка гистограммы). ^[1] Это алгоритм сортировки, который использует формулу интерполяции для распределения данных « разделяй и властвуй» . Интерполяционная сортировка также является разновидностью сортировки сегментов алгоритма . ^[2] Метод интерполяционной сортировки использует массив длин сегментов записей, соответствующий исходному числовому столбцу. Используя массив длины обслуживания, рекурсивным алгоритмом сложности пространства на можно предотвратить изменение $O(n^{2})$ из-за стекирования памяти. Запись сегментации массива длин может с помощью вторичной функции динамически объявлять и удалять пространство памяти массива . Пространственная сложность, необходимая для управления рекурсивной программой, равна $O(3n)$ . Содержит двумерный массив динамически выделяемой памяти и массив длин записей. Однако сложность выполнения все же можно сохранить как эффективный метод сортировки $O(n+k)$ . ^[3] Массив динамически выделяемой памяти может быть реализован в виде связанного списка , стека , очереди , ассоциативного массива , древовидной структуры такой объект массива, как JavaScript и т. д. Применим . Разница в структуре данных связана со скоростью доступа к данным и, следовательно, со временем, необходимым для сортировки . Когда значения в упорядоченном массиве равномерно распределены примерно в арифметической прогрессии , линейное время упорядочивания интерполяционной сортировки равно $O(n)$ . ^[4]

Алгоритм интерполяционной сортировки

Установите массив длины сегмента для записи длины несортированного сегмента. Инициализируйте исходную длину массива.
[Основная сортировка] Если массив длин сегмента очищен и сортировка завершена. Выполните [Функция разделения], если она не очищена.
[Функция разделения] Выполните деление, извлекая длину сегмента из конца массива длин сегмента. Найдите максимальное и минимальное значения в ведре. Если максимальное значение равно минимальному, сортировка завершается и функция разделения прекращается.
Настройте двумерный массив как все пустые сегменты. Разделите на сегменты в соответствии с номером интерполяции.
После разделения на сегменты поместите длину сегментов в массив длины сегмента. И помещаем элементы обратно в исходный массив по одному из всех непустых корзин.
Вернитесь к [Основной сортировке].

Алгоритм сортировки гистограммы

Определение NIST: Эффективное трехпроходное усовершенствование алгоритма сортировки по кольцу. ^[5]

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

Упражняться

Реализация интерполяционной сортировки

JavaScript-код:

Array.prototype.interpolationSort = function()
{
  var divideSize = new Array();
  var end = this.length;
  divideSize[0] = end;
  while (divideSize.length > 0) { divide(this); } 
  // Repeat function divide to ArrayList
  function divide(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) { max = A[i]; } }
    }
    if (min == max) { end = end - size; }
    else {
      var p = 0;
      var bucket = new Array(size);
      for (var i = 0; i < size; i++) { bucket[i] = new Array(); }
      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++) { A[start++] = bucket[i][j]; }
          divideSize.push(bucket[i].length);
        }
      }
    }
  }
};

Рекурсивный метод интерполяционной сортировки

Наихудшая пространственная сложность: $O(n^{2})$

Array.prototype.interpolationSort= function()
{//-- Edit date:2019/08/31 --//
  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) { max = this[i];} }
  }
  if (min != max) {
    var bucket = new Array(size);
    for (var i = 0; i < size; i++) { bucket[i] = new Array(); }
    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) { bucket[i].interpolationSort(); } // Recursion
      for (var j = 0; j < bucket[i].length; j++) { this[start++] = bucket[i][j]; }
    }
  }
};

Реализация сортировки гистограммы

Array.prototype.histogramSort = function()
{//-- Edit date:2019/11/14 --//
  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) { distribute(this); } 
  // Repeat function distribute to Array
  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) { max = A[i]; } }
    }
    if (min == max) { end = end - size; }
    else {
      for (var i = start; i < end; i++) { hitCount[i] = 0; }
      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) { divideSize.push(hitCount[i]); }
      }
      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++) { A[i] = sortedArray[i]; }
    }
  }
};

Вариант

Сортировка тегов интерполяции

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

Сортировка по тегам интерполяции — это рекурсивный метод сортировки с интерполяцией. Чтобы избежать переполнения стека, вызванного рекурсией, происходит сбой памяти. Вместо этого используйте массив тегов логического типа данных для выполнения рекурсивной функции по освобождению памяти. Требуемый дополнительный объем памяти близок к $2n+(n)bits$ . Содержит двумерный массив динамически выделяемой памяти и массив тегов логического типа данных. Стек, очередь, ассоциативный массив и древовидная структура могут быть реализованы в виде сегментов.

Поскольку объект массива JavaScript подходит для этого метода сортировки, разница в структуре данных связана со скоростью доступа к данным и, следовательно, со временем, необходимым для сортировки. Линейное время Θ(n) используется, когда значения в сортируемом массиве распределены равномерно. Алгоритм сортировки сегментов не ограничивает сортировку нижним пределом $O(nlogn)$ . Средняя сложность сортировки тегов интерполяции составляет $O(n+k)$ . ^[3]

Алгоритм сортировки тегов интерполяции

Установите массив тегов, равный исходному размеру массива, и инициализируйте его ложным значением.
[Основная сортировка] Определяет, были ли отсортированы все сегменты исходного массива. Если сортировка не завершена, выполняется [Функция разделения].
[Функция разделения] Найдите максимальное и минимальное значения в сегменте. Если максимальное значение равно минимальному, сортировка завершается и деление прекращается.
Настройте двумерный массив как все пустые сегменты. Разделите на сегменты в соответствии с номером интерполяции.
После разделения на сегмент отметьте начальную позицию сегмента как истинное значение в массиве тегов. И помещаем элементы обратно в исходный массив по одному из всех непустых корзин.
Вернитесь к [Основной сортировке].

Упражняться

JavaScript-код:

Array.prototype.InterpolaionTagSort = function()
{// Whale Chen agrees to "Wikipedia CC BY-SA 3.0 License". Sign date: 2019-06-21 //
  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++) { Tag[i] = false; } 
    Divide(this); 
  } 
  while (end > 1) {                     // Algorithm step-2  
    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) { max = A[i]; } } }
    if ( min == max) { end = start; }    // Algorithm step-3 Start to be the next bucket's end
    else {                                          
      var interpolation = 0; 
      var size = end - start; 
      var Bucket = new Array( size );    // Algorithm step-4         
      for (var i = 0; i < size; i++) { Bucket[i] = new Array(); }  
      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++) { A[start++] = Bucket[i][j]; } 
        } 
      }  
    }
  } // Algorithm step-6 
};

Сортировка тегов интерполяции на месте

Сортировка тегов интерполяции на месте — это на месте алгоритм интерполяционной сортировки . Сортировка тегов интерполяции на месте может обеспечить сортировку только за N раз замены, поддерживая N битовых тегов; однако массив, подлежащий сортировке, должен представлять собой непрерывную целочисленную последовательность и не повторяться, иначе ряд будет полностью равномерно распределен для приближения к числу арифметической прогрессии .

Данные столбца фактора не должны повторяться. Например, сортировку от 0 до 100 можно выполнить за один шаг. Количество обменов: $O(n)$ , временная сложность расчета равна: $O(n)$ , а наихудшая пространственная сложность равна $O(n)bits$ . Если характеристики ряда соответствуют условным требованиям этого метода сортировки: «Массив представляет собой непрерывное целое число или неповторяющуюся арифметическую прогрессию», сортировка по тегу интерполяции на месте будет отличным методом сортировки, чрезвычайно быстрым и экономит место в памяти.

Алгоритм сортировки тегов интерполяции на месте

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

Алгоритм процесса:

Установите равное количество массивов тегов для инициализации ложными значениями.
Посетите массив, когда tag[i] имеет значение false, вычислите позицию, соответствующую интерполяции = p.
Поменяйте местами a[i] и a[p], пусть tag[p] = true.
Массив туров завершен и сортировка завершена.

Упражняться

JavaScript-код:

Array.prototype.InPlaceTagSort = function()
{ // Edit Date: 2019-07-02
  var n = this.length;
  var Tag = new Array(n);
  for (i = 0; i < n; i++) { Tag[i] = false; }
  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) { max = this[i]; } } } 
  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; 
    } 
  } 
};
needSortArray.InPlaceTagSort();

Происхождение сортировки на месте, выполняемой в $O(n)$ время

В «Математическом анализе алгоритмов» Дональд Кнут заметил: «... что исследование вычислительной сложности — это интересный способ отточить наши инструменты для решения более рутинных задач, с которыми мы сталкиваемся изо дня в день». ^[6]

Кнут далее отметил, что, что касается проблемы сортировки, эффективная по времени перестановка на месте по своей сути связана с проблемой поиска лидеров цикла, и перестановки на месте могут быть легко выполнены в $O(n)$ время, если бы нам разрешили манипулировать $n$ дополнительные биты «тега», указывающие, какая часть перестановки была выполнена в любой момент времени. Без таких битов тегов, заключает он, «кажется разумным предположить, что каждый алгоритм потребует для перестановки на месте как минимум $n\log n$ шагов в среднем». ^[6]

Сортировка по тегам интерполяции на месте — это один из алгоритмов сортировки, разработанных проф. Дональд Кнут сказал: «манипулируйте $n$ дополнительные биты «тегов»... поиск лидеров цикла и перестановки на месте могут быть легко выполнены в $O(n)$ время".

Аналогичный метод сортировки

Сортировка сегментами, сочетающая другие методы сортировки и рекурсивный алгоритм.

Сортировку сегментами можно комбинировать с другими методами сортировки для завершения сортировки. Если сортировка осуществляется по сегментной сортировке и сортировке вставкой, это также довольно эффективный метод сортировки. Но когда в ряду появляется большое отклонение от значения: например, когда максимальное значение ряда превышает следующее по величине значение более чем в N раз. После обработки серии столбцов распределение таково, что все элементы, кроме максимального значения, попадают в один и тот же сегмент. Второй метод сортировки использует сортировку вставкой. Может привести к снижению сложности выполнения $O(n^{2})$ . Это потеряло смысл и быстродействие использования сортировки ведром.

Интерполяционная сортировка — это способ рекурсивного использования сегментной сортировки. После выполнения рекурсии по-прежнему используйте сортировку по сегментам для распределения рядов. Это позволит избежать описанной выше ситуации. Если вы хотите, чтобы сложность выполнения рекурсивной интерполяционной сортировки упала до $O(n^{2})$ , необходимо представить факториальное во всем ряду усиление. На самом деле вероятность того, что произойдет серия особых распределений, очень мала.

Ссылки

^ Алгоритм НИСТ. «интерполяционная сортировка» . Определение: См. сортировку гистограммы.
^ Сортировка гистограммы ^{[ циклическая ссылка ]}
^ Jump up to: Перейти обратно: ^а ^б Сортировка ведром ^{[ циклическая ссылка ]}
^ Сортировка сегментами. Анализ среднего случая. ^{[ циклическая ссылка ]}
^ Алгоритм НИСТ. «Сортировка гистограммы» . Определение: Эффективное трехпроходное усовершенствование алгоритма сортировки по корзинам.
^ Jump up to: Перейти обратно: ^а ^б Карл-Дитрих Нойберт (1998). «Алгоритм FlashSort» . Проверено 6 ноября 2007 г.

Внешние ссылки

[1] Алгоритм НИСТ. «интерполяционная сортировка» . Определение: См. сортировку гистограммы.

[2] Сортировка гистограммы ^{[ циклическая ссылка ]}

[ReferenceA-3] Jump up to: Перейти обратно: ^а ^б Сортировка ведром ^{[ циклическая ссылка ]}

[4] Сортировка сегментами. Анализ среднего случая. ^{[ циклическая ссылка ]}

[5] Алгоритм НИСТ. «Сортировка гистограммы» . Определение: Эффективное трехпроходное усовершенствование алгоритма сортировки по корзинам.

[neubert_code-6] Jump up to: Перейти обратно: ^а ^б Карл-Дитрих Нойберт (1998). «Алгоритм FlashSort» . Проверено 6 ноября 2007 г.

[1]

[2]

[3]

[4]

[5]

[6]

v т и Алгоритмы сортировки
Теория	Теория сложности вычислений Обозначение большого О Общий заказ Списки Размещение Стабильность Сортировка сравнения Адаптивная сортировка Сортировочная сеть Целочисленная сортировка X + Y сортировка Трансдихотомическая модель Квантовая сортировка
Обмен сортами	Пузырьковая сортировка Сорт коктейльного шейкера Нечетно-четный сорт Гребенчатая сортировка Гном сортирует Пропорциональное расширение сортировки Быстрая сортировка
Сортировки выбора	Сортировка выбором пирамидальная сортировка Гладкая сортировка Декартова сортировка дерева Сортировка турниров Циклическая сортировка Слабая пирамидальная сортировка
Сортировки вставками	Сортировка вставкой Шеллсорт Сплейсорт Сортировка дерева Сортировка библиотеки Сортировка терпения
Объединить сортировки	Идет судьба Каскадная сортировка слиянием Осциллирующая сортировка слиянием Многофазная сортировка слиянием
Виды распределения	сорт американского флага Сортировка бисера Сортировка ведром Пакетная сортировка Подсчет сортировки Интерполяционная сортировка Сортировка по ячейкам Сортировка проксмап Поразрядная сортировка Флэш-сортировка
Параллельные сортировки	Битонический сортировщик Батчерная сортировка слиянием нечет-чет Попарная сортировочная сеть Выборочная сортировка
Гибридные сорта	Блокировать сортировку слиянием Сорт Киркпатрика – Райша Тимсорт Интросорт Спред-сортировка Сортировка слиянием-вставкой
Другой	Топологическая сортировка Предтопологический порядок Сортировка блинов Спагетти сорт
Непрактичные сорта	марионетка сортировка медленная сортировка Богосорт

Алгоритм

Алгоритм интерполяционной сортировки

Алгоритм сортировки гистограммы

Упражняться

Реализация интерполяционной сортировки

Рекурсивный метод интерполяционной сортировки

Реализация сортировки гистограммы

Вариант

Сортировка тегов интерполяции

Алгоритм сортировки тегов интерполяции

Упражняться

Сортировка тегов интерполяции на месте

Алгоритм сортировки тегов интерполяции на месте

Упражняться

Происхождение сортировки на месте, выполняемой в O ( n ) {\displaystyle O(n)} время

Аналогичный метод сортировки

Сортировка сегментами, сочетающая другие методы сортировки и рекурсивный алгоритм.

Ссылки

Внешние ссылки

Происхождение сортировки на месте, выполняемой в $O(n)$ время