Мини-сортировка -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [3.149.239.209]

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray

Новое голосование

Мини-сортировка , Отсортировать массив из 5 элементов...

albom

Сообщ. #1 , 22.11.03, 19:43

Senior Member

Профиль · PM

Поощрения: 2 Dgm

Рейтинг (т): 20

Нужно отсортировать массив из пяти элементов (пусть это будут целые числа), используя только семь сравнений.
Как тут быть? Как постоить алгоритм сортировки массива с фиксированой длинной за наименьшее количество сравнений (для длинны 5, минимум сравнений - 7)?

Заранее спасибо.

Sazabis

Сообщ. #2 , 24.11.03, 07:49

Master

Профиль · PM

Поощрения: 9 Dgm

Рейтинг (т): 122

--
сраниваешь 2 пары если надо меняешь их местами, так чтобы они были упорядочены, скажем упорядочиваем их по возрастанию.

Использовали 2 сранения. Имеем 1<2, 3<4, 5

--
вставляем последний элемент, скажем, в первую, пару.

Использовали еще 2 сравнения (max) итого 4. Имеем 1<2<3, 4<5

--
всавляем первый эл. второй пары в первую последовательность, нужно от 1 до 3 сравнений, так как второй эл. не надо сравнивать с числами меньше первого, то вставка его займет оставшиеся до трех сравнения (max)

итого 7 сравнений.

AntSecam

Сообщ. #3 , 24.11.03, 08:07

Unregistered

Пожалуйста поподробнее:

Цитата

сраниваешь 2 пары если надо меняешь их местами, так чтобы они были упорядочены, скажем упорядочиваем их по возрастанию.

Использовали 2 сранения. Имеем 1<2, 3<4, 5

Цитата

вставляем последний элемент, скажем, в первую, пару.

Использовали еще 2 сравнения (max) итого 4. Имеем 1<2<3, 4<5

Цитата

всавляем первый эл. второй пары в первую последовательность, нужно от 1 до 3 сравнений

В худшем случае 3, итого 7, ВОПРОС: куда девать последний элемент?

Sazabis	Сообщ. #4 , 24.11.03, 08:19
Master Профиль · PM Поощрения: 9 Dgm Рейтинг (т): 122	немного напутал тут все наглядно написано: algolist Сообщение отредактировано: Sazabis - 24.11.03, 08:56

1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution time: 0,0169 ] [ 14 queries used ] [ Generated: 27.07.24, 13:13 GMT ]