Сортировка методом простых вставок
Сортировка выбором
Сущность метода:
Находится максимальный элемент и меняется местами с первым элементом массива, после чего исключается из рассмотрения. Процесс повторяется до одного элемента.
Алгоритм сортировки выбором по убыванию:
For t:=1 to n-1 do
begin
max:=a[t]; k:=t;
for i:=t+1 to n do
if a[i]>max then begin max:=a[i]; k:=i;
end;
x:=a[t];
a[t]:=a[k];
a[k]:=x;
end;
Сортировка обменом
Сущность метода:
Если два элемента массива расположены не по порядку, то они меняются местами. Процесс повторяется до тех пор, пока элементы не будут упорядочены.
Демонстрация метода (сортировка по возрастанию):
| Исходный массив | ||||||||
| Искомый массив |
Алгоритм сортировки обменом по возрастанию:
For i:=1 to n-1 do
For j:=1 to n-i do if a[j]>a[j+1] then begin
x:=a[j];
a[j]:=a[j+1];
a[j+1]:=x
end;
Сортировка методом простых вставок
Сортировка этим методом заключается в следующем: на i-м шаге считается, что часть массива, содержащая первые i-1 элементов, уже упорядочена, т. е.
A[1] ≤A[2] ≤ … ≤A[i-1] (для сортировки по неубыванию). Далее берётся i-й элемент, и для него подбирается место в отсортированной части массива, такое, что после его вставки упорядоченность не нарушается. Затем выполняется вставка элемента A[i] на найденное место. На каждом шаге отсортированная часть массива увеличивается.
Рассмотрим на примере:
Алгоритм сортировки вставками по возрастанию:
For i:=2 to n do
begin
x:=a[i]; j:=i-1;
While (j>0) and (x<a[j]) do
begin a[j+1]:=a[j]; j:=j-1; end;
a[j+1]:=x;
end;
1. Цифровая сортировка(acmp.ru)
| № | INPUT.TXT | OUTPUT.TXT |
| 3 9 -20 14 | -20 9 14 | |
| 10 12 7 92 5 18 4 32 48 11 74 | 4 5 7 11 12 18 32 48 74 92 |
На планете «Аурон» атмосфера практически отсутствует, поэтому она известна своими перепадами температур в различных точках. Известно, что эти перепады колеблются от -100 до 100 градусов. Нашим специалистам удалось выяснить значения температур в N точках этой планеты. К сожалению, эти значения вычислены с большими погрешностями, поэтому их решили округлить до целых чисел. Хотелось бы наглядно видеть участки с повышенной и пониженной температурой. Вам требуется помочь. Вы должны упорядочить температуры участков по неубыванию.
Входные данные:В первой строке входного файла INPUT.TXT задано натуральное число N - количество участков (N ≤ 106). Во второй строке через пробел записаны целые значения температур этих участков, не превосходящие 100 по абсолютной величине.
Выходные данные: В единственную строку выходного файла OUTPUT.TXT нужно вывести разделенные пробелом значения температур всех известных участков, которые должны следовать друг за другом в порядке неубывания.
2. Сортировка времени (acmp.ru)
Требуется выполнить сортировку временных моментов, заданных в часах, минутах и секундах.
Входные данные
| № | INPUT.TXT | OUTPUT.TXT |
| 4 10 20 30 7 30 00 13 59 59 13 30 30 | 7 30 0 10 20 30 13 30 30 13 59 59 |
Во входном файле INPUT.TXT в первой строке записано число N (1<=N<=100), а в последующих N строках N моментов времени. Каждый момент времени задается 3 целыми числами - часы (от 0 до 23), минуты (от 0 до 59) и секунды (от 0 до 59).
Выходные данные
В выходной файл OUTPUT.TXT выведите моменты времени, упорядоченные в порядке неубывания без ведущих нулей.
3. Населенный пункт
Заданы два одномерных массива. Один содержит К населенных пунктов района, а другой - расстояние от каждого из них до районного центра (расстояние – целые числа < 1000). Определить название населенного пункта, который ближе всего расположен к центру.
| № | INPUT.TXT | OUTPUT.TXT |
| Шашки Рубежевичи Николаевщина 20 29 15 | Николаевщина |
Входные данные: В первой строке входного файла INPUT.TXT записано число К – количество населенных пунктов (1<=К<=20). На следующих К строках располагаются названия населенных пунктов. Последняя строка содержит К чисел, представляющих расстояние от каждого населенного пункта до центра. Все числа разделены пробелом.
Выходные данные: В выходной файла OUTPUT.TXT нужно вывести название ближайшего к центру населенного пункта.
4.Статистика
Вася не любит английский язык, но каждый раз старается получить хотя бы четверку за четверть, чтобы оставаться ударником. В текущей четверти Вася заметил следующую закономерность: по нечетным дням месяца он получал тройки, а по четным – четверки. Так же он помнит, в какие дни он получал эти оценки. Поэтому он выписал на бумажке все эти дни для того, чтобы оценить, сколько у него троек и сколько четверок. Помогите Васе это сделать, расположив четные и нечетные числа в разных строчках. Вася может рассчитывать на оценку 4, если четверок не меньше, чем троек.
Входные данные
В первой строке входного файла INPUT.TXT записано единственное число N – количество элементов целочисленного массива (1<=N<=100). Вторая строка содержит N чисел, представляющих заданный массив. Каждый элемент массива – натуральное число от 1 до 31. Все элементы массива разделены пробелом.
| № | input.txt | output.txt |
| 5 4 16 19 31 2 | 19 31 4 16 2 YES | |
| 8 29 4 7 12 15 17 24 1 | 29 7 15 17 1 4 12 24 NO |
Выходные данные
В первую строку выходного файла OUTPUT.TXT нужно вывести числа, которые соответствуют дням месяцев, в которые Вася получил тройки, а во второй строке соответственно расположить числа месяца, в которые Вася получил четверки. В третьей строке нужно вывести «YES», если Вася может рассчитывать на четверку и «NO» в противном случае. В каждой строчке числа следует выводить в том же порядке, в котором они идут во входных данных. При выводе, числа отделяются пробелом.
5. Сортировка масс
Как известно, Россия является одним из ведущих экспортеров нефти. Разные страны мира, от достаточно больших до сравнительно маленьких, нуждаются в этой нефти как в воздухе. В ее состав в больших количествах входят ароматические углеводороды, которые обуславливают ее высокое качество. Доставка нефти в пункт назначения осуществляется с помощью нефтепровода. Считается, что количество нефти, отправленное в страну назначения, равно количеству полученной нефти. На самом деле это, конечно, не так. Как и многое другое, нефть воруют некоторые несознательные личности. Причем неофициально считается, что больше нефти воруют в нефтепроводах тех стран, куда нефти посылается больше (может быть, несознательные личности считают, что приносят, таким образом, меньше ущерба, кто знает...). Официальное руководство компании «Русская Нефть» решило узнать, правдивый это слух или нет, чтобы усилить (а может просто установить) охрану на тех нефтепроводах, где больше всего воруют нефть.
Для этого им нужно отсортировать нефтепроводы по количеству нефти, которая протекает в направлении какой-то страны за сутки. У компании «Русская Нефть», как и у любой уважающей себя компании, есть несколько штатных программистов, и руководство предложило им решить эту, в сущности, нетрудную задачу. Но программистов поставило в тупик то, что данные о количестве нефти представлены в разных единицах измерения (начиная от граммов и заканчивая тоннами).
| № | input.txt | output.txt |
| 3 2 t 3 p 4 g | 4 g 3 p 2 t | |
| 5 2340000 g 4576 p 2 t 32 t 2000000 g | 2 t 2000000 g 2340000 g 32 t 4576 p |
Поэтому они решили найти человека, который был бы в силах решить эту задачу за них, и обещают взять его на работу в эту перспективную и процветающую компанию. Решите задачу, и, кто знает, может, повезет именно Вам?
Входные данные: В первой строке входного файла input.txt находится целое число N (1<=N<=1000) — количество нефтепроводов. В каждой из следующих N строк находится количество (точнее — масса) нефти, транспортированной по соответствующему нефтепроводу за сутки, по одному в строке. Масса нефти задана целым числом от 1 до 106 с указанием соответствующей единицы измерения. Число и единица измерения разделены ровно одним пробелом. Единица измерения задается одной из трех букв: g (граммы), p (пуды), t (тонны). Напомним, что 1 пуд = 16380 граммов, 1 тонна = 106 граммов.
Выходные данные: В выходной файл output.txt выведите N строк, в которых должны быть записаны массы нефти в порядке неубывания. Каждая строка должна описывать массу нефти в одном из нефтепроводов. Массы должны быть описаны в том же формате, в котором записаны во входном файле. Приоритет равных масс, записанных в разных форматах должен соответствовать порядку, в котором они следуют во входном файле.