Автор Тема: Устойчивая сортировка  (Прочитано 2240 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Устойчивая сортировка
« : ПЭТРам 24, 2009, 07:07:09 pm »
Пишу рефер по сортировке. Вроде все основные алгоритмы разобрал. Ну вот единственное, не могу нигде найти зачем нужна именно устойчивая сортировка. Кто может помочь, хотя бы один пример, самый легкий, где нужен алгоритм устойчивой сортировки. Прошу не реализацию, а жизненный пример, где она применяется, или ссылки. (А самое лучшое пример, где без неё не обойтись.)
   У меня в справочнике Шилдта, говорится, что она нужна напр, при сортировке по двум ключам, например база данных отсортирована по почтовым индексам - это главный ключ, а под каждым индексом еще отсортированы фамилии. Далее говорится, что при добавлении в такую базу нового адреса и пересортировки, порядок подключей (т.е фамилий внутри индекса) менятся не должен. Но что-то я этого не понимаю :no:.
« Последнее редактирование: ПЭТРам 24, 2009, 07:11:51 pm от Alex_cs_gsp »
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн gigauser

  • Статский советник
  • *****
  • Сообщений: 976
  • Репутация: 20
  • Banned
Re: Устойчивая сортировка
« Ответ #1 : ПЭТРам 24, 2009, 08:44:14 pm »
она нужна напр, при сортировке по двум ключам, например база данных отсортирована по почтовым индексам - это главный ключ, а под каждым индексом еще отсортированы фамилии.
а что непонятного-то? в блок с индексами напрример 192168 добавляется новая запись, это ускоряет вставку, т.к. нет необходиомсти проверять всю базу снова, а сам блок уже отсортирован.
элементарный пример такой сортировки - quicksort, на некоторых набрах она является оптимальной по скорости выполнения. Имхо, устойчивость алгоритма сортировки не может быть критичной по сравненнию со скоростью работы хотя бы.
Banned

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Устойчивая сортировка
« Ответ #2 : ПЭТРам 24, 2009, 09:21:05 pm »
А устойчивость в данном случае нужна только для того, если кому-то в голову взбредёт снова отсортировать, и всё? Или есть, что-то посерьёзнее?
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн gigauser

  • Статский советник
  • *****
  • Сообщений: 976
  • Репутация: 20
  • Banned
Re: Устойчивая сортировка
« Ответ #3 : ПЭТРам 24, 2009, 09:28:59 pm »
А устойчивость в данном случае нужна только для того, если кому-то в голову взбредёт снова отсортировать, и всё?
нет, это нужно например для оптимизации вставки например, когда данных много и они часто, но незначительно меняются.
все вышесказанное исключительно ИМХО.
Banned

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Устойчивая сортировка
« Ответ #4 : ПЭТРам 24, 2009, 10:21:37 pm »
Не могу сообразить, если будут добавляться новые данные то индексы, в независимости от устойчивости сортировки, поменяются и ссылки все-равно прийдется обновлять, в чем оптимизация?
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Устойчивая сортировка
« Ответ #5 : ПЭТРам 24, 2009, 11:50:53 pm »
Может я неправильно понимаю вопрос но:
Вот смотри приведенную уже в пример быстрою сортировку если взять, лучше всего она сработает на несортированных данных (из личного исследования трудоемкости) а на сортированных, она себя ведет гораздо хуже. А представь,  есть здоровенная база данных (ну например самопальная, причем записей тысяч 5) и тебе надо ее отсортировать. Вот в первый раз (допустим по задачи, ну и по жизни) вся эта база не сортированна (не в смысле операции, а тупо при добавлении небыло контсроля). Ну и быстрой сортировкой прошлись по базе (отсортировали по ключу). Далее добавили в базу пару тройку сотен запесей и нам надо ее отсортировать.
Вопрос: Как хорошо сработает быстрая сортировка?
ПСЫ. все это конечно только для примера.
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Устойчивая сортировка
« Ответ #6 : ПЭТРам 25, 2009, 12:12:11 am »
Устойчивым можно сделать любой алгоритм сортировки, не обязательно только быструю. Тут вопрос в принципе, зачем алгоритму быть устойчивым (или для каких случаев?). Может это было нужно для каких-то древних баз, когда структур не существовало.
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Устойчивая сортировка
« Ответ #7 : ПЭТРам 25, 2009, 12:13:54 am »
Цитировать
Может это было нужно для каких-то древних баз, когда структур не существовало.
Следом вопрос. А как работают современные СУБД?
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Устойчивая сортировка
« Ответ #8 : ПЭТРам 25, 2009, 12:18:37 am »
 Логический доступ ко всем и каждому элементу данных (атомарному значению) в реляционной базе данных должна обеспечиваться путем использования комбинации имени таблицы, первичного ключа и имени столбца
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн Inf-root

  • Глобальный модератор
  • Коллежский советник
  • *****
  • Сообщений: 571
  • Репутация: 21
  • Пол: Мужской
Re: Устойчивая сортировка
« Ответ #9 : ПЭТРам 25, 2009, 12:24:19 am »
Цитировать
Логический доступ ко всем и каждому элементу данных (атомарному значению) в реляционной базе данных должна обеспечиваться путем использования комбинации имени таблицы, первичного ключа и имени столбца
:D
А при помощи чего этого добиваются. Ты не путай алгоритм и структуру данных. Нет, ну у деревьев и у списков алгоритмы разные. но все же. например таблицу можно представить как список, но можно представить как и дерево.
В старости нет лучшего утешения,
чем сознание того, что все силы в
молодости отданы делу, которое не
стареет.
(с) Артур Шопенгауэр (немецкий философ)

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Устойчивая сортировка
« Ответ #10 : ПЭТРам 25, 2009, 12:40:02 am »
Должно быть, если использовать неустойчивую сортировку, то нарушиться структура???? Не понимаю.
Когда вы с собой разговариваете, вы получаете информацию?