Изучение нового материала.

3. Изучение нового материала.

- Упорядочивание массивов (сортировка)

Сортировка - один из наиболее распространенных процессов обработки данных. Сортировкой числового массива называют расположение его элементов в возрастающем или убывающем по величине порядке. Сортировка символьного массива заключается в расположении элементов, например, по алфавиту или по длине строк. Сортировка массивов включена в качестве стандартной операции во многие системы прикладного обеспечения (MS Word, MS Excel и др). Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Существует достаточно много методов (алгоритмов) сортировки массивов. Мы рассмотрим два из них: метод прямого выбора и метод обмена (метод «пузырька»)

Постановка задачи сортировки в общем виде предполагает, что существуют только два типа действий с данными сортируемого типа:

· сравнение двух элементов (x < y) ;

· пересылка элемента (x := y).

Основное действие сортировки выбором - поиск наименьшего элемента в просматриваемой части массива, и перестановка с первым элементом этой части.

Все намного проще, чем тебе кажется СМОТРИ ВИДЕО

Алгоритм сортировки выбором осуществляет n-1 линейный просмотр массива A. В результате каждого просмотра наименьший элемент просмотренной части массива меняется местами с первым элементом этой части. Первый просмотр осуществляется во всем массиве, а каждый следующий – в диапазоне, на единицу меньшем. Таким образом, левая часть массива постепенно становится упорядоченной

Сортировка массивов выбором:

Program SelectSort;

Const

n = 20;{допустим числовой массив из 20 элементов}

Var

a : array[1..n] of Data;

i, j, MinInd : Integer;

b : Data;

Begin

{ поиск наименьшего элемента в просматриваемой части массива }

For i := 1 to n - 1 do begin

MinInd := i;

For j := i + 1 to n do

If a[j] < a[MinInd]

then MinInd := j;

b := a[MinInd];

a[MinInd] := a[i];

a[i] := b

end;

End.

- сортировку обменом (так называемая «пузырьковая» сортировка)

Основное действие сортировки обменами - сравнение двух элементов и, если результат сравнения отрицателен, перестановка их местами.

Алгоритм сортировки обменами осуществляет n-1 линейный просмотр массива А. В результате каждого просмотра наибольший элемент просмотренной части массива «всплывает» на последнее место в результате сравнения и перестановки, если нужно, двух соседних элементов. Первый просмотр осуществляется во всем массиве, а каждый следующий просмотр – в диапазоне, на единицу меньшем. Таким образом, правая часть массива постепенно становится упорядоченной.

СМОТРИ ВИДЕО (идея: выполняется обмен местами пар элементов с выбором макс и мин до конца массива, при повторной проверке и сортировке пар элементов мин и макс упорядочиваются, если массив большой, выполняется следующая проверка массива по парам элементов. Недостаток метода пузырька – медленно)

ВИДЕО СОРТИРОВКА ВСТАВКАМИ

⇐ Предыдущая 123 Следующая ⇒