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

Сортировка списка - C++

Восстановить пароль Регистрация
 
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 04:55     Сортировка списка #1
Дан список сел и расстояния до них от города. Нужно вывести села в порядке удаленности от города. Городов до 10^8. Расстояния - целые числа, <= 10^6
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2014, 04:55     Сортировка списка
Посмотрите здесь:

Сортировка списка C++
C++ Сортировка списка
C++ Сортировка списка
сортировка списка C++
Сортировка списка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
12.04.2014, 07:34
  #2

Не по теме:

Цитата Сообщение от freewrestler Посмотреть сообщение
Городов до 10^8
Это для императора галактики?
На земле столько городов нет: http://www.statisticbrain.com/total-...-in-the-world/

freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 07:35  [ТС]     Сортировка списка #3
Условие задачи таково
IrineK
Заблокирован
12.04.2014, 07:39     Сортировка списка #4
freewrestler,
Разъясните, у вас городов 10^8 и у каждого города - свои села
или
у вас город один и у него 10^8 сел?
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 07:48  [ТС]     Сортировка списка #5
Есть один город. А затем села - у каждого собственное название и определенное расстояние от этого города. Нам дано количество сел N( 1 <= N <= 10^8), а также даны названия этих сел и расстояние для каждого села до города. Нужно вывести список сел в порядке удаленности. К примеру:

Входные данные:
3
Дыбенко 35
Каменномостский 13
Утриш 18

Выходные данные:
Каменномостский 13
Утриш 18
Дыбенко 35

Добавлено через 4 минуты
Нужно сделать структурами, создать функцию сортировки, а после ввода данных вызвать эту функцию. Но к сожалению реализовать не могу..
IrineK
Заблокирован
12.04.2014, 07:51     Сортировка списка #6
Количество намекает на то, что нужно создавать стек, а затем вставлять следующий пункт, используя бинарный поиск.
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 07:52  [ТС]     Сортировка списка #7
а ну тогда совсем молчу ))
IrineK
Заблокирован
12.04.2014, 08:02     Сортировка списка #8
Если будете сортировать как обычно - это долго.

Добавлено через 10 минут
Цитата Сообщение от freewrestler Посмотреть сообщение
ну тогда совсем молчу
Если можно пользоваться STL, то не так уж страшно.

Если в задании указано, что нужно написать все самому - тогда немного страшнее.
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 08:04  [ТС]     Сортировка списка #9
STL-ом пользоваться думаю можно, а об обязательстве решения самому не сказано)
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
12.04.2014, 08:16     Сортировка списка #10
sort();
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 08:17  [ТС]     Сортировка списка #11
sort - Timelimit exceeded =))
IrineK
Заблокирован
12.04.2014, 08:44     Сортировка списка #12
Сортировки дают кво операций ~ N2
Если у вас N = 108, то N2 = 1016
Комп способен на порядка 107 в секунду.
Значит, вам нужно 109 секунд = 32 года.

Добавлено через 10 минут
Кво операций при бинарном поиске по N элементам 1 + log2N
Искать будем по списку, т.е. среднее кво операций будет вполовину меньше.
Нужно расставить N элементов, т.е. общее кво операций
N(1 + log2N) / 2

При N = 108 М = 1 + 8*log210 = 1 + 8*3,3 = 28 операций
Поскольку, список нарастает от 1 до N, среднее кво операций равно половине этой величины, т.е. 14 операций на одну вставку.
Для N вставок: 14 * 108 операций
Комп справится за 140 с.
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 08:45  [ТС]     Сортировка списка #13
а 140 секунд это разве мало?)
IrineK
Заблокирован
12.04.2014, 08:47     Сортировка списка #14
Все познается в сравнении.
Если мысленно представить 32 года и 140 секунд, то ответ очевиден.
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 08:47  [ТС]     Сортировка списка #15
С этим полностью согласен)
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
12.04.2014, 11:20     Сортировка списка #16
Сортировки дают кво операций ~ http://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{2}
Почему сразу квадрат? N log N же ( не, ну я не спорю, есть и алгоритмы с квадратичной сложностью, но кто их будет использовать - сам себе злобный буратина )
IrineK
Заблокирован
12.04.2014, 12:36     Сортировка списка #17
N log N заявлена в sort
Но
Цитата Сообщение от freewrestler Посмотреть сообщение
sort - Timelimit exceeded =))
Значит, надо искать другие пути.

Добавлено через 6 минут
Voivoid,
сложность N log N достигается в среднем. Но возможны "худшие" случаи. Тогда сортировка деградирует до N2.
Например, для быстрой сортировки можно почитать здесь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2014, 17:09     Сортировка списка
Еще ссылки по теме:

C++ Сортировка списка
Сортировка списка C++
Сортировка списка C++

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

Или воспользуйтесь поиском по форуму:
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
12.04.2014, 17:09     Сортировка списка #18
Ну, например для merge sort N log N даже в худшем случае. А для quick sort да, асимптотика действительно в ряде случаев вырождается до квадратичной, но с этим давным давно уже научились бороться, сейчас в библиотеках quick sort в чистом виде нигде не используются, везде применяются разного рода ухищрениях позволяющие избавиться от квадратичной сложности.

А по поводу задачи, то думаю имеет смысл попробовать counting sort. Если ограничения по памяти нет, то должно прокатить
Yandex
Объявления
12.04.2014, 17:09     Сортировка списка
Ответ Создать тему
Опции темы

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