Адаптивные алгоритмы сортировки и сети сортировки для сортировки списка из 32 случайных элементов

Question

Если мы используем последовательную машину (параллельные сравнения невозможны), где сравнения выполняются последовательно, и мы стремимся минимизировать количество тактов процессора при сортировке 32 случайных элементов, следует ли нам использовать сортировочную сеть или алгоритм адаптивной сортировки?

Не существует оптимальных сетей (пока) для n = 32 элементов. В практическом плане, если мы хотим минимизировать количество тактов ЦП, лучше ли разделить 32 элемента на четыре подсписка из n = 8 и применить оптимальную сеть сортировки к каждому подсписку, а затем объединить списки?

Здесь мы, очевидно, работаем со «средней производительностью», потому что адаптивным алгоритмам может повезти, если нам будет дан уже отсортированный список.

Сокращая числа, мы имеем следующее:

Сортировка списка по размеру n:

• Минимальное количество сравнений для n = 2 равно 1.

• Минимальное количество сравнений для n = 4 равно 5.

• Минимальное количество сравнений для n = 8 равно 19.

Объединение двух списков размером n:

• Слияние двух списков с n = 2 равно 2 * n - 1 = 3 сравнения

• Слияние двух списков с n = 4 равно 2 * n - 1 = 7 сравнений

• Слияние двух списков с n = 8 равно 2 * n - 1 = 15 сравнений.

• Слияние двух списков с n = 16 - это 2 * n - 1 = 31 сравнение.

Общее количество сравнений, если мы разделим n = 32 на шестнадцать n = 2 подсписков:

• Сортировка: 1 * 16 = 16
• Слияние: 3 * 8 + 7 * 4 + 15 * 2 + 31 * 1 = 113
• Всего: 129

Общее количество сравнений, если мы разделим n = 32 на восемь n = 4 подсписков:

• Сортировка: 5 * 8 = 40
• Слияние: 7 * 4 + 15 * 2 + 31 * 1 = 89
• Итого: 129

Общее количество сравнений, если мы разделим n = 32 на четыре n = 8 подсписка:

• Сортировка: 19 * 4 = 76
• Слияние: 15 * 2 + 31 * 1 = 61
• Всего: 137

Теперь можно подумать, что было бы лучше разделить n = 32 элемента на n = 2 или n = 4 подсписка, так как общее число сравнений меньше. Но mergin требует хранения частей массива "не на своем месте", что может свести на нет преимущество меньшего количества сравнений?

Мои интуитивные ощущения говорят мне, что в среднем неадаптивная сортировочная сеть похожа на алгоритм с точки зрения общего сравнения, но сортировочная сеть выигрывает благодаря меньшим издержкам, я прав?

---

Я пытаюсь отсортировать n = 32 элемента в среднем менее чем за 1200 тактов. Я работаю на простой последовательной машине с простой 256 слов * 16-битной памятью и только четырьмя регистрами , поэтому сеть / алгоритм должны быть простыми, быстрыми и не требовать большого количества пространство. АЛУ имеет только функции сложения, вычитания, сдвига в один бит, вращения на один бит, И и ИЛИ. Операции с памятью и ALU занимают один тактовый цикл.

Answer 1

Куча сортировки Вычисление индекса тривиально - сравниваемые элементы всегда имеют индексы n, 2n + {1,2}, что делает его вычислительно эффективным с вашей архитектурой.

Рабочая лошадка сортировки кучи - это обычная процедура:

while(true){
    r=(i+1)*2; l=r-1;
    if (*l > * i) { 
       if (*r > *l) swap(i,r);
       else swap(i,l);
    }
    else { 
       if (*r >* i) swap(i,r);
       else break;
    }
 }

Операция обмена должна в качестве побочного эффекта также обновить адрес i до l или r. В отличие от решения из учебника, мы не проверяем, действительны ли адреса дочерних элементов, но мы торгуем пространством, чтобы ускорить выделение буфера из 32 нулей в конце массива. Как только i не превосходит ни одного из дочерних элементов, обход до дна кучи заканчивается.