Главная » Pascal, Основы » Массивы (часть 2)
Фев
27

Массивы (часть 2)

Массивы (часть 2)

Основные методы сортировки массивов

  1. Вступление
  2. Метод пузыря
  3. Модифицированный метод пузыря
  4. Метод прямого выбора
  5. Метод прямой вставки

Вступление

Все существующие методы сортировки можно поделить на обменные сортировки — исполняется обмен между двумя чаще соседними элементами массивов, если элементы расположены неупорядоченно;
Метод прямого выбора в массиве выбирается элемент с определенными свойствами(мин., макс.), а потом выбранный элемент ставится на свое место;
Метод прямой вставки — последовательно выбирается элемент с массивом и после определения его места в упорядоченном массиве этот элемент непосредственно вставляется на свое место.
Метод пузыря





Наиболее известным методом обменной сортировки — метод пузыря, в нем при последовательном проходе по массиву сравниваются два соседних элемента, и при неправильном расположении исполняется взаимообмен. процесс повторяется n-1 раз, где n — размер массива.

[sourcecode language=»pascal»]
Program Bubble;
const= 20;
var
mas: array[1..n] of integer;
Res,i,j: integer;
begin
for i:= 1 to n do
for j:= 1 to n -1 do
if mas[j] > mas[j+1];
then
begin
Res:= mas[j];
mas[y]:= mas[j+1];
mas[j+1]:= Res;
end;
end.
[/sourcecode]
Модифицированный метод пузыря

Будем считать флажок уровнем false, если перестановки не произошло true, в противном случае. Кроме того после каждого прохождения по массиву наиболее(наименее) всплывает наверх, тоесть занимает свою позицию.
Вводим переменную «k», которая будет фиксировать правую границу упорядоченности.
[sourcecode language=»pascal»]
Program Bubble2;
const n= 20;
var
mass: array[1..n] of integer;
i,j,k: integer;
Res: integer;
Flag: boolean;
begin
k:= 1;
repeat
Flag = false;
for i:= n-k do
begin
if mas[i] > mas[i+1]
then
begin
Res:= mas[i];
mas[i]:= mas[i+1];
mas[i+1]:= Res;
Flag:= True;
end;
k:= k+1;
Until
Flag= false;
end;
end.
[/sourcecode]
Метод прямого выбора

Выбирается минимальный элемент массива, а потом выполняется его обмен с первым элементом таблицы. Первый элемент считается упорядоченным и процесс повторяется, начиная со второго элемента. Заканчивается он тогда, когда неупорядоченный подмассив становится длиной в один элемент.
[sourcecode language=»pascal»]
Program Example;
const n= 20;
var
mas:= array[1..10] of integer;
i,j,min,n_min: integer;
begin
for i:= 1 to n01 do
begin
min:= mas[1];
n_min:= i;
for j:= 1 to n do
if mas[j] < min
then
begin
min:= mas[j];
n_min:= j;
end;
mas[n_min]:= mas;
mas[i]:= min;
end;
end.
[/sourcecode]
Метод прямой вставки

Обеспечивает вставку каждого элемента и неупорядоченного массива на свое место, в уже упорядоченный массив.
На начале сортировки массив разбивается на два подмассива: один упорядоченный, один неупорядоченный.
В неизвестном массиве только один элемент можно считать упорядоченным, поэтому левая часть будет состоять с одного элемента. Потом по очереди берутся элементы с правой части, и для них находится место вставки в первую часть, так чтобы упорядоченность не нарушалась. После этого в массиве необходимо сделать сдвиг элементов, чтобы освободить место, на которое и будет вставляться очередной элемент. Элемент как будто плывет влево от своего начального места нахождения. Этот процесс прекращается, если найденный элемент не больше за данный или достигнуто начало массива.
[sourcecode language=»pascal»]
Program Insert;
const n= 20;
var
mas:= array[1..n] of integer;
i,j,rar: integer;
begin
for i:= 2 to n do
begin
while(j>1) and (mas[j] < mas[j-1]) do
begin
rar:= mas[j];
mas[j]:= mas[j,1];
mas[j-1]:= rar;
j:= j-1;
end;
end;
end.
[/sourcecode]

____
Строительство и ремонт загородных домов в Подмосковье



Понравилась статья? Сделай приятно ее автору, поделись с друзьями:


Хотите получать обновления данного блога на EMail?

Введите адрес Почтового Ящика:




Подтвердите подписку в письме пришедшем на Почту, после чего начнете получить рассылку.