Региональная научная конференция школьников
«ИНИЦИАТИВА МОЛОДЫХ»
Секция «Информатика и ИКТ»
Работу выполнил
Цветков Виктор
учащийся 9 класса
МОУ-СОШ с. Кировское
Марксовского района
Руководитель учитель математики и
информатики высшей
квалификационной категории
2012 г.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ ……………………………………………………………………3
Глава 1. МЕТОД ВЫБОРА …………………………………………………...5
Глава 2. МЕТОД ОБМЕНА (МЕТОД ПУЗЫРЬКА) ………………………..10
Глава 3. МЕТОД ВСТАВКИ …………………………………………………14
ЗАКЛЮЧЕНИЕ ……………………………………………………………….16
ИСТОЧНИКИ ИНФОРМАЦИИ ……………………………………..………17
ВВЕДЕНИЕ
«Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования”.
Д. Кнут
Сортировка массива – один из наиболее распространенных процессов обработки данных.
Так, например, список учеников класса, фамилии в телефонном справочнике, банковские картотеки клиентов всегда отсортированы для облегчения доступа к нужной информации. Сортировка – это размещение объектов в определенном порядке. Числа могут размещаться по возрастанию или по убыванию, фамилии – в алфавитном порядке.
Механические сортировки – построение солдат по росту, раскладка денежных купюр или игральных карт по их достоинству и т. д., имеют место в повседневной жизни и кажутся простыми. Простота эта иллюзорна, потому что сортируется небольшое количество элементов.
Первые программы сортировки были написаны фон Нейманом в 1945 году и до середины 60-х годов какого-либо продвижения в теории сортировки не наблюдалось. Проблема сортировки остро возникла с широким внедрением ЭВМ в бизнес, где необходимо было обрабатывать огромные массивы числовой и текстовой информации.
Сортировка – это идеальный объект для демонстрации огромного разнообразия алгоритмов, изобретенных для одной и той же задачи. Поэтому это еще и идеальный объект, демонстрирующий необходимость анализа производительности алгоритмов. На примерах сортировок можно показать, как путем усложнения алгоритма, можно добиться значительного выигрыша в эффективности.
Методы сортировки делятся на прямые и улучшенные.
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, с использованием оригинальных идей и рационализаций для ускорения процесса преобразования массива данных. Поэтому для понимания основных принципов большинства сортировок изучение лучше начинать с прямых методов. К тому же, так как улучшенные методы требуют большого числа операций, для массивов размерностью меньше 100 элементов, прямые методы оказываются эффективнее. Прямые методы актуальны еще и тем, что моделируют естественное поведение человека, осуществляющего сортировку вручную.
Прямые методы разделяются по принципу, лежащему в их основе, на сортировки:
o обменом (метод пузырька);
o выбором (метод выбора);
o вставкой (метод вставки).
В данной работе можно познакомиться с прямыми методами сортировки одномерного массива и с алгоритмами их реализации, а также узнать о том, какие из них наиболее эффективны и в каких случаях.
Глава 1. МЕТОД ВЫБОРА
Метод выбора основан на методе нахождения максимального или минимального элементов массива. В самом деле, после того, как будут найдены максимальный или минимальный элементы, будет известно, что именно они будут первым или последним элементами отсортированного массива.
Допустим, нужно отсортировать одномерный числовой массив A размерностью n по возрастанию. Чтобы сэкономить память, необходимо поменять полученное значение максимума со значением в последней ячейке.
Пусть максимальным оказалось значение в ячейке i. Тогда следует произвести следующий обмен:
A(i)=A(n)
A(n)=A(i), равному MAX.
Поскольку наибольший элемент мы уже нашли, то перед ним должен встать наибольший элемент из оставшихся элементов массива. Процесс повторяется, но уже с массивом из (n – 1) элементов. Второй по величине элемент встанет на предпоследнее место.
Повторяя процесс, необходимое число раз, мы полностью отсортируем массив по возрастанию.
Рассмотрим работу алгоритма.
1. Задаем размер массива.
2. Проверяем, не вышли ли мы за границы массива. Если вышли – прекращаем работу. Если не вышли – продолжаем.
3. Находим максимум на заданном интервале и запоминаем, в какой ячейке лежало максимальное значение.
4. Меняем значения в ячейках местами.
5. Изменяем интервал поиска.
6. Возвращаемся к п. 2.
Программа на языке Pascal, реализующая данный алгоритм, выглядит следующим образом:
сonst n = 10;
var
arr: array[1..n] of byte;
max, id_max, i, j, k: byte;
BEGIN
randomize;
for i := 1 to n do begin
arr[i] := random(256);
write(arr[i]:4)
end;
writeln;
writeln('*****');
j := n;
while j > 1 do
begin
max := arr[1]; id_max := 1;
for i := 2 to j do if arr[i] > max then begin
max := arr[i]; id_max:=i;
end;
arr[id_max] := arr[j];
arr[j] := max;
j := j - 1;
write('max=',max:4,' ');
for k := 1 to n do write(arr[k]:4);
writeln;
writeln('');
end;
writeln('массив отсортирован ');
for i := 1 to n do write(arr[i]:4);
readln
END.
На рисунке представлен результат выполнения данной программы, по которому можно проследить пошаговое выполнение данного алгоритма.
 |
