Сортировка массивов методом вставок

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Сортировка массивов методом вставок

Сортировка массивов методом вставок

Министерство Образования и Науки Украины

Национальный Аэрокосмический Университет

им. Н. Е. Жуковского “ХАИ”

Кафедра 302

Домашнее задание по курсу

„Программирование и алгоритмические языки”

по теме:

„СОРТИРОВКА МАССИВОВ МЕТОДОМ ВСТАВОК”

Выполнил:

студент 326 группы

Чаплыгин В. И.

Проверил:

Момот М. А.

Харьков

2003

Содержание

1. Постановка задачи ……………………………………………………………… 3

2. Теоретическое обоснование и алгоритм решения задачи …………………… 3

3. Пример работы программы ……………………………………………………. 4

4. Исходный код программы с комментариями …………...……………………. 9

5. Список литературы …………………………………………………………… 13

6. Приложение 1: блок-схема программы ……………………………………... 14

7. Приложение 2: блок-схема функции сортировки (SortByIncrease()) ……… 15

Постановка задачи

Задание:

Упорядочить массив x по убыванию или возрастанию (т.е. переставить его

элементы так чтобы для всех k выполнялось xk<=xk-1 или xk>=xk-1

соответственно), используя следующий алгоритм сортировки (упорядочивания):

сортировка вставками: пусть первые k элементов массива уже упорядочены

по не убыванию; берется (k+1)-й элемент и размещается среди первых k

элементов так, чтобы упорядоченными оказались уже k+1 первых элементов;

этот метод применяется при k от 1 до n-1.

Основные требования к программе:

. В программе должны использоваться функции, для которых следует явно

сопоставить прототипы (объявления, описания), определения и вызовы.

. Как минимум в одной функции должны быть параметры по умолчанию и

соответственно в программе должны быть вызовы такой функции в разной

форме.

. Использовать все циклы С++.

. Доступ к элементам массива по [] и *.

. Заполнение массива случайным образом.

. Программа должна создаваться из проекта, содержащего несколько файлов

исходного кода (*.h, *.срр).

. Должны использоваться уловная компиляция (стражи включения).

. Программа должна иметь дружественный интерфейс - основные операции

должны вызываться через соответствующие элементы текстового меню.

. Итерации в текстовый файл отчета.

. Передача имени файла отчета в командной строке.

. Считывание исходных данных из файла.

. Использование параметров командной cтроки.

Теоретическое обоснование метода

«Сортировка при помощи прямого включения»

и алгоритм решения задачи

Метод основывается на следующем: считается, что перед рассмотрением записи

R[j] предыдущие записи R[1],R[2],...,R[j-1] уже упорядочены, и R[j]

вставляется в соответствующее место. Сортировка таблицы начинается со

второй записи. Ее ключ сравнивается с ключом первой записи, и, если

упорядоченность нарушена, то записи R[1] и R[2] переставляются. Затем ключ

записи R[3] сравнивается с ключами записей R[2] и R[1]. Как только

программа обнаруживает, что (j+1)-й элемент массива меньше (при сортировке

по возрастанию) j-го элемента, она копирует значение этого элемента в

буферную переменную и с начала массива до j анализирует, пока значение

буферной переменной не будет меньше какого-либо элемента х. Затем кусок

массива, начиная с х и до j, перемещается на одну ячейку в сторону

возрастания, и на образовавшееся место х записывается значение

перемещаемого элемента. Дальше продолжается перемещение по основному

массиву до элемента n-1 (т.к. мы сравниваем j-й и (j+1)-й элементы):

41 54 10 66 27 42 80 61 43 37

^ <~~

10 41 54 66 27 42 80 61 43 37

^ <~~

10 27 41 54 66 42 80 61 43 37

^ <~~

10 27 41 42 54 66 80 61 43 37

^ <~~

10 27 41 42 54 61 66 80 43 37

^ <~~

10 27 41 42 43 54 61 66 80 37

^ <~~

10 27 37 41 42 43 54 61 66 80

см. приложение 2.

Пример работы программы

Запускаем программу InsetSort:

[pic]

Программа прелагает нам выбрать один из пунктов меню для выполнения

соответствующей операции. Итак, выбираем 1:

[pic]

Введем желаемое количество элементов массива.

[pic]

Массив создан. Теперь можно вывести массив на экран, добавить некоторое

количество элементов, найти какой-либо элемент по значению и т.д. Выведем

массив на экран.

[pic]

Также эта программа предоставляет возможность удалить какой-либо элемент,

введя его порядковый номер. Допустим, мы хотим удалить элемент под

номером 7 со значением 89, затем выведем снова массив на экран:

[pic]

Теперь добавим 6 элементов к существующему массиву:

[pic]

В программе реализована функция чтения из файла. Если задано три

параметра запуска программы, то она принимает argv[2], как название

файла, из которого будет происходить считывание информации. Если же

задано меньшее количество параметров, то InsetSort предложит ввести

названии файла в течении выполнения программы.

Перед выбором пункта 7 (Open File) необходимо очистить массив (пункт

6), иначе программа сигнализирует об ошибке. А после выбора элемента меню

