close

Вход

Забыли?

вход по аккаунту

?

Сортировка элементов одномерного массива

код для вставкиСкачать
Для работы с одномерным массивом.
Тема
: «Сортировка элементов одномерного массива» Автор: Андрюшина А.В.
Школа №616
г. Зеленоград
2009 г.
Ряд однотипных данных, имеющих имя, порядковый номер и численное значение называются массивами.
-
5 14 7 10 32 9 -
45 34 16
А
Понятие массива.
1 2 3 4 5 6 7 8 9
Пример: Сформировать одномерный массив из 9 элементов и распечатать его. Сортировка элементов в массиве
Сортировка представляет собой процесс упорядочения элементов в массиве по возрастанию или убыванию их значений. Например:
Массив Х из n
элементов будет отсортирован в порядке возрастания значений его элементов
, если
X[1] <= X[2] <= … <= X [n]
И в порядке убывания, если X[1] >= X[2] >= … >= X [n]
Способы сортировки массива:
Сортировка «перестановкой
»
Сортировка «
вставкой
»
Сортировка «
выбором
»
Сортировка «
пузырька
»
Быстрая сортировка
Сортировка массива методом «пузырька»
Сортировка методом пузырька использует метод обменной сортировки и основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.
Принцип сортировки массива по возрастанию методом «пузырька»
Сравним первый элемент массива со вторым. Если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвѐртого, I
-
го и (
I + 1)
-
го, (
n –
1)
-
го и n
-
го элементов. В результате этих действий самый большой элемент станет на последнее (
n
-
е) место. Теперь повторим данный алгоритм сначала, но последний (
n
-
й) элемент, рассматривать не будем, так как он уже занял своѐ место. После проведения данной операции самый большой элемент оставшегося массива встанет на (
n
-
1) место. Так повторяем до тех пор, пока не упорядочим весь массив.
Сортировка массива А состоящего из 5 элементов, по возрастанию методом «пузырька»
Номер элемента
1
2
3
4
5
Исходный массив
7
3
5
4
2
Первый просмотр
3
5
4
2
7
Второй просмотр
3
4
2
5
7
Третий просмотр
3
2
4
5
7
Четвертый просмотр
2
3
4
5
7
Таблица сортировки массива по возрастанию
Блок
-
схема сортировки массива методом «пузырька»
j:=1
i:=1
a[i]>a[i+1]
Pr:=a[i+1]; A[i+1]=a[i];
A[i]:=pr;
да
j:=j+1
да
нет
нет
j < n
i:=i+1
i< n
-
j
да
j=j+1
j=n
-
1
да
нет
нет
Сформировать массив из n элементов и упорядочить элементы в массиве по возрастанию их значений (метод «пузырька»)
Сортировка массива методом «перестановки»
Таблица сортировки массива по убыванию методом «перестановки»
перестановки
№ элеме
нтов
Значения элементов массива
Первая
Вторая
Третья
Четвертая
1
7
14
14
14
14
2
9
9
9
9
9
3
1
1
1
7
7
4
14
7
7
1
5
5
5
5
5
5
1
Если
n элементов, то количество перестановок n
2
Таблица сортировка массива по возрастанию методом «перестановки»
перестановки
№ элеме
нтов
Значения элементов массива
Первая
Вторая
Третья
Четвертая
1
7
1
1
1
1
2
9
9
5
5
5
3
1
7
7
7
7
4
14
14
14
14
9
5
5
5
9
9
14
Если
n элементов, то количество перестановок n
2
Блок
-
схема сортировки массива методом «перестановки»
i:=1
J:=i+1
a[i]>a[j]
Pr:=a[j]
A[j:]=a[i]
A[i]:=pr
да
j:=j+1
да
нет
нет
j < n
i:=i+1
i< n
-
1
да
Сформировать массив А размерностью 10. Задать значения элементов массива с помощью ГСЧ . Расположить элементы массива по возрастанию (метод перестановки).
Сформировать массив А размерностью 10. Задать значения элементов массива с помощью ГСЧ . Расположить элементы массива по убыванию (метод перестановки).
Сортировка массива методом «вставки»
Сначала упорядочиваются два элемента массива.
Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум.
Четвѐртый элемент помещают в список из уже упорядоченных трѐх элементов.
Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.
ПРИМЕР :
Дан массив из восьми элементов. Первые шесть уже упорядочены, а седьмой нужно вставить между вторым и четвѐртым. Сохраним его во вспомогательной переменной Х.
Пятый элемент переместим на место шестого, четвѐртый –
на место пятого, а третий на место четвѐртого. То есть выполнили сдвиг элементов массива на одну позицию вправо. Запишем содержимое вспомогательной переменной в третью позицию.
Y
1
Y
2
Y
6
Y
5
Y
4
Y
3
Y
8
Y
7
X Начало
Ввод n
i=1,n
Yi
i=2,n
X=Yi
j=i -
1
Yj+1=X
i=1,n
Yj
Конец
1
Блок
-
схема сортировки массива методом «вставки»
1
Yj+1=Yj
J=j -
1
J>0 and x<y
j
Фрагмент программы, реализующей сортировку массива методом вставки.
For i:=1 to n do
Begin
x:=y[i];{
Сохраним текущий элемент массива.
}
{
В переменной j будем хранить номера элементов, предшествующих текущему.
}
J:=i
-
1;
{
Сдвиг массива на одну позицию в право до тех пор, пока
}
While (x<y[j]) and (j>0) do
Begin
y[j+1] :=y[j]:
j:=j
-
1;
End;
{
Запись текущего элемента на соответствующую позицию
,}
{
то есть перед элементами
, превышающими его
.}
y[j+1]:=x;
end;
Сортировка массива по возрастанию методом «выбора»
•
Найдем в массиве самый большой элемент и поменяем его местами с последним элементом.
•
Повторим алгоритм поиска максимального элемента, уменьшив количество просматриваемых элементов на единицу и поменяем его местами с предпоследним элементом.
•
Описанную выше операцию поиска проводим до полного упорядочивания элементов в массиве..
Для упорядочивания массива по убыванию необходимо перемещать минимальный элемент.
Блок –
схема сортировки массива методом «выбора»
i=2,n
K=n
j=1,n
max=y[1]
nom=1
y[i]>max
max=y[i]
nom=i
n=n
-
1
b=y[nom]
y[nom]=y[n]
y[n]=b
Быстрая сортировка.
Один из самых
быстрых алгоритмов, позволяющих достигать производительности ~ O(n*log n).
1. В исходной последовательности выбирается некоторый опорный элемент a[i]
.
2. Пробегаемся по всей последовательности и элементы, меньшие, либо равные a[i]
располагаем слева от него, большие -
справа. 3.
Эту же самую процедуру рекурсивно запускаем для 2
-
х полученных половинок. <= a[i] a[i] >=a[i]
Т.е. в 2
-
х полученных последовательностях слева и справа от выбранного на первом шаге элемента -
также выбираем некоторый опорный ключ и перебрасываем соответствующие большие и меньшие чем он элементы. 4. В уже 4
-
х полученных последовательностях -
тоже самое. Пока не получим последовательности, состоящие лишь из одного элемента.
После выполнения всех рекурсий в результате получаем отсортированную исходную последовательность.
Принцип работы
Выбор опорного элемента
При быстрой сортировке выбор опорного элемента на каждом шаге
играет очень значительную роль, т.к. от этого зависит суммарная
скорость выполнения
всего
алгоритма при различных условиях сортировки.
Варианты выбора опорного элемента.
1.
Частичная упорядоченность элементов. 2.
Наиболее хаотичное расположение элементов. 3.
Самые распространенные варианты:
•
выбор середины отрезка
•
выбор случайного элемента последовательности
•
выбор первого элемента последовательности. Алгоритм выбора опорного элемента последовательности
Этот алгоритм был впервые описан К. А. Р. Хоаром в его классической статье «Быстрая сортировка» положение первого обмена
Чтобы отсортировать массив, мы разделяем его на два под массива и сортируем каждый из них рекурсивно. Например, для сортировки массива из семи элементов:
Разделение массива
4
9
7
6
2
3
8
i
j
4
9
7
6
2
3
8
4
3
7
6
2
9
8
4
3
2
6
7
9
8
Исходное положение
i
Положение второго обмена
Положение третьего обмена
j
i
j
i
j
program Quitsort;
uses
crt;
Const
N=10;
Type
Mas=array[1..n] of integer;
var
a: mas;
k: integer;
function Part(l, r: integer):integer;
var
v, i, j, b: integer;
begin
V:=a[r];
I:=l
-
1;
j:=r;
repeat
repeat
dec(j)
until (a[j]<=v) or (j=i+1);
repeat
inc(i)
until (a[i]>=v) or (i=j
-
1);
b:=a[i];
a[i]:=a[j];
a[j]:=b;
until i>=j;
a[j]:=a[i];
a[i]:= a[r];
a[r]:=b;
part:=i;
end;
procedure QuickSort(l, t: integer);
var i: integer;
begin
if l<t then
begin
i:=part(l, t);
QuickSort(l,i
-
1);
QuickSort(i+1,t);
end;
end;
begin
clrscr;
randomize;
for k:=1 to 10 do
begin
a[k]:=random(100);
write(a[k]:3);
end;
QuickSort(1,n);
writeln;
for k:=1 to n do
write(a[k]:3);
readln;
end.
Пример: Сформировать массив из 10 элементов. Значения задать ГСЧ. Отсортировать массив методом «быстрой сортировки».
Результат работы программы
60,79, 82, 58, 39, 9, 54, 92, 44, 32
60,79, 82, 58, 39, 9, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9, 32, 82, 58, 39, 60, 54, 92, 44, 79 9, 32, 44, 58, 39, 60, 54, 92, 82, 79
9, 32, 44, 58, 39, 54, 60, 92, 82, 79
9, 32, 44, 58, 39, 92, 60, 54, 82, 79
9, 32, 44, 58, 39, 54, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 60, 39, 54, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 58, 54, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 92, 82
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
Заключение
Метод быстрой сортировки позволяет существенно сократить количество операций.
Например: Все предыдущие методы требовали N
2
операций, где
N
–
количество элементов.
Метод быстрой сортировки требует в среднем N*Log
2
N операций.
В случае N=
100, выигрыш составляет порядка 100 раз.
Автор
zsh616
Документ
Категория
Методические пособия
Просмотров
4 152
Размер файла
384 Кб
Теги
элементов, сортировка, одномерного, массива1
1/--страниц
Пожаловаться на содержимое документа