Скорость работы алгоритма можно увеличить вдвое, используя одновременно максимальное и минимальное значения. В этом случае программа на языке Pascal будет выглядеть следующим образом:
const n= 10;
var arr:array[1..n] of byte;
max, id_max, min, id_min, f,i, j,k:byte;
BEGIN
randomize;
for i:= 1 to n do begin
arr[i]:=random(256);
write(arr[i]:4)
end;
writeln;
writeln('**');
j:= n;
f:=1;
while j>(n div 2) do
begin
max:= arr[f];
id_max:=f;
min:=arr[f];
id_min:=f;
for i:= f to j do
if arr[i]>max then
begin
max:= arr[i];
id_max:=i;
end;
arr[id_max]:=arr[j];
arr[j]:=max;
for i:= f to j do
if arr[i]<min then
begin
min:= arr[i];
id_min:=i;
end;
arr[id_min]:=arr[f];
arr[f]:=min;
j:=j-1;
f:=f+1;
write('max=',max:4,' ');
writeln('min=',min:4);
for k := 1 to n do write(arr[k]:4);
writeln;
writeln('');
end;
writeln('массив отсортирован');
for i := 1 to n do write(arr[i]:4);
readln
END.
По результату выполнения данной программы видно, что количество шагов сокращено вдвое:
Данный алгоритм можно использовать для сортировки как числовой, так и текстовой информации. В случае сортировки текстовой информации сортировка кодов символов, из которых состоят текстовые строки, по возрастанию соответствует сортировке самих текстовых строк по алфавиту.
Кроме рассмотренного метода выбора, существуют и многие другие способы сортировки массива. Они различаются алгоритмической сложностью, затратами вычислительных мощностей и скоростью работы. Использование различных алгоритмов обусловлено типом информации, которую необходимо рассортировать, а точнее, типом ее "разупорядоченности". В частности, это зависит от степени так называемой "разреженности" массива. "Разреженный" массив – это массив, большинство элементов которого равны (например, нулевые) и лишь немногие имеют различные значения.
Пример разреженного массива:
1,0,0,0,0.5,0,0,0,0,0,9,0,0,7,6,0,0,0
Еще пример разреженного массива:
Пусто
Пусто
Пусто
Дерево
Пусто
Пусто
Дом
Пусто
Пусто
Методом выбора гораздо быстрее сортируются разреженные массивы, нежели массивы других типов. Дело в том, что при использовании метода выбора компьютер осуществляет большое количество арифметических операций только тогда, когда приходится заменять одно значение другим. В разреженном массиве результат сравнения в большинстве случаев не вызовет никаких действий, поэтому практически все время выполняется только одна операция – сравнение, которую компьютер выполняет очень быстро.
Однако в том случае, когда элементы массива сильно перемешаны, метод выбора будет работать долго.
Глава 2. МЕТОД ОБМЕНА (МЕТОД ПУЗЫРЬКА)
Методом, оптимизированным на упорядочивание больших объемов сильно разупорядоченных элементов является метод обмена, или метод пузырька.
Его основная стратегия – минимум вычислительных операций при обмене элементов местами.
Самая простая операция при сортировке производится в три действия. Рассмотрим алгоритм сортировки по убыванию. Нужно:
1. Для n элементов сравнить два соседних элемента.
2. Если "нижний" элемент больше "верхнего", поменять их местами.
3. 
Сделать шаг вниз и перейти к п. 1.
При одном проходе такого алгоритма по массиву, наибольшие по значению элементы продвигаются ("всплывают") на один шаг вверх, а наименьшее значение опускается в самый низ, "утопает". Именно за такое поведение элементов при сортировке массива метод и назван "пузырьковым".
Для того чтобы массив из n элементов был полностью отсортирован, алгоритм метода обмена следует повторить (n-1) раз.
Обратим внимание, что после 1-го прохода самый нижний, n-й, элемент займет свое место. После k-го прохода элементы от (n – k + 1)-го до n-го займут правильные места. Следовательно, длину каждого последующего прохода можно сократить на один шаг.
Рассмотрим пример. В полном алгоритме метода обмена при сортировке массива из 10 элементов производится 81 сравнение пары элементов (9 проходов по 9 сравнений: 9*9=81). В сокращенном алгоритме производится 45 сравнений пары элементов (9 проходов по убывающей от 9 сравнений до 1: 9+8+7+6+5+4+3+2+1=45). Во втором случае происходит значительная экономия вычислительных ресурсов.
Программа на языке Pascal, реализующая сокращенный алгоритм сортировки методом «пузырька» будет выглядеть следующим образом:
const n= 10;
var arr:array[1..n] of byte; i, j,k, buf:byte;
BEGIN
randomize;
for i:= 1 to n do begin
arr[i]:=random(256);
write(arr[i]:4)
end;
writeln;
writeln('***');
for k:=1 to n-1 do
begin
for j:=1 to n-k do if arr[j]<arr[j+1] then
begin
buf:=arr[j+1];
arr[j+1]:=arr[j];
arr[j]:=buf;
end;
for i := 1 to n do write(arr[i]:4);
writeln;
writeln('');
end;
writeln('массив отсортирован');
for i := 1 to n do write(arr[i]:4);
readln
END.
На рисунке представлен результат выполнения сортировки массива методом пузырька, на котором можно проследить пошаговое выполнение данного алгоритма.
 |
Однако возможен случай, когда массив уже в достаточной мере упорядочен. Тогда даже в сокращенном алгоритме появится много холостых проходов. Приведем пример массива, сортировка которого завершится на первом же проходе:
6 | 7 | 4 | 5 | 2 | 3 | 1 |
В данном массиве поменяются местами пары цифр: 6 и 7; 4 и 5; 2 и 3, а остальные проходы будут холостыми.
Чтобы избежать этой ситуации, в алгоритм включают так называемый "флажок" – логическую переменную, которая устанавливается в значение "true" перед началом каждого прохода. Если была выполнена, хотя бы одна операция обмена, флажок устанавливается в значение "false". После окончания каждого прохода значение флажка проверяется. Если он так и остался в значении "true", сортировка прекращается досрочно.
Таким образом, вводя дополнительный оператор сравнения, мы улучшаем свойства алгоритма. Вот так будет выглядеть программа на языке Pascal, реализующая сортировку методом пузырька с флажком:
const n= 10;
var arr:array[1..n] of byte; i, j,k, c:byte;
flag:boolean;
BEGIN
randomize;
for i:= 1 to n do begin
arr[i]:=random(256);
write(arr[i]:4)
end;
writeln;
writeln('*');
i:=0;
flag:=true;
While flag do
begin
i:=i+1;
flag:=false;
for j:=1 to n-i do
if arr[j] < arr[j+1] then
begin
c:=arr[j]; arr[j]:=arr[j+1]; arr[j+1]:=c; {меняем элементы местами}
flag:=true;
end;
for k := 1 to n do write(arr[k]:4);
writeln;
writeln('');
end;
writeln('массив отсортирован');
for i := 1 to n do write(arr[i]:4);
readln
END.
Будучи введенный в программу, флажок замедляет вычисления на каждом шаге, но может сократить количество шагов в некоторых случаях организации массива.
На рисунке приведен результат выполнения программы сортировки массива методом пузырька с применением флажка. Мы видим, что применение флажка сократило количество шагов в два раза.
 |
Применять или не применять флажок – это решает программист, основываясь на знании структуры исходных данных.
Глава 3. МЕТОД ВСТАВКИ
Метод вставки широко используется при игре в карты.
Суть метода заключается в следующем алгоритме. Массив данных разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части принимается первый элемент массива.
Таким образом будет иметь место n-1 проход (где n размерность массива), каждый из которых будет включать четыре действия:
1) взятие очередного элемента из неотсортированной части и сохранение в дополнительной переменной;
2) поиск позиции в отсортированной части массива для вставки элемента, взятого предыдущим действием, который бы не нарушил порядок;
3) сдвиг элементов массива для вставки элемента массива в отсортированную часть;
4) вставка элемента в найденную позицию.
Для реализации данного метода существует несколько алгоритмов, которые отличаются способом поиска позиции вставки. Программа на языке Pascal, реализующая один из таких алгоритмов выглядит так:
const n= 10;
var arr:array[1..n] of byte;
i, j,x, k,l:byte;
BEGIN
randomize;
for i:= 1 to n do begin
arr[i]:=random(256);
write(arr[i]:4)
end;
writeln;
writeln('*');
for i:=2 to n do
begin
x:=arr[i];
j:=1;
while x>arr[j] do j:=j+1;
for k:=i-1 downto j do arr[k+1]:=arr[k];
arr[j]:=x;
for l := 1 to n do write(arr[l]:4);
writeln;
writeln('');
end;
writeln('массив отсортирован');
for i := 1 to n do write(arr[i]:4);
readln
END.
На рисунке представлен результат пошагового выполнения этой программы:
Хотя алгоритм сортировки методом вставки уступает в эффективности более сложным, у него есть ряд преимуществ:
o эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
o эффективен на наборах данных, которые уже частично отсортированы;
o это устойчивый тип сортировки (не меняет порядок элементов, которые уже отсортированы;
Минусом является высокая сложность алгоритма.
ЗАКЛЮЧЕНИЕ
Сортировка – достаточно хороший пример задачи, которую можно решать с помощью многих различных методов. Каждый из них имеет и свои достоинства, и свои недостатки, и выбирать алгоритм нужно, исходя из конкретной постановки задачи и в зависимости от структуры обрабатываемых данных.
При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
o количество присваиваний;
o количество сравнений.
Прямые методы сортировки требуют приблизительно n2 сравнений, где n – размерность массива. Количество присваиваний чаще всего зависит от предварительной упорядоченности массива. Поэтому оптимальной сортировки не существует.
Прямые методы сортировки, рассмотренные в работе, на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. Кроме того, в некоторых случаях (как правило, при небольшой длине массива и/или особом исходном расположении элементов массива) некоторые из прямых методов могут даже превзойти по эффективности улучшенные методы.
ИСТОЧНИКИ ИНФОРМАЦИИ
1. Изучаем Turbo Pascal. – СПб.: Питер, 2002.
2. , Некоторые вопросы школьного курса информатики и методики её преподавания. – Саратов: Изд-во Сарат. ун-та, 2006.
3. Алгоритмы сортировки массивов. – М.: Наука, 1997.
4. http://students. *****/students/yakimenko4/index. php? cont=8
5. http://knowledge. *****/programming/3c0a65625a2ad68a5d43bd27_0.html
6. http://web-pascal. *****/stat/sort. htm