7 введем название считываемого файла данных, если это необходимо.

(Первым элементом файла должно быть число, значение которого равно

количеству элементов в файле.) Проделаем вышеуказанные действия и выведем

результат на экран:

[pic]

При выборе пункта 9 у нас будет возможность отсортировать массив

элементов, как по возрастанию, так и по убыванию. Например, отсортируем

существующий массив по возрастанию и выведем результат на экран:

[pic]

В итоге мы получили отсортированный массив и массу удовольствия при

работе в этой чудотворной программе. А кроме этого еще и файл отчёта, в

который были записаны все шаги к полной сортировке массива.

Помните, что файл будет создан только после корректного завершения

программы InsetSort.

Исходный код программы с комментариями

-----------------------------------------------------------------

?“??.X??

#????v?? ??v??.??

??? ???v();

???????? ?;

???? ?????[20],??????[20];

??? *????[100]’{0},?’0,??????????;

////////////////////?“??/////////////////////

??? ????(??? ????,???? *????[]){

// ??? ?[10];

??? ????’0;//?S?S?S????, ??????????? ™®? ????S???.(??? ®???™?)

??????????’????;

?? (????>1)//???? ??™?? ?????S??, ?? ??????? S©?

??????(?????,????[1]);//??? ???®???S ™?? ????? ???S??.

????

??????(?????,????.????);

?? (????>2)

??????(??????,????[2]);//?????? ??©??S?? - ™?? ??S???.

?.????(?????);//???™???S ? ??™©???®?? ????? ? ??????.

??{//????????? ???? ????’0.

????’???v();//????®?? ??????? ???©?????.

}????? (????’’0);

?.?????();//???????S ????? ? ?????? ?? ??.

??v?<<??????????????????????;

??v?<<??????????. ? 0.3 (X) 2003-2004 X?????? ?? X???????? ???????.?;

???.???();

???.???();

???v?? 0;

}

////////////////////????////////////////////

??? ???v(){

??v?<<????<<? ???? ???v:?<<????;

??v?<<? 1. ???? ??? ????.? <<????;

??v?<<? 2. “?? ???????.? <<????;

??v?<<? 3. ????? ????.? <<????;

??v?<<? 4. ?????? ???????.?<<????;

??v?<<? 5. ???? ????.? <<????;

??v?<<? 6. ????? ????.? <<????;

??v?<<? 7. ???? ????.? <<????;

??v?<<? 8. ???? ???????.? <<????;

??v?<<? 9. ???? ????.? <<????;

??v?<<? 0. ????.? <<????;

??v?<<????<<???v? ?????? : ?;

??? ?;

??

????? (?<0 || ?>9);

?????? (?)

{???? 1 : ???????????(); ?????; //???? ??? ????

???? 2 : “??????????(); ?????; //“?? ???????

???? 3 : ?????????(); ?????; //????? ????

???? 4 : ?????????????(); ?????; //?????? ???????

???? 5 : ????????(); ?????; //???? ????

???? 6 : ?’0; ?????; //????? ????

???? 7 : ????????(); ?????; //???? ????

???? 8 : ???????????(); ?????; //???? ???????

???? 9 : ?v????v(); ?????; //???? ????

???? 0 : ???v?? -1;

//????

}

???v?? 0;

}//???v

-----------------------------------------------------------------

?v??.???

#????v?? ??v??.??

?????? ??? *????[100],?,??????????;

?????? ???????? ?;

????? ??? ?’100;

//////////////////???????????//////////////////

???? ???????????(){

?? (?!’0) {??v?<<????<<??????! ??v ???? ???????? ????.?;

??v?<<????<<?????? ??v? ?????v? ???? ??? ??? ?????.?<<????;}

???? {??v?<<????<<????v? ?v?????? ?? ????????: ?;

??{

???>>?;

?? ((?<1)||?>?){

??v?<<????<<???? ?v?????? ?? ?????????!?<<????;

??v?<<???? ?v?????? ?? ???????: ?<<?<<????;

??v?<<???? ?????: ?;}

}????? ((?<1)||(?>?));

?????(????(????));

??? (??? ?’0; ?<?; ?++){

????[?]’??? ???;

*????[?]’????()%100;}

}

}

//////////////////“??????????///////////////////

???? “??????????(){

??v?<<????<<????v? ?v?????? ?? ????????: ?;

??? ?;

??{

???>>?;

?? ((?<1)||((?+?)>?)){

??v?<<????<<???? ?v?????? ?? ?????????!?<<????;

??v?<<???v ???? ?<<?-?<<? ???? ?????.?<<????;

??v?<<???? ?????: ?;}

}????? ((?<1)||((?+?)>?));

?????(????(????));

??? (??? ?’?; ?<(?+?); ?++){

????[?]’??? ???;

*????[?]’????()%100;}

?’?+?;

}

////////////////////?????????///////////////////

???? ?????????(){

?? (?’’0) ??v?<<????<<????? ?? ?????.?<<????;

????{

??v?<<????;

???(??? ?’0; ?<?; ?++){

?? (?%10’’0) ??v?<<????;

??v?<<????(3)<<*????[?];}

??v?<<????;

}

}

