Вернутся на главную

Сортировка


Сортировка на нашем сайте

Статьи
Статьи для студентов
Статьи для учеников
Научные статьи
Образовательные статьи Статьи для учителей
Домашние задания
Домашние задания для школьников
Домашние задания с решениями Задания с решениями
Задания для студентов
Методички
Методические пособия
Методички для студентов
Методички для преподавателей
Новые учебные работы
Учебные работы
Доклады
Студенческие доклады
Научные доклады
Школьные доклады
Рефераты
Рефератывные работы
Школьные рефераты
Доклады учителей
Учебные документы
Разные образовательные материалы Разные научные материалы
Разные познавательные материалы
Шпаргалки
Шпаргалки для студентов
Шпаргалки для учеников
Другое

Пусть имеется ряд чисел: 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

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] >= …





Название статьи Сортировка