Тема №13. Сортировка массивов

Тема №13. Сортировка массивов

Тема имеет исключительно важное значение

Первой серьезной задачей программирования, с которой сталкивается начинающий программист – это задача сортировки массива. Под сортировкой понимается упорядочивание элементов массива по возрастанию (или по убыванию) без создания копии массива (т.е. «на месте»).

Самый простой алгоритм – это линейная сортировка. Рассмотрим рис. 13.1.

Проведем последовательно сравнение первого элемента со всеми последующими, при если при очередном сравнении (например сразу 4 и 2) выяснится, что элементы стоят в «неправильном» порядке – переставим их местами, затем продолжим сравнение

(рис. 13.2). По окончании одного прохода, можно сказать, что в первом элементе массива находится минимальный элемент (Рис. 13.4).

Рис 13.1

Рис 13.2

Рис 13.3

Рис 13.4

Далее применим указанную процедуру к неотсортированному «остатку» массива (рис. 13.5) до тех пор, пока не переставим два последних элемента (рис. 13.6-13.7).

Рис 13.5

Рис 13.6

Рис 13.7

Рис 13.8

Алгоритм линейной сортировки очень прост, но не экономичен, среднее число просмотров и перестановок пропорционально квадрату числа элементов (точнее -N2 /2 ).

- 37 -

Приведем программу сортировки. Обратите внимание, что мы использовали массив в качестве параметра процедуры. Для этого необходимо создать тип Massiv (стр. 34). Часто для экономии памяти массив передают через var-параметр (стр. 32), даже если не предполагается его модифицировать в подпрограмме. Т.е. заголовок процедуры print мог бы выглядеть следующим образом:

procedure print (var m : Massiv); .

Program LinerSort;

Const N = 10; // Число элементов массива

Type Massiv = array [1..N] of integer; // Определение типа Massiv

procedure swap(var x,y: integer); // Перестановка элементов местами

var z : integer;

begin

z:=x; x:=y; y:=z;

end;

procedure print(m : Massiv); // Вывод массива

var i : integer;

begin

for i:=1 to N do write(m[i]:5);

writeln; // Новая строка

end;

// Переменные главной программы

var a : Massiv; i,j : integer;

begin

// Заполнение массива случайными числами в диапазоне от 0 до 99

for i:=1 to N do a[i]:=random(100);

print(a); // Вывод массива

for i:=1 to N-1 do // Внешний цикл до N-1 (обратите внимание!)

for j:=i+1 to N do // Внутренний цикл от i+1 (обратите внимание!) if (a[i]>a[j]) then swap(a[i],a[j]); // Перестановка элементов

print(a); // Вывод отсортированного массива

end.

Задание 13

1. Внимательно прочитать текст. Оформите сортировку массива в виде отдельной процедуры (здесь уже применение var-параметра будет обязательным). (2 балла)

2. Добавьте в процедуру сортировки операторы, которые позволил ли бы узнать сколько раз происходят перестановки в процессе сортировки. Выясните этот вопрос для N=10, 100, 1000.

(3балла) - 38 -

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Сортировка массивов

Из книги автора

Сортировка массивов array_reverseРасстановка элементов массива в обратном порядке.Синтаксис:array array_reverse(array arr [, bool preserve_keys])Функция array_reverse() возвращает массив, элементы которого следуют в обратном порядке относительно массива, переданного в параметре. При этом связи между


Создание массивов

Из книги автора

Создание массивов Массивом называют множество однородных предметов, образующих единое целое. Массивы программы AutoCAD – это совокупность копий одного объекта, расположенных на равном расстоянии друг от друга. Так как массивы связаны со смещением координат, они могут быть


8.1.4. Сравнение массивов

Из книги автора

8.1.4. Сравнение массивов При сравнении массивов возможны неожиданности — будьте осторожны!Для сравнения массивов служит метод экземпляра <=>. Он работает так же, как в других контекстах, то есть возвращает -1 (меньше), 0 (равно) или 1 (больше). Методы == и != опираются на


8.1.22. Чередование массивов

Из книги автора

8.1.22. Чередование массивов Предположим, что есть два массива и надо построить из них третий, который содержит массивы из двух элементов, взятых из соответственных позиций исходных массивов. В последних версиях Ruby модуль Enumerable содержит метод zip:a = [1, 2, 3, 4]b = ["a", "b", "c", "d"]с =


8.1.25. Синхронная сортировка нескольких массивов

Из книги автора

8.1.25. Синхронная сортировка нескольких массивов Предположим, что необходимо отсортировать массив, которому соответствуют «параллельные» массивы, то есть в соответственных позициях находятся логически связанные данные. Не хотелось бы, чтобы в результате сортировки это


УКАЗАТЕЛИ МАССИВОВ

Из книги автора

УКАЗАТЕЛИ МАССИВОВ      Как было сказано в гл. 9, указатели позволяют нам работать с символическими адресами. Поскольку в реализуемых аппаратно командах вычислительной машины интенсивно используются адреса, указатели предоставляют возможность применять адреса


Типы массивов

Из книги автора

Типы массивов Firebird позволяет создавать однородные массивы для большинства типов данных. Использование массива позволяет хранить множество элементов данных в виде дискретных, многомерных элементов в одном столбце. Firebird может выполнять операции над целым массивом,


Определение массивов

Из книги автора

Определение массивов Массив может быть определен как домен (с использованием CREATE DOMAIN) или как столбец в операторе CREATE TABLE или ALTER TABLE. Определение домена или столбца как массива похоже на определение любого другого такого объекта, здесь только добавляется указание


Создание массивов

Из книги автора

Создание массивов Массивом называют множество однородных предметов, образующих единое целое. Массивы программы AutoCAD – это совокупность копий одного объекта, расположенных на равном расстоянии друг от друга. Так как массивы связаны со смещением координат, они могут быть


Компьютерра №33 (605) Тема номера: Выставки ТЕМА НОМЕРА SIGGRAPH 2005

Из книги автора

Компьютерра №33 (605) Тема номера: Выставки ТЕМА НОМЕРА SIGGRAPH 2005 В начале августа в Лос-Анджелесе прошла выставка SIGGRAPH 2005. Полное название этого мероприятия звучит следующим образом: 32-я Международная конференция по компьютерной графике и интерактивным технологиям


Ревизия массивов

Из книги автора

Ревизия массивов Набросок библиотечного класса ARRAY дан в предыдущей лекции. Теперь мы в состоянии дать ему подходящее определение. Фундаментальное понятие массива требует задания предусловий, постусловий и инварианта.Приведем улучшенный, но все еще схематичный


ТЕМА НОМЕРА: Как родилась эта тема

Из книги автора

ТЕМА НОМЕРА: Как родилась эта тема Автор: Владимир ГуриевОбычно мы стараемся придумать на первое апреля что-нибудь веселое, но последние несколько лет редакции и без первого апреля живется все лучше и веселее, так что настроения шутить у нас не было, и в тематическом