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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
#1

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

12.04.2014, 04:55. Просмотров 488. Ответов 17
Метки нет (Все метки)

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

Сортировка списка - C++
Здравствуйте, не совсем понимаю как должна быть реализована сортировка вставками в деке. Что имеется на данный момент: class List...

Сортировка списка - C++
Получается, что пользователь вносит книги в библиотеку, записывая имя писателя, название, год издания и тд... После чего он может...

Сортировка списка - C++
Народ нужна помощь :) Элементы списка представлены следующим образом: class Node { public: char *name; Node *next; ...

Сортировка списка - C++
Здравствуйте!!! Прошу помочь мне написать алгоритм сортировки односвязного списка. Задание такое: необходимо из элементов трёх списков...

Сортировка списка - C++
помогите сделать сортировку по возрасту, а то ничего не выходит #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; struct...

Сортировка списка - C++
Люди помогите плиз я уже не могу!! надо сортировать список!!! Останьные недоработки тоже можете указать. Вот код Жду ответов) ...

Сортировка списка - C++
Всем привет) Нужно реализовать сортировку списка, линейного однонаправленного. Написал, но что-то как-то не правильно... void...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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...
518 / 348 / 53
Регистрация: 11.09.2013
Сообщений: 1,995
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
673 / 276 / 12
Регистрация: 31.03.2013
Сообщений: 1,339
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++
Приветствую всех! Есть небольшая проблема: не могу понять, как создать сортировку в алфавитном порядке. Вот код: void SortList() { ...

Сортировка списка - C++
Привет, всем.. Ребята помогите у подруги зачет по программированию ей надо решить задачку.. Информационное поле элемента...

Сортировка списка - C++
Помогите пожалуйста, нужна сортировка методом вставок односвязанного кольцевого списка, не пойму как делать. Со списками ток начал...

Сортировка списка - C++
Всем привет задание такое Разработать программу работы со связным списком сеансов в кинотеатре. Для каждого сеанса должна храниться...

Сортировка связного списка - C++
Привет всем! как правильно написать сортировку для связного циклического списка ? помогите пожалуйста... #include &lt;iostream&gt; using...


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

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru