Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Сортировки какой использовать алгоритм
Ответ
 
Опции темы Опции просмотра
  (#16 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 19.04.2008, 17:15

Цитата:
Да... Мощный алгоритм. Больше всего мне нравится его время работы в наихудшем случае - бесконечность ...
не бесконечность, а кол-во перестановок данных элементов.
На прологе такую сортировку пишут - ничё, работает...
Ответить с цитированием
  (#17 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 19.04.2008, 21:49

Цитата:
не бесконечность, а кол-во перестановок данных элементов.
На прологе такую сортировку пишут - ничё, работает...
Значит я не понял сути. Каждый раз элементы переставляются рандомно?
Ответить с цитированием
  (#18 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 19.04.2008, 23:54

можно и рандомно, можно просто перебирать все возможные перестановки.
Ответить с цитированием
  (#19 (permalink)) Старый
andriano andriano вне форума
Member
 
Сообщений: 227
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 13.02.2006
По умолчанию 20.04.2008, 21:51

Цитата:
Представляешь, увидишь на форуме сообщение:
- Народ, помогите решить задачку. Есть массив из трёх чисел - отсортировать его
А что, форум - это единственное место, где может потребоваться решить какую-нибудь задачу?
Практический ример: при софтверном рендере надо отсортировать вершины треуголтника по y-координате. Чем будешь сортировать?
Ответить с цитированием
  (#20 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 20.04.2008, 23:34

Цитата:
Предложи более быстрый способ сортировки массива из трех элементов.
Сортировка вставкой отработает как минимум не хуже для трёх элементов. А для бОльшего числа элементов - лучше.
Ответить с цитированием
Ads.
  (#21 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 21.04.2008, 20:03

Цитата:
можно и рандомно, можно просто перебирать все возможные перестановки.
Вот если рандомно. то время работы в наихудшем случае - бесконечность.
Ответить с цитированием
  (#22 (permalink)) Старый
andriano andriano вне форума
Member
 
Сообщений: 227
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 13.02.2006
По умолчанию 23.04.2008, 22:48

Цитата:
Сортировка вставкой отработает как минимум не хуже для трёх элементов. А для бОльшего числа элементов - лучше.
Хорошо, давай сравним:
Код:
type
  vertex = record
    x,y : integer;
  end;
  triangle = array[0..2]of vertex;
var t : triangle;
begin
  if t[0].y > t[1].y then
    swap(t[0],t[1]);
  if t[1].y > t[2].y then begin 
    swap(t[1],t[2]);
    if t[0].y > t[1].y then
      swap(t[0],t[1]);
  end;
end;
Предложи свой вариант вставками.
Ответить с цитированием
  (#23 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 24.04.2008, 12:16

Ок, вызов принимаю!

Твой вариант в худшем случае осуществляет 3 сравнения и 3 перестановки.
Здравый смысл подсказывает, что массив из 3х элементов всегда можно упорядочить 2мя перестановками.
Вот мой вариант:

Код:
int a[ 3 ] = { 1, 2, 3 };

int k = ( a[ 1 ] < a[ 2 ] ) ? 1 : 2;
if ( a[ 0 ] < a[ k ] )
    { std::swap( a[ 0 ], a[ k ] ); }
if ( a[ 1 ] > a[ 2 ] )
    { std::swap( a[ 1 ], a[ 2 ] ); }
У меня в худшем случае 3 сравнения и 2 перестановки.

А вообще, ни твой ни мой варианты не являются алгоритмами сортировок. Это лишь очень частные случаи.
Ответить с цитированием
  (#24 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 24.04.2008, 22:16

могу предложить вариант как отсортировать массив за два такта.
Ответить с цитированием
Ads
  (#25 (permalink)) Старый
andriano andriano вне форума
Member
 
Сообщений: 227
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 13.02.2006
По умолчанию 25.04.2008, 23:00

Цитата:
Ок, вызов принимаю!
Ну, для современных суперскалярных процессоров наиболее дорогая операция - это сравнение. У тебя их всегда 3, а у меня в среднем 2.5. Это во-первых.
А во вторых, ты готов показать, что приведенный тобой алгоритм является реализацией именно алгоритма сортировки вставками?
Ответить с цитированием
  (#26 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 26.04.2008, 13:36

Цитата:
Ну, для современных суперскалярных процессоров наиболее дорогая операция - это сравнение. У тебя их всегда 3, а у меня в среднем 2.5. Это во-первых.
Откуда дровишки? Ссылки?

Цитата:
А во вторых, ты готов показать, что приведенный тобой алгоритм является реализацией именно алгоритма сортировки вставками?
Это частный случай сортировки вставками. Точно так же, как и твой код - частный случай сортировки пузырьком.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм сортировки шелла на Xlisp qas Lisp 0 18.05.2011 18:04
Какой алгоритм использовать для выделения объектов на изображении max1 Вопросы начинающих программистов 0 05.02.2011 17:31
Какой флюс использовать? Wildd Любые вопросы от новичков 2 22.08.2010 12:12
Как к программе написать алгоритм сортировки marisha26 Visual C++ 1 18.11.2009 15:00
Время, графика, рандом какой использовать алгоритм 1122 С/С++ 5 10.06.2008 10:43
Алгоритм сортировки слиянием на С++ 5u1c1de Вопросы начинающих программистов 2 03.02.2008 00:43
Алгоритм художника, метод сортировки по глубине Freemanson С/С++ 12 12.04.2007 10:38
Сравнение сортировки слиянием из PFC и сортировки на основе rbt Винитарх Prolog 1 14.03.2007 14:29
Какой алгоритм сортирует массивы cv6 Алгоритмы 12 27.04.2006 20:11
Какой драйвер в DBE использовать для DBF Legos Delphi 0 24.11.2005 16:50
Алгоритм сортировки и поиска в больших числах noirum Вопросы начинающих программистов 9 19.11.2005 16:04
Самый быстрый алгоритм сортировки массива RENegade С/С++ 5 01.11.2005 12:14



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов