Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
bellaps
0 / 0 / 0
Регистрация: 28.10.2016
Сообщений: 6
14.11.2016, 01:14     Отсортировать 8 чисел только 16 сравнениями #1
Как отсортировать 8 чисел только 16 сравнениями?? Может у кого есть идеи?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.11.2016, 01:14     Отсортировать 8 чисел только 16 сравнениями
Посмотрите здесь:

C++ Отсортировать по убыванию только элементы вектора, расположенные на чётных позициях
Ввести n положительных целых чисел. Найти количество чисел, записанных только четными цифрами C++
Отсортировать только простые числа в массиве C++
C++ Отсортировать текст и вывести только согласные буквы
C++ Определить, что только одно из чисел А и В четное и каждое из чисел А,В,С кратно трем.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
afront
676 / 638 / 230
Регистрация: 29.02.2016
Сообщений: 2,068
14.11.2016, 10:33     Отсортировать 8 чисел только 16 сравнениями #2
обычна сортировка выбором для случая когда нужно все переставить сделает именно столько сравнений.
если начальное расположение цифр будет иным и какие то цифры стоят на "своем" месте - сравнений будет меньше

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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-
Не Эксперт C++
1473 / 618 / 174
Регистрация: 24.08.2014
Сообщений: 2,512
Записей в блоге: 1
Завершенные тесты: 2
14.11.2016, 10:37     Отсортировать 8 чисел только 16 сравнениями #3
afront, А почему вы прибавляете count, только если условие дало true?
Ведь сравнение есть, независимо от того, истину оно дало, или ложь.
afront
676 / 638 / 230
Регистрация: 29.02.2016
Сообщений: 2,068
14.11.2016, 11:16     Отсортировать 8 чисел только 16 сравнениями #4
GbaLog-, да, я не прав, посчитал перестановки
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2787 / 1433 / 393
Регистрация: 18.10.2014
Сообщений: 2,639
14.11.2016, 12:34     Отсортировать 8 чисел только 16 сравнениями #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от 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
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
14.11.2016, 12:46     Отсортировать 8 чисел только 16 сравнениями #6
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ну алгоритм тут довольно хитрый (описан у Кнута) и с не очень большой практической ценностью
Есть подозрение, что подобные алгоритмы разрабатывают для реализации в железе, а не в софте
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2787 / 1433 / 393
Регистрация: 18.10.2014
Сообщений: 2,639
14.11.2016, 12:51     Отсортировать 8 чисел только 16 сравнениями #7
Цитата Сообщение от Evg Посмотреть сообщение
Есть подозрение, что подобные алгоритмы разрабатывают для реализации в железе, а не в софте
Трудно сказать... При упоминании железа на ум сразу приходят сети сортировки. Но в сетях сортировки порядок сравнений жестко прошит заранее и из-за этого сравнений (компараторов) получается больше. 8 элементов - 19 компараторов минимум.
zer0mail
2185 / 1868 / 187
Регистрация: 03.07.2012
Сообщений: 6,640
Записей в блоге: 1
14.11.2016, 16:27     Отсортировать 8 чисел только 16 сравнениями #8
Интересно, можно ли отсортировавать:
элементов сравнений
5......................7
6.....................10
7.....................13
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2787 / 1433 / 393
Регистрация: 18.10.2014
Сообщений: 2,639
14.11.2016, 19:12     Отсортировать 8 чисел только 16 сравнениями #9
Цитата Сообщение от zer0mail Посмотреть сообщение
Интересно, можно ли отсортировавать:
элементов сравнений
5......................7
6.....................10
7.....................13
Да, можно.
zer0mail
2185 / 1868 / 187
Регистрация: 03.07.2012
Сообщений: 6,640
Записей в блоге: 1
14.11.2016, 19:22     Отсортировать 8 чисел только 16 сравнениями #10
Теория информации определяет нижнюю границу (в правом столбике). Но нижняя граница не всегда достижима..
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2787 / 1433 / 393
Регистрация: 18.10.2014
Сообщений: 2,639
14.11.2016, 19:31     Отсортировать 8 чисел только 16 сравнениями #11
Цитата Сообщение от zer0mail Посмотреть сообщение
Теория информации определяет нижнюю границу (в правом столбике). Но нижняя граница не всегда достижима..
Таблица справа в

https://en.wikipedia.org/wiki/Compar...to_sort_a_list

содержит известные результаты. Расхождение с теоретической нижней границей начинается с 12 элементов, но периодически возвращается на границу.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
14.11.2016, 19:46     Отсортировать 8 чисел только 16 сравнениями #12
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
При упоминании железа на ум сразу приходят сети сортировки. Но в сетях сортировки порядок сравнений жестко прошит заранее и из-за этого сравнений (компараторов) получается больше
В железных алгоритмах (например, в микросхеме), насколько я понимаю, наиболее критичным является количество тактов. Типа того, что 4 сравнения можно выполнять параллельно (одновременно)
bellaps
0 / 0 / 0
Регистрация: 28.10.2016
Сообщений: 6
14.11.2016, 20:05  [ТС]     Отсортировать 8 чисел только 16 сравнениями #13
TheCalligrapher, "Тут просто делается бинарный поиск места для вставки среди 6 элементов, на который надо 3 сравнения."
Я не совсем поняла, как это достижимо?
Если, например, у меня ряд [b1] [b2] [a1] [a2] [b3] [a3] [a4], то с чем именно мне сравнивать b4,чтобы получилось за 3 срнвнения?
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2787 / 1433 / 393
Регистрация: 18.10.2014
Сообщений: 2,639
14.11.2016, 20:37     Отсортировать 8 чисел только 16 сравнениями #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
bellaps
0 / 0 / 0
Регистрация: 28.10.2016
Сообщений: 6
03.12.2016, 21:56  [ТС]     Отсортировать 8 чисел только 16 сравнениями #15
Добавлено через 1 минуту
TheCalligrapher, Добрый день! Снова всплыл вопрос. Но разве это не 5 сравнений? Ведь сравниваем а4 с 5 остальными элементами..

Добавлено через 6 минут
Добавлю, что задание раположить элементы в возрастающей последовательности,сравнивая и перестанавливая после сравнения. В visual basic. Типа:
If a>b then
x=a
a=b
b=x
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2016, 22:18     Отсортировать 8 чисел только 16 сравнениями
Еще ссылки по теме:

Отсортировать только положительные элементы масива по росту C++
C++ Отсортировать по возрастанию только положительные элементы массива
C++ Отсортировать по возрастанию только четные элементы массива

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2787 / 1433 / 393
Регистрация: 18.10.2014
Сообщений: 2,639
03.12.2016, 22:18     Отсортировать 8 чисел только 16 сравнениями #16
Цитата Сообщение от bellaps Посмотреть сообщение
Но разве это не 5 сравнений? Ведь сравниваем а4 с 5 остальными элементами..
Ничего не понял. Какое еще a4? a4 мы вообще не трогаем.

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

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

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

Что же касается минимизация количества сравнений, то для 8 элементов меньше 16 получить невозможно и алгоритм приведен выше.
Yandex
Объявления
03.12.2016, 22:18     Отсортировать 8 чисел только 16 сравнениями
Ответ Создать тему
Опции темы

Текущее время: 18:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru