Современные информационные технологии/2. Вычислительная техника и программирование

Мурадилова Г.С., Балгабаева Р.Н.

Кокшетауский государственный университет им.Ш.Уалиханова, Казахстан

НЕКОТОРЫЕ МЕТОДЫ СОРТИРОВКИ МАССИВОВ В КУРСЕ ДИСЦИПЛИНЫ «АЛГОРИТМИЗАЦИЯ И ЯЗЫКИ ПРОГРАММИРОВАНИЯ»

При изучении дисциплины «Алгоритмизация и языки программирования» студентами компьютерных специальностей, в целях развития алгоритмического мышления, умения применять полученные знания при решении задач различной направленности, закрепления понятий «функция», «рекурсия» серьезное внимание уделяется методам сортировки массивов.

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

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

Существует достаточно много методов (алгоритмов) сортировки массивов. Рассмотрим один из наилучших методов – метод Хоара. Он базируется на пузырьковом методе. В основе быстрой сортировки - "метода деления пополам". Эту сортировку также называют быстрой сортировкой - Quicksort. Метод был разработан в 1962 году профессором Оксфордского университета К. Хоаром.

Хоар предложил следующий алгоритм. Выберем какой-то средний элемент последовательности pp (обычно в качестве такового выбирают средний элемент). Если он стоит на своем месте (имеется ввиду ситуация, когда последовательность упорядочена), то все элементы, расположенные левее не больше pp, а элементы, находящиеся правее - не меньше pp.

Поэтому первый шаг быстрой сортировки заключается в том, чтобы перенести в левую часть массива те элементы правой половины, которые меньше pp, а в правую часть те элементы из левой половины, которые больше pp. Обычно при этом поиск ведут в обе стороны от pp и как только обнаруживают пару, нарушающую порядок, производят обмен. Затем аналогичный прием применяют к каждой из полученных половин. В каждой из них выбирается свой средний элемент и относительно него осуществляются необходимые перестановки. Как следует из описания, алгоритм Хоара очень хорошо укладывается в понятие рекурсивной процедуры. Для единообразия в обращении процедура быстрой сортировки представлена в виде двух процедур – внешней fun, к которой обращается пользователь, и внутренней – fun1. Последняя выполняет рекурсивную обработку подмассива, заданного граничными значениями индексов – l(left) и r(right).

Программная реализация метода Хоара представлена в листинге:

#include <iostream.h>

#include <conio.h>

void fun(int *y, int l, int r);

void fun1(int *y, int n)

{

fun(y,0,n-1);

return;

}

void fun(int *y, int l, int r)

{

register int i,j;

int pp,buf;

i=l;

j=r;

pp=y[(l+r)/2];

do

{

while (y[i] < pp && i < r) i++;

while (pp < y[j] && j > l) j--;

if(i<=j)

{

buf=y[i];

y[i]=y[j];

y[j]=buf;

i++; j--;

}

}

while(i<=j);

if(l < j) fun(y,l,j);

if(i < r) fun(y,i,r);

return;

}

int main(int argc, char* argv[])

{

int a[10];

int n=10;

for (int i=0;i<10;i++)

cin>>a[i];

fun1(a,n);

for (int i=0;i<10;i++)

cout<<a[i]<<" ";

getch();

return 0;

}