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

Не путать с интерполяционным поиском .

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

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

Алгоритм

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

Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$O(n^{2})$
Лучшая производительность	$O(n)$
Средняя производительность	$O(n+k)$
Наихудшая пространственная сложность	$O(n*3)$
Оптимальный	$O(n)$

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

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

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

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

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

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

Упражняться

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

JavaScript-код:

Множество  .  прототип  .  interpolationSort   =   функция  ()  {    вар   divizeSize   =   новый   массив  ();    вар   конец   =   это  .  длина  ;    разделитьРазмер  [  0  ]   =   конец  ;    в то время как   (  divizeSize  .  length   >   0  )   {   делите  (  это  );   }     // Повторяем функцию деления для ArrayList    function   разделить  (  A  )   {      var   size   =   diveSize  .  поп  ();      вар   начало   =   конечный   размер  ​  ;      вар   мин   =   A  [  начало  ];      вар   Макс   =   A  [  начало  ];      для   (  вар   я   =   начало   +   1  ;   я   <   конец  ;   я  ++  )   {        если   (  А  [  я  ]   <   мин  )   {   мин   =   А  [  я  ];   }        Еще   {   если   (  А  [  я  ]   >   Макс  )   {   Макс   =   А  [  я  ];   }   }      }      if   (  min   ==   max  )   {   end   =   end   -   size  ;   }      Еще   {        вар   п   =   0  ;        вар   ведро   =   новый   массив  (  размер  );        для   (  вар   я   =   0  ;   я   <   размер  ;   я  ++  )   {   ведро  [  я  ]   =   новый   массив  ();   }        for   (  var   я   =   начало  ;   я   <   конец  ;   я  ++  )   {          p   =   Math  .  пол  (((  A  [  i  ]   -   мин   )   /   (  макс   -   мин   )   )   *   (  размер   -   1   ));          ведро  [  п  ].  нажать  (  A  [  i  ]);        }        for   (  var   i   =   0  ;   я   <   size  ;   я  ++  )   {          if   (  ведро  [  i  ].  длина   >   0  )   {            for   (  var   j   =   0  ;   j   <   ведро  [  i  ].  length  ;   j  ++  )   {   A  [  start  ++  ]   =   ведро  [  i  ][  j  ];   }            РазделитьРазмер  .  толчок  (  ведро  [  i  ].  длина  );          }        }      }    }  }; 

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

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

Множество  .  прототип  .  interpolationSort  =   function  ()  {  //-- Дата редактирования: 31.08.2019 --//    var   start   =   0  ;    вар   размер   =   это  .  длина  ;    вар   мин   =   это  [  0  ];    вар   Макс   =   это  [  0  ];     для   (  вар   я знак   равно   1  ;   я   <   размер  ;   я  ++  )   {      если   (  это  [  я  ]   <   мин  )   {   мин   =   это  [  я  ];   }      Еще   {  if   (  this  [  i  ]   >   max  )   {   max   =   this  [  i  ];}   }    }    if   (  min   !=   max  )   {      var   Bucket   =   new   Array  (  size  );      для   (  вар   я   =   0  ;   я   <   размер  ;   я  ++  )   {   ведро  [  я  ]   =   новый   массив  ();   }      вар   интерполяция   =   0  ;      for   (  var   я   =   0  ;   я   <   размер  ;   я  ++  )   {        интерполяция   =   Math  .  пол  (((  this  [  i  ]   -   min  )   /   (  max   -   min  ))   *   (  size   -   1  ));        ведро  [  интерполяция  ].  нажать  (  это  [  я  ]);      }      for   (  var   я   =   0  ;   я   <   размер  ;   я  ++  )   {        if   (  ведро  [  я  ].  длина   >   1  )   {   ведро  [  я  ].  интерполяционная сортировка  ();   }   // Рекурсия        for   (  var   j   =   0  ;   j   <   Bucket  [  i  ].  length  ;   j  ++  )   {   this  [  start  ++  ]   =   Bucket  [  i  ][  j  ];   }      }    }  }; 

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

Множество  .  прототип  .  histogramSort   =   function  ()  {  //-- Дата редактирования: 14.11.2019 --//    var   end   =   this  .  длина  ;    вар   sortedArray   =   новый   массив  (  конец  );    вар   интерполяция   =   новый   массив  (  конец  );    вар   hitCount   =   новый   массив  (  конец  );    вар   divizeSize   =   новый   массив  ();    разделитьРазмер  [  0  ]   =   конец  ;    в то время как   (  divizeSize  .  length   >   0  )   {   распределить  (  это  );   }     // Повторить функцию распределения по массиву    function   распределения  (  A  )   {      var   size   =   diveSize  .  поп  ();      вар   начало   =   конечный   размер  ​  ;      вар   мин   =   A  [  начало  ];      вар   Макс   =   A  [  начало  ];      для   (  вар   я   =   начало   +   1  ;   я   <   конец  ;   я  ++  )   {        если   (  А  [  я  ]   <   мин  )   {   мин   =   А  [  я  ];   }        Еще   {   если   (  А  [  я  ]   >   Макс  )   {   Макс   =   А  [  я  ];   }   }      }      if   (  min   ==   max  )   {   end   =   end   -   size  ;   }      Еще   {        for   (  вар   я   =   начало  ;   я   <   конец  ;   я  ++  )   {   hitCount  [  я  ]   =   0  ;   }        for   (  var   я   =   начало  ;   я   <   конец  ;   я  ++  )   {          интерполяция  [  я  ]   =   начало   +   Math  .  пол  (((  A  [  i  ]   -   мин   )   /   (  макс   -   мин   )   )   *   (  размер   -   1   ));          hitCount  [  интерполяция  [  i  ]]  ++  ;        }        for   (  var   я   =   начало  ;   я   <   конец  ;   я  ++  )   {          if   (  hitCount  [  i  ]   >   0  )   {   divizeSize  .  нажать  (  hitCount  [  i  ]);   }        }        hitCount  [  конец  -  1  ]   =   конец   -   hitCount  [  конец  -  1  ];        for   (  var   i   =   end  -  1  ;   i   >   start  ;   i  --  )   {          hitCount  [  i  -  1  ]   =   hitCount  [  i  ]   -   hitCount  [  i  -  1  ];        }        for   (  var   я   =   начало  ;   я   <   конец  ;   я  ++  )   {          sortedArray  [  hitCount  [  интерполяция  [  я  ]]]   =   A  [  я  ];          hitCount  [  интерполяция  [  i  ]]  ++  ;        }        for   (  var   i   =   начало  ;   я   <   конец  ;   я  ++  )   {   A  [  я  ]   =   sortedArray  [  я ];  }     }   } }; 

Вариант

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

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

Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$O(n^{2})$
Лучшая производительность	$O(n)$
Средняя производительность	$O(n+k)$
Наихудшая пространственная сложность	$O(2n+(n)bits)$
Оптимальный	$O(n)$

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

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

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

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

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

Упражняться

JavaScript-код:

Множество  .  прототип  .  InterpolaionTagSort   =   function  ()  {  // Кит Чен соглашается с «Лицензией Wikipedia CC BY-SA 3.0». Дата подписания: 21 июня 2019 г. //    var   end   =   this  .  длина  ;     если   (  конец   >   1  )   {       вар   начало   =   0   ;       var   Tag   =   новый   массив  (  конец  );            // Шаг 1 алгоритма      for   (  var   i   =   0  ;   i   <   end  ;   i  ++  )   {   Tag  [  i  ]   =   false  ;   }       Разделить  (  это  );     }     while   (  end   >   1  )   {                       // Шаг 2 алгоритма      while   (  Tag  [  --  start  ]   ==   false  )   {   }   // Находим начало следующего сегмента      Divide  (  this  );     }    function   Divide  (  A  )   {         var   min   =   A  [  start  ];       вар   Макс   =   A  [  начало  ];      для   (  вар   я   =   начало   +   1  ;   я   <   конец  ;   я  ++  )   {         если   (  А  [  я  ]   <   мин  )   {   мин   =   А  [  я  ];   }         Еще   {   если   (  А  [  я  ]   >   Макс  )   {   Макс   =   А  [  я  ];   }   }   }      if   (   мин   ==   макс  )   {   конец   =   начало  ;   }      // Шаг 3 алгоритма. Начало должно быть концом следующего сегмента      else   {                                                  var   interpolation   =   0  ;         вар   размер   =   конец   -   начало  ;         var   Bucket   =   новый   массив  (   размер   );      // Шаг 4 алгоритма        for   (  var   i   =   0  ;   i   <   size  ;   i  ++  )   {   Bucket  [  i  ]   =   new   Array  ();   }          for   (  var   я   =   начало  ;   я   <   конец  ;   я  ++  )   {             интерполяция   =   Math  .  пол   (((  A  [  i  ]   -   мин  )   /   (  макс   -   мин  ))   *   (  размер   -   1  ));           Ведро  [  интерполяция  ].  нажать  (  A  [  i  ]);         }         for   (  var   i   =   0  ;   i   <   size  ;   i  ++  )   {          if   (  Bucket  [  i  ].  length   >   0  )   {      // Шаг 5 алгоритма            Tag  [  start  ]   =   true  ;             for   (  var   j   =   0  ;   j   <   Bucket  [  i  ].  length  ;   j  ++  )   {   A  [  start  ++  ]   =   Bucket  [  i  ] [  j  ];   }           }         }        }    }   // Шаг алгоритма 6 }; 

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

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

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

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

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

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

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

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

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

Упражняться

JavaScript-код:

Множество  .  прототип  .  InPlaceTagSort   =   function  ()  {   // Дата редактирования: 2019-07-02    var   n   =   this  .  длина  ;    var   Tag   =   новый   массив  (  n  );    для   (  я знак   равно   0  ;   я   <   п  ;   я  ++  )   {   Тег  [  я  ]   =   ложь  ;   }    вар   мин   =   это  [  0  ];    вар   Макс   =   это  [  0  ];    для   (  я   знак равно   1  ;   я   <   п  ;   я  ++  )   {   если   (  это  [  я  ]   <   мин  )   {   мин   =   это  [  я  ];   }    Еще   {   если   (  это  [  я  ]   >   Макс  )   {   Макс   =   это  [  я  ];   }   }   }     вар   р   =   0  ;    вар   темп   =   0  ;    for   (  я знак   равно   0  ;   я   <   n  ;   я  ++  )   {      while   (  Tag  [  i  ]   ==   false  )   {         p   =   Math  .  пол  (((  this  [  i  ]   -   min  )   /   (  max   -   min  ))   *   (  n   -   1  ));        темп   =   это  [  я  ];        это  [  я  ]   =   это  [  п  ];         это  [  п  ]   =   температура  ;        Тег  [  p  ]   =   правда  ;       }     }   };  нуженСортмассив  .  ИнПлацеТагСорт  (); 

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

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

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

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

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

1. Флэш-сортировка
2. Сортировка проксмап
3. сорт американского флага

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

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

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

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

• интерполяцияSort.html
• гистограммаSort.html
• Алгоритм FlashSort
• Математический анализ алгоритмов
• http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496
• Сортировка ведром Рекурсивный метод Кит Чен 16.09.2012.
• Алгоритм интерполяционной сортировки тегов Кит Чен 24.03.2013.
• интерполяционная сортировка (доступна версия для Паскаля)
• Платформа тестирования сортировки массивов JavaScript w3schools