Выбираем в исходном массиве некоторый барьерный элемент x=a[k]. (В качестве барьерного элемента принято в большинстве случаев брать средний элемент a[(n+1) div 2)], n-размер массива). На втором шаге переставляем элементы массива таким образом, чтобы слева от х оказались элементы массива меньшие или равные х, а справа – элементы массива, большие х. Далее применяем предыдущие действия для каждой из полученных частей массива и т.д., пока не останутся подмассивы, состоящие из одного элемента, т.е. пока не будет отсортирован весь массив.
Программа, реализующая метод быстрой сортировки, включает в свое тело вызов следующей процедуры:
………….……………………………….
procedure sor (m,l:integer);
var i, j, x, t: integer;
Begin
i:=m; j:=l;
{выбор барьерного элемента}
x:=a[(m+l) div 2];
{поиск и замена местами элементов не соответствующих данному условию}
Repeat
while a[i]<x do i:=i+1;
while a[j]>x do j:=j-1;
if i<=j then
begin t:=a[i];
a[i]:=a[j];
a[j]:=t;
i:=i+1; j:=j-1;
end;
until i>j;
{рекурсивный вызов самой процедуры}
if m<j then sor(m,j);
if i<l then sor(i,l);
end;
…………………………………………………….
В этой процедуре формальные параметры m и l указывают номера первого и последнего элемента сортировки массива. При первом вызове может быть m=1, а l=n (здесь n – размер массива). Цикл repeat … until для переменных i и j используется для перемены мест элементов, не соответствующих искомому порядку. Цикл while для переменной i используется для нахождения элемента, большего «барьерного» в левой половине массива. Цикл while для переменной j используется для нахождения элемента меньшего «барьерного» и находящегося в правой половине массива. Условия m<j и i<l предназначены для очередного вызова процедуры, до тех пор, пока не останется массив, состоящий из одного элемента.
Рассмотрим принцип работы «быстрой сортировки» на примере массива
При вызове процедуры из основной программы с значениями m=1 и l=7 переменная i принимает значение 1, а j=7. Барьерным элементом выбирается четвертый элемент (x=a[(1+7) div 2]=a[4]=4). Цикл while для переменной i заканчивается при i=1, а цикл while для переменной j при значении j=6. После того, как поменяем местами первый и шестой элемент, получаем массив
и значения i=2 и j=5. Так как условие выхода из цикла не выполняется, тело цикла repeat … until выполняется еще раз. Цикл while для переменной i заканчивается при i=2, а цикл while для переменной j при значении j=4. После того, как поменяем местами второй и четвертый элемент, получаем массив
и значения i=3 и j=3. Так как условие выхода из цикла не выполняется, тело цикла repeat … until выполняется еще раз. Цикл while для переменной i заканчивается при i=4, а цикл while для переменной j при значении j=3. Так как i<j, элементы a[3] и a[4] остаются на месте и выполняется условие выхода из цикла repeat … until. После проверки условий m<j и i<l процедура sor вызывается с параметрами m=1, j=3 и i=4, l=7.
Для значений m=1, j=3 выполнение процедуры sor будет следующим. Барьерным элементом выбирается второй элемент (x=a[(1+3) div 2]=a[2]=4). Цикл while для переменной заканчивается при значении i=2, а цикл while для переменной j при значении j=3. После того, как поменяем местами второй и третий элемент, получаем массив
и значения i=3 и j=2. Условие выхода из цикла repeat … until выполняется. Условие i<l не выполняется, а выполнение условия m<j вызывает процедуру sor для значений m=1, j=2. Барьерным элементом выбирается первый элемент (x=a[(1+2) div 2]=a[1]=1). Цикл while для переменной i заканчивается при i=1, а цикл while для переменной j при значении j=1. Меняя местами первый элемент с первым элементом, мы получим
и значения i=2 и j=0. Условия m<j (1<0) и i<l (2<2) не выполняются. Рекурсивного вызова процедуры не происходит.
При значениях i=4 и l=7 процедура sor выполняется по следующему принципу. Барьерным элементом выбирается пятый элемент (x=a[(4+7) div 2]=a[5]=7). Цикл while для переменной i заканчивается при i=5, а цикл while для переменной j при значении j=7. После того, как поменяем местами пятый и седьмой элемент, получаем массив
и значения i=6 и j=6. Условие выхода из цикла repeat … until не выполняется, а циклы while заканчиваются при значениях i=6 и j=7. Так как не выполняется условие i<=j и выполняется условие i>j, из цикла repeat … until мы выходим без изменений массива.
Условия m<j (4<5), i<l (6<7) вызывают процедуру sor еще раз для значений m=4 и j=5, i=6 и l=7.
При значениях m=4 и j=5 выполнение процедуры sor протекает в следующем порядке.
Барьерным элементом выбирается четвертый элемент (x=a[(4+5) div 2]=a[4]=6). Цикл while для переменной i заканчивается при i=4, а цикл while для переменной j при значении j=5. После того, как поменяем местами четвертый и пятый элемент, получаем массив
и значения i=5 и j=4. Условие выхода из цикла repeat … until выполняется, и проверяются условия m<j (4<4), i<l (5<5). Не-выполнение этих условий останавливает рекурсивный вызов процедуры sor.
При значениях i=6 и l=7 выполнение процедура sor протекает в следующем порядке.
Барьерным элементом выбирается шестой элемент (x=a[(6+7) div 2]=a[6]=8). Цикл while для переменной i заканчивается при i=6, а цикл while для переменной j при значении j=7. После того, как поменяем местами шестой и седьмой элемент, получаем массив
и значения i=7 и j=6. Условие выхода из цикла repeat … until выполняется, и проверяются выполнение условий m<j (6<6), i<l (7<7). Так как они не выполняются, рекурсивный вызов процедуры sor прекращается.
Конечным результатом быстрой сортировки мы получим отсортированный массив
Примеры решения задач на сортировку массивов
Пример 1. Дан одномерный массив. Каждый элемент содержит следующую информацию: фамилия и рост студента. Упорядочить студентов по возрастанию роста.
Входные данные – одномерный массив а, каждый элемент которого в качестве значения имеет пару данных различного типа. В языке Turbo Pascal такие элементы удобно описать с помощью типа запись, с двумя полями: типа string для фамилии и типа integer для роста. В программе этот тип назван student.
Выходные данные – отсортированный массив, который размещается в памяти в тех же ячейках, что и исходный, поэтому в программе обозначается тем же именем а.
Сортировка производится методом пузырька. При этом два соседних элемента упорядочиваются в порядке возрастания значений в поле rost. Для того, чтобы в случае необходимости поменять местами два элемента, нужна промежуточная переменная того же типа, что и элементы массива. Этой переменной в программе дано имя b. Так как при выводе на экран в списке вывода процедуры writeln могут быть лишь величины стандартного типа, а тип запись не является стандартным, приходится указывать каждое поле элемента массива по отдельности.
program m1;
const n=10;
type student=record
fam:string;
rost:integer;
end;
var a:array [1..n] of student;
b:student;
i,k:integer;
begin
for i:=1 to n do
begin write('Вводите фамилию');readln(a[i].fam);
write('вводите рост');readln(a[i].rost);
end;
{сортировка студентов по росту методом пузырька }
for k:=n downto 2 do
for i:=1 to k-1 do
if a[i].rost>a[i+1].rost then
begin
b:=a[i];
a[i]:=a[i+1];
a[i+1]:=b;
end;
for i:=1 to n do
writeln(a[i].fam,' ',a[i].rost);
end.
Пример 2. Дан массив A – массив целых чисел. Сформировать новый массив B из элементов массива A, кратных 5-ти, и отсортировать его по возрастанию.
Входные данные – одномерный массив а, элементами которого являются целые числа.
Выходные данные – отсортированный массив b, состоящий из тех элементов исходного массива a, которые кратны 5-ти.
Сортировка производится методом выбора. При этом элементы массива упорядочиваются в порядке возрастания. Для того, чтобы поменять местами два элемента, используются две переменные: min для сохранения самого элемента и imin для сохранения позиции этого элемента в массиве. Отсортированный массив выводится на экран в виде строки.
program m1;
const n=6;
type mas=array[1..n] of integer;
var a,b:mas;
s,min,imin,j,i:integer;
begin
writeln ('введите элементы массива');
for i:=1 to n do read(a[i]);
j:=1;
{формирование нового массива из элементов исходного массива, кратных 5-ти}
for i:=1 to n do
if a[i]mod 5=0 then begin b[j]:=a[i];j:=j+1; end;
j:=j-1;
{сортировка полученного массива методом выбора}
for s:=1 to j-1 do
begin
min:=b[s];
imin:=s;
for i:=s+1 to j do
if b[i]<min then
begin
min:=b[i];
imin:=i;
end;
b[imin]:=b[s];
b[s]:=min
end;
for i:=1 to j do write(b[i],' ');
end.
Пример 3. Дан одномерный массив размера n, состоящий из целых чисел. Упорядочить элементы этого массива так, чтобы расположить сначала четные, а потом нечетные элементы в порядке возрастания.
Входные данные – одномерный массив а, элементами которого являются целые числа. Выходные данные – отсортированный массив, в начале которого находятся отсортированные четные элементы, а затем отсортированные нечетные элементы. Элементы массива размещаются в памяти в тех же ячейках, что и исходный, поэтому в программе обозначаются тем же именем а.
Сортировка производится методом быстрой сортировки. Перед сортировкой четные элементы собираются в левую часть, а не четные элементы в правую часть массива. Для этого используется цикл repeat…until. А циклы while для переменных i и j используется для нахождения несоответствующих заданному условию четных и нечетных элементов соответственно. При сортировке элементы упорядочиваются по возрастанию. Отсортированный массив выводится на экран в одну строку.
program m1;
const n=6;
type mas=array[1..n] of integer;
var a:mas;
c,i,j,t:integer;
procedure sor(m,l:integer);
var i,j,x,t:integer;
begin
i:=m;j:=l;
x:=a[(m+l) div 2];
repeat
while a[i]<x do i:=i+1;
while a[j]>x do j:=j-1;
if i<=j then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
i:=i+1;j:=j-1;
end;
until i>j;
if m<j then sor(m,j);
if i<l then sor(i,l);
end;
begin write('введите элементы массива');
for i:=1 to n do read(a[i]);
i:=1;j:=n;
{сбор четных элементов в правую часть массива, а нечетных в левую }
repeat
while a[i] mod 2=0 do i:=i+1;
while a[j] mod 2=1 do j:=j-1;
if i<=j then begin
c:=a[i];
a[i]:=a[j];
a[j]:=c;
i:=i+1;
j:=j-1;
end;
writeln('i=',i,' j=',j);
until i>j;
{сортировка элементов}
sor(1,j);
sor(i,n);
for i:=1 to n do write(a[i],' ');
end.
Пример 4. Дан массив А – массив чисел, записанных в 8-ой системе счисления. Отсортировать его в порядке убывания. Результат выдать в 8-ичной и 10-ичной системе счисления.
Входные данные – одномерный массив а, каждый элемент которого в качестве значения имеет целое число, заданное в 8-ичной системе счисления. Так как на языке Turbo Pascal для чисел 8-ичной системе отдельного типа не предусмотрено, поэтому числам присваиваем тип integer, а при вводе чисел вводим числа 8-ичной системы счисления.
Выходные данные – два отсортированных массива, один из которых размещается в памяти в тех же ячейках, что и исходный, поэтому в программе обозначается тем же именем а и состоит из чисел в 8-ичной системе счисления. Элементами второго массива, который в программе обозначается именем b, являются те же элементы массива а, только переведенные в 10-ичную систему счисления.
Сортировка производится методом вставки. При этом элементы массива упорядочиваются в порядке возрастания. При сортировке цикл while для переменной j используется для нахождения позиции элемента, который не соответствует заданному условию.
После того как массив a отсортирован, элементы массива переводятся в 10-ичную систему счисления с помощью цикла while по переменной k и записываются в массив b.
Массивы а и b выводятся в разные строки.
program m1;
const n=6;
type mas=array [1..n] of integer;
var a,b:mas;
k,i,j,p,c,t,f:integer;
begin writeln('введите элементы массива в 8-ичной системе счисления');
for i:=1 to n do read(a[i]);
{сортировка элементов массива методом вставки}
for i:=2 to n do
begin f:=a[i];
j:=1;
while (f>a[j]) do j:=j+1;
for k:=i-1 downto j do
a[k+1]:=a[k];
a[j]:=f;
end;
j:=1;
for i:=1 to n do
begin k:=a[i];t:=1;c:=0;
while abs(k)>=1 do begin
p:=k mod 10;
c:=c+p*t;
k:=k div 10;
t:=t*8;
end;
b[j]:=c; j:=j+1;
end;
for i:=1 to n do write(a[i],' '); writeln;
for i:=1 to n do write(b[i],' ');
end.
Пример 5. Дан одномерный массив, состоящий из слов. Отсортировать по возрастанию длины те элементы, в составе которых есть в знак "?".
Входные данные – одномерный массив а, каждый элемент которого строка состоящий из набора символов. Выходные данные – отсортированный массив, который размещается в памяти в тех же ячейках, что и исходный, поэтому в программе обозначается тем же именем а. Перед тем как начать сортировку массива, находим первую строку, в которой имеется знак "?". Если такого элемента в массиве не имеется, то на экран выводится сообщение об этом и выводится сам массив, а если есть такой элемент, начинается сортировка тех элементов массива, которые соответствуют данному условию. Сортировка производится методом выбора. При этом элементы упорядочиваются в порядке возрастания. Для того, чтобы в случае необходимости поменять местами два элемента, используются промежуточные величины: amin – переменная для временного размещения строки, min – для временного хранения длины слова, imin – для хранения позиции элемента в массиве. Элементы массива выводятся на экран в виде столбца.
program m1;
const n=5;
type mas=array [1..n] of string;
var a:mas; b:boolean;
k,i,s,t,imin,min:integer;
c,amin:string;
begin writeln('вводите элементы массива');
for i:=1 to n do readln(a[i]); b:=false;
i:=1;
while (i<=n) and not(b) do begin
c:=a[i];
for k:=1 to length(c) do
if c[k]='?' then b:=true;
i:=i+1;
end;
if not(b) then writeln('такого элемента в этом массиве нет') else begin
