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

@freewrestler · Регистрация: 10.11.2011

Студворк — интернет-сервис помощи студентам

Дан список сел и расстояния до них от города. Нужно вывести села в порядке удаленности от города. Городов до 10^8. Расстояния - целые числа, <= 10^6

@~~IrineK~~ · 12.04.2014, 07:34

Не по теме:

Сообщение от freewrestler

Городов до 10^8

Это для императора галактики?
На земле столько городов нет: http://www.statisticbrain.com/... the-world/

@freewrestler · 12.04.2014, 07:35 **[ТС]**

Условие задачи таково

@~~IrineK~~ · 12.04.2014, 07:39

freewrestler,
Разъясните, у вас городов 10^8 и у каждого города - свои села
или
у вас город один и у него 10^8 сел?

@freewrestler · 12.04.2014, 07:48 **[ТС]**

Есть один город. А затем села - у каждого собственное название и определенное расстояние от этого города. Нам дано количество сел N( 1 <= N <= 10^8), а также даны названия этих сел и расстояние для каждого села до города. Нужно вывести список сел в порядке удаленности. К примеру:

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

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

Добавлено через 4 минуты
Нужно сделать структурами, создать функцию сортировки, а после ввода данных вызвать эту функцию. Но к сожалению реализовать не могу..

@~~IrineK~~ · 12.04.2014, 07:51

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

@freewrestler · 12.04.2014, 07:52 **[ТС]**

а ну тогда совсем молчу ))

@~~IrineK~~ · 12.04.2014, 08:02

Если будете сортировать как обычно - это долго.

Добавлено через 10 минут

Сообщение от freewrestler

ну тогда совсем молчу

Если можно пользоваться STL, то не так уж страшно.

Если в задании указано, что нужно написать все самому - тогда немного страшнее.

@freewrestler · 12.04.2014, 08:04 **[ТС]**

STL-ом пользоваться думаю можно, а об обязательстве решения самому не сказано)

@dzrkot · 12.04.2014, 08:16

sort();

@freewrestler · 12.04.2014, 08:17 **[ТС]**

sort - Timelimit exceeded =))

@~~IrineK~~ · 12.04.2014, 08:44

Сортировки дают кво операций ~ N²
Если у вас N = 10⁸, то N² = 10¹⁶
Комп способен на порядка 10⁷ в секунду.
Значит, вам нужно 10⁹ секунд = 32 года.

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

При N = 10⁸ М = 1 + 8*log₂10 = 1 + 8*3,3 = 28 операций
Поскольку, список нарастает от 1 до N, среднее кво операций равно половине этой величины, т.е. 14 операций на одну вставку.
Для N вставок: 14 * 10⁸ операций
Комп справится за 140 с.

@freewrestler · 12.04.2014, 08:45 **[ТС]**

а 140 секунд это разве мало?)

@~~IrineK~~ · 12.04.2014, 08:47

Все познается в сравнении.
Если мысленно представить 32 года и 140 секунд, то ответ очевиден.

@freewrestler · 12.04.2014, 08:47 **[ТС]**

С этим полностью согласен)

@Voivoid · 12.04.2014, 11:20

Сортировки дают кво операций ~ $https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{2}$

Почему сразу квадрат? N log N же ( не, ну я не спорю, есть и алгоритмы с квадратичной сложностью, но кто их будет использовать - сам себе злобный буратина )

@~~IrineK~~ · 12.04.2014, 12:36

N log N заявлена в sort
Но

Сообщение от freewrestler

sort - Timelimit exceeded =))

Значит, надо искать другие пути.

Добавлено через 6 минут
Voivoid,
сложность N log N достигается в среднем. Но возможны "худшие" случаи. Тогда сортировка деградирует до N².
Например, для быстрой сортировки можно почитать здесь.

@Voivoid · 12.04.2014, 17:09

Ну, например для merge sort N log N даже в худшем случае. А для quick sort да, асимптотика действительно в ряде случаев вырождается до квадратичной, но с этим давным давно уже научились бороться, сейчас в библиотеках quick sort в чистом виде нигде не используются, везде применяются разного рода ухищрениях позволяющие избавиться от квадратичной сложности.

А по поводу задачи, то думаю имеет смысл попробовать counting sort. Если ограничения по памяти нет, то должно прокатить

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	12.04.2014, 08:47 [ТС]	15
	С этим полностью согласен) 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
		1
	Сортировка списка 12.04.2014, 04:55. Показов 1177. Ответов 17 Метки нет (Все метки) Дан список сел и расстояния до них от города. Нужно вывести села в порядке удаленности от города. Городов до 10^8. Расстояния - целые числа, <= 10^6 0

@~~IrineK~~
	12.04.2014, 07:34 #2
	Не по теме: Сообщение от freewrestler Городов до 10^8 Это для императора галактики? На земле столько городов нет: http://www.statisticbrain.com/... the-world/ 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	12.04.2014, 07:35 [ТС]	3
	Условие задачи таково 0

@~~IrineK~~ Заблокирован
	12.04.2014, 07:39	4
	freewrestler, Разъясните, у вас городов 10^8 и у каждого города - свои села или у вас город один и у него 10^8 сел? 0

@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 минуты Нужно сделать структурами, создать функцию сортировки, а после ввода данных вызвать эту функцию. Но к сожалению реализовать не могу.. 0

@~~IrineK~~ Заблокирован
	12.04.2014, 07:51	6
	Количество намекает на то, что нужно создавать стек, а затем вставлять следующий пункт, используя бинарный поиск. 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	12.04.2014, 07:52 [ТС]	7
	а ну тогда совсем молчу )) 0

@~~IrineK~~ Заблокирован
	12.04.2014, 08:02	8
	Если будете сортировать как обычно - это долго. Добавлено через 10 минут Сообщение от freewrestler ну тогда совсем молчу Если можно пользоваться STL, то не так уж страшно. Если в задании указано, что нужно написать все самому - тогда немного страшнее. 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	12.04.2014, 08:04 [ТС]	9
	STL-ом пользоваться думаю можно, а об обязательстве решения самому не сказано) 0

@dzrkot zzzZZZ... 527 / 358 / 94 Регистрация: 11.09.2013 Сообщений: 2,041
	12.04.2014, 08:16	10
	sort(); 0

Опции темы

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	12.04.2014, 08:17 [ТС]	11
	sort - Timelimit exceeded =)) 0

@~~IrineK~~ Заблокирован
	12.04.2014, 08:44	12
	Сортировки дают кво операций ~ N² Если у вас N = 10⁸, то N² = 10¹⁶ Комп способен на порядка 10⁷ в секунду. Значит, вам нужно 10⁹ секунд = 32 года. Добавлено через 10 минут Кво операций при бинарном поиске по N элементам 1 + log₂N Искать будем по списку, т.е. среднее кво операций будет вполовину меньше. Нужно расставить N элементов, т.е. общее кво операций N(1 + log₂N) / 2 При N = 10⁸ М = 1 + 8log₂10 = 1 + 83,3 = 28 операций Поскольку, список нарастает от 1 до N, среднее кво операций равно половине этой величины, т.е. 14 операций на одну вставку. Для N вставок: 14 * 10⁸ операций Комп справится за 140 с. 0

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126
	12.04.2014, 08:45 [ТС]	13
	а 140 секунд это разве мало?) 0

@~~IrineK~~ Заблокирован
	12.04.2014, 08:47	14
	Все познается в сравнении. Если мысленно представить 32 года и 140 секунд, то ответ очевиден. 0

@Voivoid 710 / 283 / 16 Регистрация: 31.03.2013 Сообщений: 1,340
	12.04.2014, 11:20	16
	Сортировки дают кво операций ~ $https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{2}$ Почему сразу квадрат? N log N же ( не, ну я не спорю, есть и алгоритмы с квадратичной сложностью, но кто их будет использовать - сам себе злобный буратина ) 0

@~~IrineK~~ Заблокирован
	12.04.2014, 12:36	17
	N log N заявлена в sort Но Сообщение от freewrestler sort - Timelimit exceeded =)) Значит, надо искать другие пути. Добавлено через 6 минут Voivoid, сложность N log N достигается в среднем. Но возможны "худшие" случаи. Тогда сортировка деградирует до N². Например, для быстрой сортировки можно почитать здесь. 0

@Voivoid 710 / 283 / 16 Регистрация: 31.03.2013 Сообщений: 1,340
	12.04.2014, 17:09	18
	Ну, например для merge sort N log N даже в худшем случае. А для quick sort да, асимптотика действительно в ряде случаев вырождается до квадратичной, но с этим давным давно уже научились бороться, сейчас в библиотеках quick sort в чистом виде нигде не используются, везде применяются разного рода ухищрениях позволяющие избавиться от квадратичной сложности. А по поводу задачи, то думаю имеет смысл попробовать counting sort. Если ограничения по памяти нет, то должно прокатить 0