////////////////?????????????///////////////////

???? ?????????????(){

?? (?’’0) ??v?<<????<<????? ?? ?????.?<<????;

????

}

////////////////////???? ????/////////////////////

???? ????????(){

?? (?’’0) ??v?<<????<<????? ?? ?????.?<<????;

????{

??? (??? ?’0; ?<?; ?++){

?? (?%10’’0) ?<<????;

?<<????(3)<<*????[?];}

?<<????;

}

}

///////////////////???????????////////////////////

???? ???????????(){

?? (?’’0) ??v?<<????<<????? ?? ?????.?<<????;

????{

??v?<<????<<????v? ??? ???v?, ????? ?v?? ?? ??????: ?;

??? ?,?’0; ???>>?;

??? (??? ?’0; ?<?; ?++){

?? (*????[?]’’?) {

??v?<<????<<(?+1)<<?-?? ????????<<? - ?<<*????[?];

?’?;}}

?? (?’’0) ??v?<<????<<???? ???????? ???? ?????? ??????? ????

???? ???v??;

??v?<<????;

}

}

//////////////////?v?????(????)///////////////////

???? ?v????v(){

?? (?’’0) ??v?<<????<<????? ?? ?????.?<<????;

????{

??v?<<????<<? ?v? ???v:?<<????;

??v?<<? 1. ???? ???? ?? ????????.?<<????;

??v?<<? 2. ???? ???? ?? ????????.?<<????<<????;

??? ?;

??v?<<???v? ??????: ?;

?? ???>>?;????? (?<1 || ?>2);

?????? (?)

{???? 1 : ??????????????(); ?????; //????????

???? 2 : ??????????????(); ?????; //????????

}

}

}

/////////////////??????????????//////////////////

???? ??????????????(){

??? ?v?;

??? (??? ?’0; ?<(?-1); ?++){

?? (*????[?]>*????[?+1]){

????????();

?v?’*????[?+1];

??? (??? ?’0; ?<(?+1); ?++){

?? (?v?<*????[?]){

??? (??? ?’?+1; ?>?; ?--)

*????[?]’*????[?-1];

*????[?]’?v?;

?????;

}//?????? ?????

}//??? ?????? ?????

}//???? v??????? ???????

}//??? ???? v??????? ???????

????????();

}

/////////////////??????????????//////////////////

???? ??????????????(){

??? ?v?;

??? (??? ?’0; ?<(?-1); ?++){

?? (*????[?]<*????[?+1]){

????????();

?v?’*????[?+1];

??? (??? ?’0; ?<(?+1); ?++){

?? (?v?>*????[?]){

??? (??? ?’?+1; ?>?; ?--)

*????[?]’*????[?-1];

*????[?]’?v?;

?????;

}//?????? ?????

}//??? ?????? ?????

}//???? v??????? ???????

}//??? ???? v??????? ???????

????????();

}

///////////////////???? ????/////////////////////

???? ????????(???? ?[20]){

?? (?!’0) {??v?<<????<<??????! ??v ???? ???????? ????.?;

??v?<<????<<?????? ??v? ?????v? ???? ??? ??? ?????.?<<????;}

???? {

?? (??????????<3){

??v?<<????<<????v? ???? ????: ?;

???? *????????’??? ????[20];

???>>????????;

?’????????;}

???????? ??(?,???::????????);

?? (! ??) ??v?<<????? ??? ??v??.?<<????;

????{

??? ?;

??>>?;

??? (??? ?’0; ?<?; ?++){

?? (?’’?) ?????;

????[?]’ ??? ???;

??>>*????[?];

?++;

}

}//?? (! ??)...

}

}

-------------------------------------------------------------------

?v??.?

//??™?????S? ?????? ®????S???.

#?????? __?v??_?

#?????? __?v??_?

#????v?? <????????.?>

#????v?? <???????.?>

#????v?? <??????.?>

#????v?? <???????.?>

#????v?? <??????.?>

#????v?? <????.?>

?????? ???? ??????[20];

//????????? ???????.

???? ???????????();

???? “??????????();

???? ?????????();

???? ?????????????();

???? ????????();

???? ?????????();

???? ???????????();

???? ?v????v();

???? ??????????????();

???? ??????????????();

???? ????????(???? ?[20]’??????);

#?????

Список литературы

1. Лафоре Р. Объектно-ориентированное программирование в С++, 4-е изд. -

СПб.: Питер, 2003. – 928 с.: ил.

2. Дейтел Х.М., Дейтел П.Дж. Как программировать на С++.. – М.: Бином,

1999. - 1024 с.

3. Страуструп Б. Язык программирования С++, 3-е изд. - СПб.; М.: Невский

Диалект - Бином, 1999. - 991 с.

4. Керниган Б., Ритчи Д. Язык программирования Си.\Пер. с англ., 3-е

изд., испр. - СПб.: "Невский Диалект", 2001. - 352 с.: ил.

[pic]

Примечание 1.

[pic]

Примечание 2.