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

@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. Если ограничения по памяти нет, то должно прокатить

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@freewrestler 3 / 3 / 0 Регистрация: 10.11.2011 Сообщений: 126

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

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

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	12.04.2014, 07:39
	freewrestler, Разъясните, у вас городов 10^8 и у каждого города - свои села или у вас город один и у него 10^8 сел? 0

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

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	12.04.2014, 07:51
	Количество намекает на то, что нужно создавать стек, а затем вставлять следующий пункт, используя бинарный поиск. 0

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

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

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

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

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	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 + 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 [ТС]
	а 140 секунд это разве мало?) 0

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	12.04.2014, 08:47
	Все познается в сравнении. Если мысленно представить 32 года и 140 секунд, то ответ очевиден. 0

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

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