Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сортировка
Пусть имеется ряд чисел: 8 2 5 4. Под сортировкой понимают их упорядочивание по возрастанию (2 4 5 8) или убыванию (8 5 4 2). Сортировать можно и символы (по алфавиту или коду ASCII) и строки (как слова в словаре). Сортировка - очень распространенная вещь в самых разных программах, в частности - в системах управления базами данных.
Задача: Задан массив из 100 произвольных положительных чисел. Отсортировать его по возрастанию. Если мы не можем сходу запрограммировать задачу, нужно подробно представить себе, в каком порядке мы решали бы ее вручную, без компьютера. Как бы мы сами сортировали 100 чисел? Мы бы запаслись пустым листом бумаги из 100 клеток. Затем нашли бы в исходном массиве максимальное число и записали его в самую правую клетку, а в исходном массиве на его месте записали бы число, меньшее самого маленького в массиве (в нашем случае подойдет 0). Затем нашли бы в изменившемся исходном массиве новое максимальное число и записали его на второе справа место. И так далее. Вот программа для 10 чисел: CONST N = 10; TYPE vector = array [1..N] of Word; CONST massiv_ishodn: vector =(3, 8, 4, 7, 20, 2, 30, 5, 6, 9); {Это исходный массив} VAR massiv_rezult: vector; {Это наш пустой лист бумаги} i: Word; FUNCTION maximum (m: vector; N: Word; var Nomer_max: Word): Word; {Это вспомогательная функция для поиска максимума в массиве} VAR i, max: Word; BEGIN max: =m[1]; Nomer_max: =1; {Это порядковый номер максимального элемента } for i: =2 to N do if max< m[i] then begin max: =m[i]; Nomer_max: =i end; maximum: =max END; PROCEDURE sortirovka (mass_ish: vector; N: Word; var mass_rez: vector); {Основная процедура сортировки} VAR i, Nom_max: Word; BEGIN for i: =1 to N do begin mass_rez[N+1-i]: =maximum(mass_ish, N, Nom_max); mass_ish[Nom_max]: =0 end {for}; END; BEGIN sortirovka (massiv_ishodn, N, massiv_rezult); for i: =1 to N do Write (massiv_rezult[i], ' '); {Распечатываем отсортированный массив} END. Функция maximum, кроме того, что сама имеет значение максимального элемента массива, выдает еще порядковый номер максимального элемента - Nomer_max. Это называется побочным эффектом функции.
Методов сортировки много. Приведенный метод - самый примитивный. Мало того, что нам пришлось расходовать память на второй массив, для выполнения сортировки массива из 100 элементов понадобилось бы около 100*100=10000 операций сравнения элементов массива между собой. Существуют методы гораздо более эффективные. Приведу один из них - метод пузырька. Представьте себе тонкую вертикальную трубку с водой. Запустим снизу пузырек воздуха. Он поднимется до самого верха. Затем пустим еще один. Он поднимется наверх и остановится сразу же под первым. Затем запустим третий и так далее все сто пузырьков. А теперь представим, что это не трубка, а наш исходный массив, а вместо пузырьков поднимаются максимальные элементы. Вот алгоритм: Сравним первый элемент массива со вторым, и если второй больше, то ничего не делаем, а если первый больше, то меняем местами первый и второй элементы. В этом вся соль метода. Затем повторяем это со вторым и третьим элементами. Если третий больше, то ничего не делаем, а если второй больше, то меняем местами второй и третий элементы. Затем повторяем все это с третьим и четвертым элементами и так далее. Таким образом, максимальный элемент, как пузырек, поднимется у нас до самого верха. Теперь, когда мы знаем, что элемент номер 100 у нас самый большой, нам предстоит решить задачу сортировки для массива из 99 элементов. Запускаем второй пузырек и так далее. Метод пузырька не требует второго массива, да и сравнений здесь в два раза меньше. Вот программа: CONST N = 10; TYPE vector = array [1..N] of Word; CONST massiv: vector =(3, 8, 4, 7, 20, 2, 30, 5, 6, 9); VAR i: Word; PROCEDURE puziryok (var mass: vector; Razmer: Word); VAR i, m, c: Word; BEGIN for m: =Razmer downto 2 do begin {Всего пузырьков – 9} for i: =1 to m-1 do begin {i увеличивается – пузырек ползет вверх} if mass[i]> mass[i+1] then begin {Стоит ли обмениваться значениями} c: =mass[i]; {Три оператора для обмена значений двух элементов с помощью} mass[i]: = mass[i+1]; {транзитного элемента c} mass[i+1]: =c end {if} end {for}; end {for}; END; BEGIN puziryok (massiv, N); for i: =1 to N do Write (massiv[i], ' '); {Распечатываем отсортированный массив} END. Задание 125: Отсортируйте по убыванию двумерный массив. Я имею в виду вот что: a[1, 1] > = a[1, 2] > = … > = a[1, N] > = > = a[2, 1] > = a[2, 2] > = …> = a[2, N] > = > = a[3, 1] > = a[3, 2] > = …
|