Задача: Существует массив. Отсортировать его по возрастанию.
Эта, на первый взгляд простая задача под силу далеко не всем, даже не совсем новичкам. Дело в том, что если вы не знакомы с существующим алгоритмом для решения этой задачи, то определенно вам понадобиться значительно время, чтобы сообразить, как же ее решать. Алгоритм (надо отметить, что он не один) на самом деле очень простой и понятный, но, как я уже сказал, его нужно знать. И рассказать о нем в рассылке надо было в обязательном порядке, что я сегодня и делаю.
Итак, будем сортировать массив, то есть переставим в нем элементы так, чтобы они стояли по возрастанию. Используем известный (возможно, пока не вам) - алгоритм "Пузырька".
Определимся, что нам потребуется. Естественно, сам массив - один и только один, дополнительных массивов никаких не будет, только простые переменные. Заведем массив, скажем, на 30 элементов. Заполнять его будем, конечно, не с клавиатруры (вводить 30 элементов вручную довольно бесполезное занятие), а выполним это с помощью известной нам функции Random. Что дальше? А дальше и начнем нашу сортировку.
Для начала немного подготовим себя и попробуем реализовать операцию перестановки двух элементов массива местами. Это довольно просто и выполняется двумя способами:
1. С помощью 3-ей переменной:
var
A: Array[1..10] of Byte;
B: Byte;
begin
.....
{ Перестановка 1-го и 2-го элементов }
B := A[1];
A[1] := A[2];
A[2] := B;
{ Вот и поменяли местами }
.....
end.
2. С помощью арифметических действий:
var
A: Array[1..10] of Byte;
begin
.....
{ Перестановка 1-го и 2-го элементов }
A[1] := A[1] + A[2];
A[2] := A[1] - A[2];
A[1] := A[1] - A[2];
{ Вот и поменяли местами }
.....
end.
Вам решать, какой способ лучше. Лично я предпочитаю второй, так как он избавляет от использования лишних переменных. Его и советую использовать.
Итак, разобрались на примерах, как переставить местами две переменные. Теперь двигаемся дальше и начнем реализовывать сам алгоритм. При этом я, безусловно, могу привести исходный текст в рассылке, но это будет, на мой взгляд, несколько преждевременно. Лучше я постараюсь подвести вас к самостоятельной реализации этого алгоритма - это позволит гораздо лучше понять его работу, да и позволит попрактиковаться. Конечный вариант вы, как всегда, можете посмотреть на сайте рассылки в разделе "Уроки для начинающих программистов >> Исходные тексты".
Итак, начнем.
Сортировка массива по возрастанию (или по убыванию - без разницы) методом пузырька осуществляется по следующему принципу, который разделим условно на два этапа (следите за ходом моих мыслей):
Первое:
Необходимо сделать цикл, на единицу меньше, чем размер массива.
В этом цикле организовать еще один, такой же.
Организовав такую структуру, вы получите два вложенных цикла, которые пробегут по массиву след. количество раз (n - размер массива):
(n-1) * (n-1)
Второе:
Во втором, внутреннем цикле необходимо выполнить проверку:
1. Если текущий элемент больше, чем следующий, то переставить их местами.
Все :))
Теперь подробнее. Во-первых, если вы будете делать проверку на больше, то сортировка будет производиться по возрастанию. Если на меньше, то по убыванию. Во-вторых, в первом этапе мы создаем два вложенных цикла, диапазоном на единицу меньше, чем размер массива. Для чего? Это налицо во втором этапе нашего алгоритма. Внутри цикла мы сравниваем текущий элемент со следующим. Фактически, выходит такая проверка (j - индекс цикла): If A[j] > A[j+1] ... Как видите, если у нас массив до 10-ти, и J будет идти до 10-ти, то в последней итерации получится: If A[10] > A[11] ..., что будет ошибкой.
Да... Программа получается очень простой и маленькой, но говорить о ней можно много. Думаю, на этом хватит - вы без труда сами составите алгоритм "Пузырька". Конечный работоспособный вариант сморите на http://prog.agava.ru.
