Учебнометодические указания к лабораторной работе 7 по курсу Информатика Разработка программы сортировки элементов массива Томск 2011 г
 Скачать 261.04 Kb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» Учебно-методические указания к лабораторной работе №7 по курсу Информатика Разработка программы сортировки элементов массива Томск 2011 г. 2 СОДЕРЖАНИЕ ВВЕДЕНИЕ 3 1 Алгоритмы сортировки 4 1.1 Метод пузырька (обменная сортировка с выбором) 4 1.2 Сортировка выбором 7 1.3 Сортировка методом Шелла 7 1.4 Другие алгоритмы сортировки. Сравнение алгоритмов 8 2 Операторы циклов 9 2.1 Оператор цикла while 11 2.2 Оператор цикла for 12 2.3 Оператор цикла do while 14 2.4 Вложенные циклы 15 3 ВВЕДЕНИЕ Данные учебно-методические указания содержат теоретический материал необходимый для выполнения лабораторной работы №7 «Разработка программы сортировки элементов массива» по курсу Информатика для бакалавров направления 140800 «Ядерные физика и технологии». В частности, рассматриваются понятие «сортировки» данных, некоторые методы сортировки и их сравнение по времени выполнения данной процедуры. 4 1 Алгоритмы сортировки Очень часто при обработке данных требуется их отсортировать, иначе говоря, упорядочить их определенным образом. Сортировка применяется в очень многих областях, будь то математические программы для расчетов или базы данных. Существует множество различных методов сортировки данных, которые подробнейшим образом описаны в классической работе Д. Кнута "Искусство программирования для ЭВМ". Причем для разных типов данных иногда целесообразно применять разные методы сортировки. Но, тем не менее, практически каждый алгоритм сортировки можно разбить на три части: − сравнение, определяющее упорядоченность пары элементов; − перестановку, меняющую местами пару элементов; − собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены. Подобными свойствами обладают и те наиболее часто используемые алгоритмы сортировки, которые будут рассмотрены ниже. 1.1 Метод пузырька (обменная сортировка с выбором) Идея этого метода отражена в названии. Самые легкие элементы массива “всплывают” наверх, самые “тяжелые” – тонут. Алгоритмически это можно реализовать следующим образом: будем просматривать весь массив “снизу вверх” (от первого элемента к последнему) и менять стоящие рядом элементы в том случае, если “нижний” элемент меньше, чем “верхний”. Таким образом, мы вытолкнем наверх самый “легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортированными первых N-1 элементов (т.е. для тех, которые лежат “ниже” первого). В результате второй по величине “пузырек” встанет на свое место (второе с конца). Очевидно, что такую процедуру необходимо проделать N-1 раз, так как в тот момент, когда (N-1) ый по счету элемент попадет на свое место, последний из сортируемых автоматически окажется на первом месте. Пример: дана D – последовательность из 5 (N=5) чисел, которую и будем сортировать по убыванию. D: 10 3 -1 4 15 d 1 d 2 d 3 d 4 d 5 5 1) Задаем k=1 (должен "всплыть" первый "пузырек"). 1.1. Задаем i=1; проверяем условие i ≤ N-k, т.е. 1≤5-1? – да, значит, будем сравнивать d i и d i+1 , т.е. d 1 и d 2 : 10<3? – нет, поэтому d 1 и d 2 местами не меняем. D: 10 3 -1 4 15 d 1 d 2 d 3 d 4 d 5 1.2. Задаем i=2; проверяем условие 2 ≤5-1? – да, значит, будем сравнивать d 2 и d 3 : 3<-1? – нет, поэтому d 2 и d 3 местами не меняем. D: 10 3 -1 4 15 d 1 d 2 d 3 d 4 d 5 1.3. Задаем i=3; проверяем условие 3 ≤5-1? – да, значит, будем сравнивать d 3 и d 4 : - 1<4? – да, поэтому d 3 и d 4 меняем местами. D: 10 3 4 -1 15 d 1 d 2 d 3 d 4 d 5 1.4. Задаем i=4; проверяем условие 4 ≤5-1? – да, значит, будем сравнивать d 4 и d 5 : - 1<15? – да, поэтому d 4 и d 5 меняем местами. D: 10 3 4 15 -1 d 1 d 2 d 3 d 4 d 5 1.5. Задаем i=5; проверяем условие 5 ≤5-1? – нет, значит, мы закончили проверять неотсортированную часть. Действительно, самое маленькое число (-1) встало на последнее место, т.е. первый "пузырек" "всплыл". 2) Задаем k=2 (должен "всплыть" второй "пузырек"). 2.1. Задаем i=1; проверяем условие i ≤ N-k, т.е. 1≤5-2? – да, значит, будем сравнивать d i и d i+1 , т.е. d 1 и d 2 : 10<3? – нет, поэтому d 1 и d 2 местами не меняем. D: 10 3 4 15 -1 d 1 d 2 d 3 d 4 d 5 2.2. Задаем i=2; проверяем условие 2 ≤5-2? – да, значит, будем сравнивать d 2 и d 3 : 3<4? – да, поэтому d 2 и d 3 меняем местами. D: 10 4 3 15 -1 d 1 d 2 d 3 d 4 d 5 2.3. Задаем i=3; проверяем условие 3 ≤5-2? – да, значит, будем сравнивать d 3 и d 4 : 3<15? – да, поэтому d 3 и d 4 меняем местами. D: 10 4 15 3 -1 d 1 d 2 d 3 d 4 d 5 6 2.4. Задаем i=4; проверяем условие 4 ≤5-2? – нет, значит, мы закончили проверять неотсортированную часть. Действительно, второе по величине маленькое число (3) встало на предпоследнее место, т.е. второй "пузырек" "встал" на свое место. Далее повторяем все действия при k=3, и т.д. до полного упорядочивания последовательности. Блок-схема данного алгоритма приведена на рисунке 1. d i < d i+1 нет да k = 1; k ≤ N-1; k = k+1 i = 1; i ≤ N-k; i = i+1 c = d i d i = d i+1 d i+1 = c Цикл, отвечаю- щий за номер очередного "пу- зырька" Цикл, отвечаю- щий за перебор неотсортирован- ных элементов Рисунок 1 – Блок-схема сортировки последовательности по убыванию значений методом пузырька Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Очевидно, что данный алгоритм можно несколько “модернизировать”, добавив во внутреннем цикле проверку “была ли хоть одна перестановка?”, а во внешнем проверять её результат (если ни одной перестановки не было – значит, последовательность уже упорядочена). Таким образом, можно избавиться от лишнего выполнения внешнего цикла, сократив тем самым общее количество действий, а следовательно, и время выполнения. 7 1.2 Сортировка выбором Смысл данного алгоритма сводится к следующему: 1. Задаем номер места К в последовательности, на которое нужно будет поместить очередной упорядочиваемый элемент. 2. Находим в неупорядоченной части последовательности элемент с самым большим (или самым маленьким) значением, запоминая его номер. 3. Меняем его местами с тем, который находится на К-ом месте. 4. Все указанные операции повторяются до тех пор, пока не упорядочим всю последовательность. Блок-схема алгоритма сортировки данным методом приведена на рисунке 2. cm < d i нет да k = 1; k ≤ N-1; k = k+1 i = k+1; i ≤ N; i = i+1 d nc = d k d k = cm cm = d i nc = i cm = d k nc = k 1 2 3 Рисунок 2 – Блок-схема сортировки последовательности по убыванию значений методом выборки максимального элемента 1.3 Сортировка методом Шелла Основная идея сортировки по Шеллу заключается в том, что сначала сравниваются удаленные друг от друга элементы, а не смежные, как в методе «пузырька». Это приводит к быстрому устранению большей части неупорядоченности и сокращает последующую работу. Интервал между элементами постепенно сокращается до единицы, когда сортировка фактически превращается в метод перестановки соседних элементов. 8 На блок-схеме, приведенной на рисунке 3, представлен алгоритм сортировки последовательности D, состоящей из N элементов. temp = d k d k = d k+sh d k+sh = temp i = sh+1; i ≤ N; i = i+1 sh=N/2; sh≥1; sh = sh/2 k = i-sh; k > 0 и d k >d k+sh ; k = k-sh Рисунок 3 – Блок-схема сортировки последовательности по убыванию значений методом Шелла. Здесь имеются три вложенных цикла. Самый внешний цикл управляет интервалом (обозначен sh) между сравниваемыми элементами, уменьшая его от N/2 в два раза при каждом проходе, пока он не станет равным нулю. Средний цикл сравнивает каждую пару элементов, разделенных на величину интервала. Самый внутренний цикл переставляет любую неупорядоченную пару. Так как интервал sh в конце концов сводится к единице, все элементы в результате упорядочиваются правильно. /Описание взято из: Карниган Б., Ритчи Д. Язык программирования Си./ 1.4 Другие алгоритмы сортировки. Сравнение алгоритмов Конечно же, на самом деле алгоритмы сортировки не ограничиваются методами, изложенными выше. В статье С. Курковского “Алгоритмы сортировки” (журнал “Монитор”, №6-7, 1992г.) приведены также метод Хоора, называемый также быстрой сортировкой, и метод сортировки с помощью бинарного дерева. Оттуда же взята диаграмма, на которой сравнивается быстродействие этих алгоритмов (рисунок ). 9 Рисунок 4 Очевидно, что для организации перебора неотсортированной части последовательности полезно применить цикл. Кроме того, еще один цикл (очевидно, внешний) будет "отвечать" за номер элемента, который "становится на свое место" в данный момент. Поэтому вспомним, как организуются операторы цикла в языке СИ. 2 Операторы циклов Циклом называется последовательность операторов, которая выполняется несколько раз в процессе выполнения программы при различных значениях некоторой переменной или при выполнении какого-то условия. Например, необходимо вычислить среднее значение последовательности а 0 , а 1 , а 2 , … а 10 В этом случае в программе можно написать следующее: float a[10], sum, sr; sum = 0; sum = sum + a[0]; sum = sum + a[1]; sum = sum + a[9]; sr = sum/10; Собственно для подсчета суммы необходимо написать 10 операторов присваивания, имеющих одинаковый вид и отличающихся только индексами текущих элементов массива. А что делать, если длина последовательности не 10, а 100? Или конкретное количество обрабатываемых элементов вводится пользователем уже в ходе выполнения вашей программы? В последнем случае просто неизвестно заранее, сколько операторов присваивания нужно выполнить. В этом случае на помощь и приходит такой инструмент, как цикл. 10 В этом случае алгоритм для расчета суммы первых N элементов последовательности А и вычисления затем среднего значения можно записать следующим образом: 1. Задаём начальное значение для суммы, равное нулю (СУММА = 0). 2. Задаем начальный номер элемента массива, например, 1 (ИНДЕКС = 1). 3. К сумме добавляем значение элемента массива с номером ИНДЕКС (СУММА = СУММА + А[ИНДЕКС]). 4. Увеличиваем ИНДЕКС на 1 (ИНДЕКС = ИНДЕКС + 1). 5. Проверяем, не вышли ли за пределы массива (ИНДЕКС<=N ?). 6. В случае результата “истина” возвращаемся к п.№3, в случае результата “ложь” переходим к следующему пункту (в нашем случае №7). 7. Вычисляем среднее (СРЕДНЕЕ = СУММА / N). Блок-схема алгоритма приведена на рисунке 5. ИНДЕКС ≤N ИНДЕКС = ИНДЕКС + 1 нет да СУММА = СУММА+ А[ИНДЕКС]) СУММА=0 ИНДЕКС = 1 Рисунок 5 – Алгоритм расчета суммы последовательности А длиной N Повторяющиеся действия (п.3, 4, 5) и будут выполняться циклически. В языке Си реализовано три вида циклов: while(), for() и do ... while(). С учетом этого, варианты реализации приведенного выше примера приведены в таблице 1: 11 Таблица 1 С использованием оператора for() С использованием оператора while() С использованием оператора do... while() С использованием операторов if и goto sum = 0; for (i=0; i } sr = sum/10; i = 0; sum = 0; while ( i < n ) { sum = sum + a[i]; i++; } sr = sum/10; i = 0; sum = 0; do { sum = sum + a[i]; i++; } while ( i < n ); sr = sum/10; i = 0; sum = 0; m: sum = sum + a[i]; i++; if ( i < n ) goto m; sr = sum/10; 2.1 Оператор цикла while Структура оператора (рисунок 6): while (выражение) оператор; выражение нет да оператор нет да Рисунок 6 Оператор while определяет операции, которые циклически выполняются до тех пор, пока проверяемое "выражение" не станет ложным, или равным нулю, т.е. если "выражение" истинно (или а общем случае не равно нулю), то "оператор" (или "тело цикла") выполняется один раз, а затем "выражение" проверяется снова. Эта последовательность действий, состоящая из проверки и выполнения тела цикла, периодически выполняется до тех пор, пока "выражение" не станет ложным. Каждый такой шаг называется "итерация". Оператор while – это цикл с предусловием; решение, выполнять ли в очередной раз тело цикла, принимается перед началом его прохождения. Поэтому вполне возможно, что тело цикла не будет выполнено ни разу. "Оператор", образующий тело цикла, может быть либо простым (одиночным, заканчивающимся символом "точка с запятой"), либо составным, тогда группа составляющих его операторов заключается в фигурные скобки. Примеры: while ( n++ < 100 ) printf(" %d %d \n",n,2*n+1); int far = 0, step = 2; while ( far < 1000 ) { far = far + step; printf(" far = %d\n", far); 12 } Не забудьте о том, что при построении цикла while вы должны включить в него какие-то конструкции, изменяющие величину проверяемого выражения так, чтобы в конце концов оно стало ложным. В противном случае выполнение цикла никогда не завершится. При организации цикла, когда его тело должно быть выполнено фиксированное число раз, осуществляются три операции: инициализация счетчика, сравнение его величины с некоторым граничным значением и увеличение значения счетчика при каждом прохождении тела цикла, причем инициализация счетчика для цикла while должна осуществиться до цикла (см. второй пример), о чем случайно можно забыть. 2.2 Оператор цикла for Структура оператора: for (инициализация; проверка условия; коррекция) оператор; Иниц.; Усл.; Корр. оператор условие коррекция нет да оператор инициализация Рисунок 7 В операторе for используются три выражения, управляющие работой цикла; они разделены символами "точка с запятой". Инициализирующее выражение вычисляется только один раз до начала выполнения какого-нибудь из операторов цикла. Если проверяемое выражение оказывается истинным (или не равным нулю), тело цикла выполняется один раз. Затем вычисляется величина корректируемого выражения, и значение проверяемого выражения определяется вновь. Таким образом, тело цикла выполняется до тех пор, пока проверяемое условие не станет ложным, или равным нулю. В виде блок-схемы порядок этих действий отображен на рисунке Ошибка! Источник ссылки не найден.. Оператор for – это цикл с предусловием: решение, выполнить в очередной раз тело цикла или нет, принимается до начала его прохождения. Поэтому может случиться так, что тело цикла не будет выполнено ни разу. Оператор, образующий тело цикла, может быть как простым, так и составным. Примеры: 13 for ( n=0; n < 10; n++) printf(" %d %d \n",n,2*n+1); В "инициализации" и "коррекции" могут находиться несколько операций, разделяемых между собой запятыми. Например: for (sum = 0.0, x = 1.0, count = 1; count <= 10; count++, x *= 2.0) { sum += 1.0/x; printf(" sum = %f ,когда count = %d\n", sum, count); } В заголовке цикла for ни одно из трех выражений не является обязательным, однако два символа "точка с запятой" обязательно должны присутствовать. Ниже приведено описание "вечного" цикла для ввода любого символа и вывода его и его кода на экран: char c; for ( ; ; ) { printf("Введите любой символ: "); scanf("%s",&c); printf("Симовол = %c; его код = %d\n", n, n); if ( c == 'q' ) break; // break – оператор выхода из цикла } Выход из цикла осуществляется, если введен символ 'q'. По-другому то же самое можно было записать так: char c='a'; for ( ; c != 'q'; ) { printf("Введите любой символ: "); scanf("%s",&c); printf("Симовол = %c; его код = %d\n", n, n); } Цикл for очень удобно использовать при работе с массивами. Пример: float g[10], f[10]; int i; for (i = 0; i < 10; i++) { printf("Введите %d-ый элемент массива: ", i); scanf("%f",&g[i]); printf("g[%d] = %f\n", i, g[i]); f[i] = 2 * g[i]; } Здесь организован ввод и вывод десяти элементов вещественного одномерного массива g и заполнение соответствующих элементов массива f по формуле f i = 2g i ВНИМАНИЕ!!! Как известно, символ ";" используется там, где соответствующий оператор ЗАКАНЧИВАЕТСЯ, поэтому фрагмент for (i = 0; i < 10; i++); // №1 { printf("Введите %d-ый элемент массива: ", i); // №2 scanf("%f",&g[i]); 14 printf("g[%d] = %f\n", , g[i]); f[i] = 2 * g[i]; } не является правильным: так как сразу после заголовка цикла (№1) стоит символ окончания оператора, то к моменту, когда начнёт выполняться оператор (№2), параметр i уже примет "плохое" значение 10, и повторений тела цикла никаких не будет (ведь собственно цикл уже закончился!!!). 2.3 Оператор цикла do while Структура оператора: do оператор while (выражение); выражение оператор нет да Рисунок 8 Оператор do while определяет действия, которые циклически выполняются до тех пор, пока проверяемое выражение не станет ложным, или равным нулю (рисунок Ошибка! Источник ссылки не найден.). Оператор do while – это цикл с постусловием; решением, выполнять или нет в очередной раз тело цикла, принимается после его прохождения. Поэтому тело цикла будет выполнено по крайней мере один раз. Оператор, образующий тело цикла, может быть как простым, так и составным. Пример 1: do{ printf("Введите любой символ: "); scanf("%s",&c); printf("Симовол = %c; его код = %d\n", n, n); } while ( c != 'q' ); В этом примере выполняется абсолютно то же самое, что и в приведенном выше для организации ввода символов. Пример 2: do{ printf("Введите количество строк в массиве (1..5): "); scanf("%d",&m); } while ( m<1 || m>5 ); Здесь в качестве "условия" проверяется значение, введенное в качестве количества строк матрицы. В случае истинности, что на самом деле означает, что число введено неправильное, количество строк запрашивается вновь. 15 2.4 Вложенные циклы Так как "оператор" во всех приведенных выше конструкциях может быть составным, то внутри него можно использовать и другой цикл, и операторы ветвления, и т.д. Вложенным называется цикл, находящийся внутри другого цикла (рисунок 9). in1=0; in1< m; in1=in1+1 Внешний цикл Вну тренний цикл Тело внешнего цикла Тело внутреннего (вложенно го) цикла in2=0; in2< n; in2=in2 +1 Рисунок 9 – Изображение на блок-схеме вложенных циклов При работе с двумерными массивами, для перебора всех элементов массива (например, он описан как double mm[razm1][razm2]), очень удобно пользоваться приведенной ниже конструкцией. Здесь цикл с параметром ind1 является внешним, в котором задается текущий номер строки в массиве mm, а цикл с параметром ind2 – внутренним, в котором задается текущий номер столбца. Таким образом, каждое сочетание ind1 и ind2 позволяет обратиться к каждому элементу массива: for (ind1=0; ind1 < razm1; ind1++) { for (ind2=0; ind2 < razm2; ind2++) { ... – операторы, использующие соответствующий элемент массива; например: mm[ind1][ind2] = Pi * (ind1+ind2); } } a = mm[ind1][ind2]; /* – неправильно, т.к. оба цикла уже закончились, и оба индекса уже приняли "плохое" значение. */ |