Сортировка массивов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ераций А, равное 0. Для сортировки организуем два цикла for. Внешний цикл с параметром I, указывающим позицию первого элемента в неотсортированной части массива, и внутренний цикл с параметром I, указывающим позицию очередного, сравниваемого с первым, элемента неотсортированной части массива.
Если условие М[I] < М[J] выполняется, т. е. в неотсортированной части массива найден элемент, больший, чем первый, то обменять местами эти элементы. Обмен осуществляется следующим образом: сначала значение М[1] запоминается в переменной N, затем значение элемента массива из J-й позиции записывается в I-ю позицию, а после этого в J-ю позицию массива записывается значение переменной N. Для наблюдения изменений состояния массива после каждой перестановки зададим цикл вывода значений всех элементов.
Запустите интегрированную среду программирования. Введите текст программы Sort_Lin и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того как компиляция выполнится успешно, запустите программу на исполнение, наблюдая в пошаговом режиме текущие значения переменных: I, J, N, M[I], M[J], а также просматривая на экране пользователя измененный за один проход внутреннего цикла массив. По последнему значению А определяем, что для данного массива сортировка по невозрастанию пузырьковым методом выполняется за 190 итераций.
1.4 Сортировка методом пузырька
Один из самых популярных методов сортировки - "пузырьковый" метод основан на том, что в процессе исполнения алгоритма более "легкие" элементы массива постепенно "всплывают". Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по убыванию состоит в последовательных просмотрах снизу вверх (от начала к концу) массива М. Если соседние элементы таковы, что выполняется условие, согласно которому элемент справа больше элемента слева, то выполняется обмен значениями этих элементов.
Запустите интегрированную среду программирования. Введите текст программы Sort_Puz и запишите файл на диск под соответствующим именем, а затем отмасштабируйте его. После того как компиляция выполнится успешно, запустите программу на исполнение, наблюдая в пошаговом режиме текущие значения переменных: I, J, N, M[I], M[J], всего массива М, а по окончании цикла J просматривая измененный за один проход массив. Как видно по результатам наблюдения, оператором повтора for с параметром J выполняется циклический просмотр элементов массива от последнего до второго, и при этом элементы, большие, чем соседи слева, смещаются при обмене к началу массива, а меньшие - вправо - всплывают в конец массива. Каждый просмотр фиксируется счетчиком просмотров - увеличением на единицу значения переменной А. После каждого просмотра-сравнения элементов массива просматриваемый участок массива уменьшается на один элемент, так как из рассмотрения исключается самый левый - самый большой элемент. Такое уменьшение просматриваемого участка выполняется внешним циклом for с параметром I.
По последнему значению А определяем, что для данного массива сортировка по невозрастанию пузырьковым методом выполняется за 170 итераций.
Метод быстрой сортировки с разделением
Оба выше рассмотренных метода достаточно просты и наглядны, но не очень эффективны. Значительно быстрее работает алгоритм сортировки К.Хоора, который называют сортировкой с разделением или "быстрой сортировкой". В основу алгоритма положен метод последовательного дробления массива на части. Рассмотрим пример программы, реализующей этот метод.
Запустите интегрированную среду программирования. Введите текст программы Quick_sort и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того как компиляция выполнится успешно, нажатием клавиши Р7 запустите программу на исполнение в пошаговом режиме с заходом в процедуру QuickS и пронаблюдайте изменения текущих значений переменных I, J, М[I], М[J], First, X, Last. В момент вызова процедуры просматривайте экран пользователя с текущим состоянием сортируемого массива или установите в окне просмотра имя массива М для наблюдения за изменением состояния массива в процессе сортировки.
После первого вызова процедуры QuickS в исходном массиве:
11 12 3 19 1 5 17 10 18 3 19 17 9 12 20 20 19 2 5
будет определена его середина (10-й элемент) и переменной X присвоено значение М[10], т. е. 18. После этого массив делится на две части:
11 12 3 19 15 17 10 18 и 3 19 17 9 12 20 20 9 2 5
Далее выполняется обмен элементами по следующему правилу: При просмотре левой части массива слева направо выполняется поиск такого элемента массива, что М[I]>Х, затем при просмотре правой части справа налево отыскивается такой элемент, что М[I]Х, не будут обменены с элементами, расположенными справа от середины и удовлетворяющими условию М[I]<Х. В результате этого получим массив из двух частей следующего вида:
11 12 3 19 1 5 17 10 18 3 19 17 9 12 20 20 19 2 5 Число итераций =1
20 12 3 19 1 5 17 10 18 3 19 17 9 12 20 11 9 2 5 Число итераций =2
20 20 3 19 1 5 17 10 18 3 19 17 9 12 12 11 9 2 5 Число итераций =3
20 20 19 19 1 5 17 10 18 3 3 17 9 12 12 11 9 2 5 Число итераций =4
20 20 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций =5
Далее рекурсивно левая часть в свою очередь дробится на две части, и вызывается процедура для сортировки левой части (с 1-го по 6-й элемент)
20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций =7
20 19 19 19 18 5 17 10 1