Отсортировать 8 чисел только 16 сравнениями

@bellaps · Регистрация: 28.10.2016

Author24 — интернет-сервис помощи студентам

Как отсортировать 8 чисел только 16 сравнениями?? Может у кого есть идеи?

@afront · 14.11.2016, 10:33

обычна сортировка выбором для случая когда нужно все переставить сделает именно столько сравнений.
если начальное расположение цифр будет иным и какие то цифры стоят на "своем" месте - сравнений будет меньше

C++

#include <iostream>
using namespace std;
int main()
{
    int n =8;
    int a[8] = {8,7,6,5,4,3,2,1};
    
    int count =0;
    for(int i = 0; i < n; ++i){ 
        int pos = i; 
        int tmp = a[i];
        for(int j = i + 1; j < n; ++j)
           if (a[j] < tmp){
               pos = j; 
               tmp = a[j]; 
               count++;
           }
        a[pos] = a[i]; 
        a[i] = tmp;
    }
    cout << "count = " << count << endl;
    system("pause");
    return 0;
}

@GbaLog- · 14.11.2016, 10:37

afront, А почему вы прибавляете count, только если условие дало true?
Ведь сравнение есть, независимо от того, истину оно дало, или ложь.

@afront · 14.11.2016, 11:16

GbaLog-, да, я не прав, посчитал перестановки

@TheCalligrapher · 14.11.2016, 12:34

Сообщение от bellaps

Как отсортировать 8 чисел только 16 сравнениями??

Ну алгоритм тут довольно хитрый (описан у Кнута) и с не очень большой практической ценностью. Обычный merge sort отсортирует за 17 сравнений и это будет намного практичнее.

А за 16 сравнений это делается так:

1. Сначала сортируем элементы в парах, на что понадобится 4 сравнения

[b1][a1] [b2][a2] [b3][a3] [b4][a4]

Теперь у нас b1 < a1, b2 < a2 и т.д.

2. Теперь полностью упорядочиваем между собой пары по возрастанию старших элементов пар a. На это потребуется 5 сравнений

[b1][a1] [b2][a2] [b3][a3] [b4][a4]

То есть пусть теперь у нас a1 < a2 < a3 < a4 и в то же время b1 < a1, b2 < a2 и т.д.

3. Теперь мысленно извлекаем элементы b из последовательности

[a1][a2][a3][a4]

и вставляем их по одному обратно в правильные места в такой очередности: b1, b3, b2, b4.

3.1. b1 уже находился на своем месте, поэтому мы вставляем его обратно без сравнения вообще

[b1][a1][a2][a3][a4]

3.2. b3 (который меньше a3) должен попасть куда-то до a3. На бинарный поиск места для вставки среди 3 элементов надо 2 сравнения.

Тут могут получиться разные варианты:

[b3][b1][a1][a2][a3][a4]
[b1][b3][a1][a2][a3][a4]
[b1][a1][b3][a2][a3][a4]
[b1][a1][a2][b3][a3][a4]

3.3. b2 (который меньше a2) должен попасть куда-то до a2. Обратите внимание, что область поиска в любом случае - 3 или 2 элемента. На бинарный поиск места для вставки надо 2 сравнения.

Количество возможных исходов тут вырастает и я их "рисовать" не буду.

3.4. b4 (который меньше a4) должен попасть куда-то до a4. Тут просто делается бинарный поиск места для вставки среди 6 элементов, на который надо 3 сравнения.

Все. Итого 4+5+2+2+3 = 16 сравнений.

Уменьшение количества сравнений возникает за счет хитрого выбора порядка вставки элементов b обратно в последовательность. И порядок этот диктуется так называемыми Числами Якобсталя.

Evg · 14.11.2016, 12:46

Сообщение от TheCalligrapher

Ну алгоритм тут довольно хитрый (описан у Кнута) и с не очень большой практической ценностью

Есть подозрение, что подобные алгоритмы разрабатывают для реализации в железе, а не в софте

@TheCalligrapher · 14.11.2016, 12:51

Сообщение от Evg

Есть подозрение, что подобные алгоритмы разрабатывают для реализации в железе, а не в софте

Трудно сказать... При упоминании железа на ум сразу приходят сети сортировки. Но в сетях сортировки порядок сравнений жестко прошит заранее и из-за этого сравнений (компараторов) получается больше. 8 элементов - 19 компараторов минимум.

zer0mail · 14.11.2016, 16:27

Интересно, можно ли отсортировавать:
элементов сравнений
5......................7
6.....................10
7.....................13

@TheCalligrapher · 14.11.2016, 19:12

Сообщение от zer0mail

Интересно, можно ли отсортировавать:
элементов сравнений
5......................7
6.....................10
7.....................13

Да, можно.

zer0mail · 14.11.2016, 19:22

Теория информации определяет нижнюю границу (в правом столбике). Но нижняя граница не всегда достижима..

@TheCalligrapher · 14.11.2016, 19:31

Сообщение от zer0mail

Теория информации определяет нижнюю границу (в правом столбике). Но нижняя граница не всегда достижима..

Таблица справа в

https://en.wikipedia.org/wiki/... ort_a_list

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

Evg · 14.11.2016, 19:46

Сообщение от TheCalligrapher

При упоминании железа на ум сразу приходят сети сортировки. Но в сетях сортировки порядок сравнений жестко прошит заранее и из-за этого сравнений (компараторов) получается больше

В железных алгоритмах (например, в микросхеме), насколько я понимаю, наиболее критичным является количество тактов. Типа того, что 4 сравнения можно выполнять параллельно (одновременно)

@bellaps · 14.11.2016, 20:05 **[ТС]**

TheCalligrapher, "Тут просто делается бинарный поиск места для вставки среди 6 элементов, на который надо 3 сравнения."
Я не совсем поняла, как это достижимо?
Если, например, у меня ряд [b1] [b2] [a1] [a2] [b3] [a3] [a4], то с чем именно мне сравнивать b4,чтобы получилось за 3 срнвнения?

@TheCalligrapher · 14.11.2016, 20:37

Сообщение от bellaps

Если, например, у меня ряд [b1] [b2] [a1] [a2] [b3] [a3] [a4], то с чем именно мне сравнивать b4,чтобы получилось за 3 срнвнения?

b4 заведомо меньше, чем a4. То есть вам надо вставить b4 слева от a4. Это запросто делается бинарным поиском за 3 сравнения. Например, в вашем варианте, начнем со сравнения с a2

Код

b4 < a2  =>  b4 < b2  =>  b4 < b1  - вставляем слева от b1
                      =>  b4 > b1  - вставляем слева от b2
         =>  b4 > b2  =>  b4 < a1  - вставляем слева от a1
                      =>  b4 > a1  - вставляем слева от a2
b4 > a2  =>  b4 < b3               - вставляем слева от b3
         =>  b4 > b3  =>  b4 < a3  - вставляем слева от a3
                      =>  b4 > a3  - вставляем слева от a4

@bellaps · 03.12.2016, 21:56 **[ТС]**

Добавлено через 1 минуту
TheCalligrapher, Добрый день! Снова всплыл вопрос. Но разве это не 5 сравнений? Ведь сравниваем а4 с 5 остальными элементами..

Добавлено через 6 минут
Добавлю, что задание раположить элементы в возрастающей последовательности,сравнивая и перестанавливая после сравнения. В visual basic. Типа:
If a>b then
x=a
a=b
b=x

@TheCalligrapher · 03.12.2016, 22:18

Сообщение от bellaps

Но разве это не 5 сравнений? Ведь сравниваем а4 с 5 остальными элементами..

Ничего не понял. Какое еще a4? a4 мы вообще не трогаем.

И откуда взялось 5? Приведенная диаграмма - это это диаграмма "ветвления" выполняющегося кода (блок-схема, если хотите). Диаграмма выполняется слева-направо. Какой бы мы путь выполнения слева-направо ни выбрали, количество фактически выполненных сравнений равно 3 (или 2).

Сообщение от bellaps

Добавлю, что задание расположить элементы в возрастающей последовательности,сравнивая и перестанавливая после сравнения.

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

Минимизация количества сравнений и минимизация количества перестановок - две очень разные, независимые темы. Пока что о минимизация количества перестановок речи не шло вообще.

Что же касается минимизация количества сравнений, то для 8 элементов меньше 16 получить невозможно и алгоритм приведен выше.

@bellaps 0 / 0 / 0 Регистрация: 28.10.2016 Сообщений: 7
	03.12.2016, 21:56 [ТС]	15
	Добавлено через 1 минуту TheCalligrapher, Добрый день! Снова всплыл вопрос. Но разве это не 5 сравнений? Ведь сравниваем а4 с 5 остальными элементами.. Добавлено через 6 минут Добавлю, что задание раположить элементы в возрастающей последовательности,сравнивая и перестанавливая после сравнения. В visual basic. Типа: If a>b then x=a a=b b=x 0

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	14.11.2016, 10:37	3
	afront, А почему вы прибавляете count, только если условие дало true? Ведь сравнение есть, независимо от того, истину оно дало, или ложь. 0

@afront 1494 / 1209 / 821 Регистрация: 29.02.2016 Сообщений: 3,614
	14.11.2016, 11:16	4
	GbaLog-, да, я не прав, посчитал перестановки 0

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,068
	14.11.2016, 12:34	5
	Сообщение было отмечено GbaLog- как решение Решение Сообщение от bellaps Как отсортировать 8 чисел только 16 сравнениями?? Ну алгоритм тут довольно хитрый (описан у Кнута) и с не очень большой практической ценностью. Обычный merge sort отсортирует за 17 сравнений и это будет намного практичнее. А за 16 сравнений это делается так: 1. Сначала сортируем элементы в парах, на что понадобится 4 сравнения [b1][a1] [b2][a2] [b3][a3] [b4][a4] Теперь у нас b1 < a1, b2 < a2 и т.д. 2. Теперь полностью упорядочиваем между собой пары по возрастанию старших элементов пар `a`. На это потребуется 5 сравнений [b1][a1] [b2][a2] [b3][a3] [b4][a4] То есть пусть теперь у нас a1 < a2 < a3 < a4 и в то же время b1 < a1, b2 < a2 и т.д. 3. Теперь мысленно извлекаем элементы `b` из последовательности [a1][a2][a3][a4] и вставляем их по одному обратно в правильные места в такой очередности: b1, b3, b2, b4. 3.1. b1 уже находился на своем месте, поэтому мы вставляем его обратно без сравнения вообще [b1][a1][a2][a3][a4] 3.2. b3 (который меньше a3) должен попасть куда-то до a3. На бинарный поиск места для вставки среди 3 элементов надо 2 сравнения. Тут могут получиться разные варианты: [b3][b1][a1][a2][a3][a4] [b1][b3][a1][a2][a3][a4] [b1][a1][b3][a2][a3][a4] [b1][a1][a2][b3][a3][a4] 3.3. b2 (который меньше a2) должен попасть куда-то до a2. Обратите внимание, что область поиска в любом случае - 3 или 2 элемента. На бинарный поиск места для вставки надо 2 сравнения. Количество возможных исходов тут вырастает и я их "рисовать" не буду. 3.4. b4 (который меньше a4) должен попасть куда-то до a4. Тут просто делается бинарный поиск места для вставки среди 6 элементов, на который надо 3 сравнения. Все. Итого 4+5+2+2+3 = 16 сравнений. Уменьшение количества сравнений возникает за счет хитрого выбора порядка вставки элементов `b` обратно в последовательность. И порядок этот диктуется так называемыми Числами Якобсталя. 3

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	14.11.2016, 12:46	6
	Сообщение от TheCalligrapher Ну алгоритм тут довольно хитрый (описан у Кнута) и с не очень большой практической ценностью Есть подозрение, что подобные алгоритмы разрабатывают для реализации в железе, а не в софте 0

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,068
	14.11.2016, 12:51	7
	Сообщение от Evg Есть подозрение, что подобные алгоритмы разрабатывают для реализации в железе, а не в софте Трудно сказать... При упоминании железа на ум сразу приходят сети сортировки. Но в сетях сортировки порядок сравнений жестко прошит заранее и из-за этого сравнений (компараторов) получается больше. 8 элементов - 19 компараторов минимум. 0

zer0mail 2664 / 2239 / 240 Регистрация: 03.07.2012 Сообщений: 8,141 Записей в блоге: 1
	14.11.2016, 16:27	8
	Интересно, можно ли отсортировавать: элементов сравнений 5......................7 6.....................10 7.....................13 0

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,068
	14.11.2016, 19:12	9
	Сообщение от zer0mail Интересно, можно ли отсортировавать: элементов сравнений 5......................7 6.....................10 7.....................13 Да, можно. 0

zer0mail 2664 / 2239 / 240 Регистрация: 03.07.2012 Сообщений: 8,141 Записей в блоге: 1
	14.11.2016, 19:22	10
	Теория информации определяет нижнюю границу (в правом столбике). Но нижняя граница не всегда достижима.. 0

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,068
	14.11.2016, 19:31	11
	Сообщение от zer0mail Теория информации определяет нижнюю границу (в правом столбике). Но нижняя граница не всегда достижима.. Таблица справа в https://en.wikipedia.org/wiki/... ort_a_list содержит известные результаты. Расхождение с теоретической нижней границей начинается с 12 элементов, но периодически возвращается на границу. 1

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	14.11.2016, 19:46	12
	Сообщение от TheCalligrapher При упоминании железа на ум сразу приходят сети сортировки. Но в сетях сортировки порядок сравнений жестко прошит заранее и из-за этого сравнений (компараторов) получается больше В железных алгоритмах (например, в микросхеме), насколько я понимаю, наиболее критичным является количество тактов. Типа того, что 4 сравнения можно выполнять параллельно (одновременно) 0

	03.12.2016, 22:18

@bellaps 0 / 0 / 0 Регистрация: 28.10.2016 Сообщений: 7
	14.11.2016, 20:05 [ТС]	13
	TheCalligrapher, "Тут просто делается бинарный поиск места для вставки среди 6 элементов, на который надо 3 сравнения." Я не совсем поняла, как это достижимо? Если, например, у меня ряд [b1] [b2] [a1] [a2] [b3] [a3] [a4], то с чем именно мне сравнивать b4,чтобы получилось за 3 срнвнения? 0

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,068
	14.11.2016, 20:37	14
	Сообщение от bellaps Если, например, у меня ряд [b1] [b2] [a1] [a2] [b3] [a3] [a4], то с чем именно мне сравнивать b4,чтобы получилось за 3 срнвнения? b4 заведомо меньше, чем a4. То есть вам надо вставить b4 слева от a4. Это запросто делается бинарным поиском за 3 сравнения. Например, в вашем варианте, начнем со сравнения с a2 Код b4 < a2 => b4 < b2 => b4 < b1 - вставляем слева от b1 => b4 > b1 - вставляем слева от b2 => b4 > b2 => b4 < a1 - вставляем слева от a1 => b4 > a1 - вставляем слева от a2 b4 > a2 => b4 < b3 - вставляем слева от b3 => b4 > b3 => b4 < a3 - вставляем слева от a3 => b4 > a3 - вставляем слева от a4 0

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,068
	03.12.2016, 22:18	16
	Сообщение от bellaps Но разве это не 5 сравнений? Ведь сравниваем а4 с 5 остальными элементами.. Ничего не понял. Какое еще a4? a4 мы вообще не трогаем. И откуда взялось 5? Приведенная диаграмма - это это диаграмма "ветвления" выполняющегося кода (блок-схема, если хотите). Диаграмма выполняется слева-направо. Какой бы мы путь выполнения слева-направо ни выбрали, количество фактически выполненных сравнений равно 3 (или 2). Сообщение от bellaps Добавлю, что задание расположить элементы в возрастающей последовательности,сравнивая и перестанавливая после сравнения. Ну тут вы уже начинаете изобретать что-то новенькое. Приведенный мною выше алгоритм работает именно так - сравнивает и переставляет. А уж сколько перестановок он выполняет после каждого сравнения - это деталь реализации, к нашему разговору пока никакого отношения не имевшая. Минимизация количества сравнений и минимизация количества перестановок - две очень разные, независимые темы. Пока что о минимизация количества перестановок речи не шло вообще. Что же касается минимизация количества сравнений, то для 8 элементов меньше 16 получить невозможно и алгоритм приведен выше. 1

Отсортировать 8 чисел только 16 сравнениями

Решение