 |
Алгоритмы сортировки одномерных массивов
|
|
|
|
Лекция 9
Алгоритмы сортировки одномерных массивов
Цели:
ü познакомиться с некоторыми алгоритмами сортировки массивов и разработки соответствующего проекта в среде Visual C++ 6. 0.
1. Сортировка одномерных массивов
Под сортировкой понимается упорядочение элементов некоторой последовательности в нужном порядке (убывания или возрастания). Существует достаточно много алгоритмов сортировок послед-овательностей. Но мы остановимся только на трёх, наиболее простых.
1. 1. Метод пузырька (метод обменной сортировкой с выбором)
Идея метода отражена в его названии. Шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то они меняются местами. При этом самые «легкие» (наименьшие) элементы массива «всплывают» наверх, а самые «тяжелые» – «тонут». Алгоритмически это можно реализовать следующим образом. Весь массив просматривается снизу вверх, стоящие рядом элементы меняются в том случае, если «нижний» элемент меньше, чем «верхний». Таким образом, наверх «всплывет» самый «легкий» элемент всего массива. Так нужно повторять для оставшихся неотсортированными N-1 элементов (т. е. для тех, которые лежат «ниже» первого) и т. д. Алгоритм достаточно прост:
| Алгоритм (в порядке возрастания) | Программа |
| объявление вещ: t[10], x, цел: i, j, k, flag для i=0 до 10-1 шаг 1 ввод t[i] все_для i для i=10-1 до 1 шаг -1 //обмена не было flag=0 для j=0 до i-1 шаг 1 если t[j]> t[j+1] //меняем местами два соседних //элемента x=t[j] t[j]=t[j+1] t[j+1]=x //обмен состоялся flag=1 все_если все_для j если flag==0 выход из цикла по i // не было // обмена все_если все_для i для i=0 до 10-1 шаг 1 вывод t[i] все_для i | #include " stdio. h" #include " math. h" #define N 10 int main ( ) { float t[N], x; int i, j, k, flag; // ввод массива t с клавиатуры for ( i=0; i< =N-1; i++ ) { printf (" x[%i]= " , i ); scanf (" %f", & t[i]); } for ( i=N-1; i> =1; i-- ) { //обмена не было flag=0; for ( j=0; j< =i-1; j++ ) { if (t[j]> t[j+1]) { // элементы меняются // местами x=t[j]; t[j]=t[j+1]; t[j+1]=x; //обмен состоялся flag=1; } } if(flag= =0) //если обмена не было, то нужно //выйти из цикла break; } // вывод массива t на экран for (i=0; i< =N-1; i++) printf (" %. 3f ", t[i]); printf (" \n" ); return 1; } |
1. 2. Сортировка выбором
|
|
|
При сортировке этим методом при просмотре массива ищется наименьший элемент, сравнивая его с первым. Если такой элемент найден, но меняется местами с первым. Затем эти действия повторяются, но не с первого элемента, а со второго. Так продолжается до тех пор, пока не будет отсортирован весь массив:
| Алгоритм (в порядке возрастания) | Программа |
| объявление вещ: t[10], x, цел: i, j, k для i=0 до 10-1 шаг 1 ввод t[i] все_для i для i=0 до 10-1 шаг 1 k=i x=t[i] для j=i+1 до 10-1 шаг 1 если t[j]< x // меняем местами два // элемента x=t[j] k=j все_если t[k]=t[i] t[i]=x все_для j все_для i для i=0 до 10-1 шаг 1 вывод t[i] все_для i | #include “stdio. h” #include “math. h” #define N 10 int main() { float t[N], x; int i, j, k; //ввод массива с клавиатуры for(i=0; i< =N-1; i++) { printf(" t[%i]=", i); scanf(" %f", & t[i]); } // сортировка массива for(i=0; i< =N-1; i++) { k=i; x=t[i]; for(j=i+1; j< =N-1; j++) //находятся элементы, которые //нужно поменять местами if(t[j]< x) { k=j; x=t[j]; } //найденные элементы меняются //местами t[k]=t[i]; t[i] = x; } for( i=0; i < =N-1; i++) { printf(" %. 3f ", t[i]); } return 1; } |
1. 3. Сортировка простыми вставками
|
|
|
Сортировка простыми вставками в чем-то похожа на вышеизложенные методы. Аналогичным образом делаются проходы по части массива и в его начале " вырастает" отсортированная последовательность.
| Алгоритм (в порядке возрастания) | Программа |
| объявление вещ: t[10], x, цел: i, j для i=0 до 10-1 шаг 1 ввод t[i] все_для i для i=0 до 10-1 шаг 1 x=t[i] // поиск позиции элемента, меньшего x // в последовательности для j=i-1 до 0 и t[j]> х шаг -1 //сдвигаем элемент вправо, пока не //нашли меньший, чем x t[j+l] =t[j]; // позиция меньшего элемента // найдена //меняем элемент t[j+l] = х; все_для j все_для i для i=0 до 10-1 шаг 1 вывод t[i] все_для i | #include " stdio. h" #define N 10 int main() { float t[10], x; int j, i; for( i=0; i< =N-1; i++) { printf(" t[%i]=", i); scanf(" %f", & t[i]); } for ( i=0; i < =N-1; i++) { x = t[i]; for ( j=i-1; j> =0 & & t[j] > x; j--) t[j+1] = t[j]; t[j+1] = x; } for( i=0; i < =N-1; i++) { printf(" %. 3f ", t[i]); } printf (" \n" ); return 1; } |
Лекция 10
Двухмерные массивы
Цели:
ü познакомиться с понятием двухмерного массива и способом его объявления;
ü освоить методику написания алгоритмов с использованием двухмерных массивов, перевода таких алгоритмов на язык программирования С++ и разработки соответствующего проекта в среде Visual C++ 6. 0.
1. Двухмерные массивы
В соответствии с синтаксисом С++ в языке существуют только одномерные массивы, однако элементами массива могут быть массивы, поэтому двухмерный массив определяется как массив массивов.
Объявление двухмерного массива заключается в последовательной записи типа элементов массива, имени массива и двух измерений. При этом в квадратных скобках, соответствующих каждому измерению, указывается количество элементов в данном измерении:
|
|
|
float B[3][2];
В данном примере каждый элемент массива будет вещественным числом, B – имя массива, число в первых квадратных скобках указывает количество строк, а число во вторых квадратных скобках – количество столбцов массива. С точки зрения математических определений, массив B – матрица, состоящая из трех строк и двух столбцов.
При объявлении массива можно инициализировать значения элементов каждого измерения, например:
float f[][]={{2. 5, 5}, {7. 895, 56}};
В этом случае будет создан вещественный массив, содержащий две строки и два столбца. Для обращения к конкретному элементу двухмерного массива необходимо записать имя массива и в двух квадратных скобках последовательно указать индексы элемента массива.
В оперативной памяти элементы массива располагаются так, что при переходе от элемента к элементу наиболее быстро меняется самый правый индекс массива. Если объявлен массив из m строк и n столбцов, то его элементы располагаются в оперативной памяти так, как показано на рис. 7.
При работе с двухмерными массивами следует учесть, что при переходе от элемента к элементу нужно будет менять номер строки и/или номер столбца. В отличие от работы с одномерными массивами решение задач с двухмерными массивами требует организации двух циклов: один для изменения номера столбца, другой для изменения номера строки.
Опишем в виде алгоритма и программы отдельно ввод двухмерного массива с клавиатуры и его вывод на экран:
| Алгоритм | Программа |
| объявление вещ: а[4][5], цел: i, j // ввод массива построчно для i=0 до 4-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j // столбца массива // затем элемент вводится с //клавиатуры ввод а[i][j] все_для j все_для i … //обработка массива //решение задачи … // вывод массива построчно для i=0 до 4-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j // столбца массива // затем элемент выводится на //экран вывод а[i][j] все_для j все_для i | #include " stdio. h" #define n 4 #define m 5 int main() { int a[n][m], i, j; for(i=0; i< =n-1; i++) { for (j=0; j< =m-1; j++) { printf (" a[%i][%i]=", i, j); scanf (" %i", & a[i][j]); } } … //обработка массива //решение задачи … for (i=0; i< =n-1; i++) { //вывод строки с номером i for (j=0; j< =m-1; j++) printf (" %i ", a[i][j]); //перевод курсора на другую //строку printf (" \n" ); } return 1; } |
|
|
|
Среди задач, связанных с использованием двухмерных массивов, особое место занимают задачи на формирование массивов, содержащих одинаковое количество строк и столбцов. Такие массивы можно сравнить с квадратными матрицами. Расположение элементов в матрицах определяется, как правило, относительно главной и побочной диагоналей (элементы главной диагонали располагаются на линии, идущей из верхнего левого в правый нижний угол матрицы, а элементы побочной диагонали – на линии, идущей из верхнего правого в левый нижний угол матрицы). Определить такое расположение можно следующим образом.
Элемент расположен:
Ø на главной диагонали, если i=j;
Ø ниже главной диагонали, если i> j;
Ø выше главной диагонали, если i< j;
Ø на побочной диагонали, если i=n-j-1;
Ø ниже побочной диагонали, если i> n-j-1;
Ø выше побочной диагонали, если i< n-j-1,
где i – номер строки, j – номер столбца в матрице размера 
(n – количество строк (столбцов) в матрице).
Закон, по которому формируется каждый элемент массива либо задается, либо его необходимо выявить из заданного образца матрицы.
Пример 1 . Получить квадратную матрицу порядка n по заданному образцу:
Ход выполнения работы
1. При решении таких задач необходимо выявить закон получения каждого элемента массива. Как правило, значение элемента зависит от номера строки и/или номера столбца. В данной задаче можно увидеть, что в нулевой строке элементы равны номеру столбца плюс 1. С увеличением номера строки на 1 элемент массива увеличивается на число n, а с увеличением номера столбца элемент увеличивается на 1. Из этого сделаем предположение, что элементы массива формируются по закону:
2. Написать программу, соответствующую алгоритму:
| Алгоритм | Программа |
| объявление цел: а[4][4], цел: i, j // формирование массива построчно для i=0 до 4-1 шаг 1 // в цикле изменяется номер i // строки массива для j=0 до 4-1 шаг 1 // в цикле изменяется номер j //столбца массива // затем элемент формируется по //закону а[i][j]=i*n+j+1 все_для j все_для i // вывод массива построчно для i=0 до 4-1 шаг 1 // в цикле изменяется номер i // строки массива для j=0 до 4-1 шаг 1 // в цикле изменяется номер j // столбца массива // затем этот элемент выводится // на экран вывод а[i][j] все_для j все_для i | #include " stdio. h" #define n 4 int main() { int a[n][n], i, j; // формирование массива построчно for(i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) { a[i][j]=i*n+j+1; } } // вывод массива построчно for (i=0; i< =n-1; i++) { // вывод элементов текущей // строки for (j=0; j< =n-1; j++) printf (" %i ", a[i][j]); // перевод курсора на новую // строку printf (" \n" ); } return 1; } |
3. Создать проект и реализовать данную задачу в среде Visual C++ 6. 0.
|
|
|
Пример 2. Получить квадратную матрицу порядка n по заданному образцу:
Ход выполнения работы
1. В этой задаче элементами массива являются 0 и 1. Значения элементов зависят от их месторасположения. Если элемент находится на главной, побочной диагонали или одновременно выше главной и ниже побочной диагонали, то его значение равно 1. В противном случае элемент массива принимает значение 0.
2. Написать программу, соответствующую алгоритму:
| Алгоритм | Программа |
| объявление цел: а[7][7], цел: i, j // формирование массива построчно для i=0 до 7-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 7-1 шаг 1 // в цикле изменяется номер j // столбца массива // затем элемент формируется по // закону если i=j или i=n-j-1 или (i< j и i> n-j-1) а[i][j]=1 иначе а[i][j]=0 все_если все_для j все_для i // вывод массива построчно для i=0 до 7-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 7-1 шаг 1 // в цикле изменяется номер j // столбца массива // затем этот элемент выводится // на экран вывод а[i][j] все_для j все_для i | #include " stdio. h" #define n 7 int main() { int a[n][n], i, j; // формирование массива построчно for(i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) { if(i==j || i==n-j-1 || (i< j & & i> n-j-1)) a[i][j]=1; else a[i][j]=0; } } // вывод массива построчно for (i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) printf (" %i ", a[i][j]); printf (" \n" ); } return 1; } |
3. Создать проект и реализовать данную задачу в среде Visual C++ 6. 0.
Пример 3. Дана квадратная матрица размера . Вычислить произведение элементов, кратных 3 и расположенных выше главной и ниже побочной диагоналей.
Ход выполнения работы
1. Алгоритм решения данной задачи аналогичен алгоритму предыдущей. Если в примере 2 элемент формируется при выполнении некоторого условия, то в данной задаче элемент массива, удовлетворяющий заданному условию, участвует в формировании произведения.
2. Написать программу, соответствующую алгоритму:
| Алгоритм | Программа |
| объявление вещ: а[5][5], p, цел: i, j // ввод массива построчно для i=0 до 5-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j //столбца массива // затем элемент вводится ввод а[i][j] все_для j все_для i // вычисление произведения p=1 для i=0 до 5-1 шаг 1 // в цикле изменяется номер i строки //массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j //столбца массива если i< j и i< n-j-1 и остаток от дел a[i][j] на 3 =0 p=p*a[i][j] все_если все_для j все_для i печать p // вывод массива построчно для i=0 до 5-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j //столбца массива // затем этот элемент выводится на //экран вывод а[i][j] все_для j все_для i | #include " stdio. h" #include " math. h" #define n 5 int main() { float a[n][n], p; int i, j; // ввод массива построчно for(i=0; i< =n-1; i++) { // ввод элементов текущей строки for (j=0; j< =n-1; j++) { printf (" a[%i][%i]=", i, j); scanf (" %f", & a[i][j]); } } // вычисление произведения p=1; for(i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) { if(i< j & & i> n-j-1 & & fmod(a[i][j], 3)==0) p=p*a[i][j]; } } printf (" P=%f\n", p); for (i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) printf (" %. 2f ", a[i][j]); printf (" \n" ); } return 1; } |
Примечание. В программе нужно было найти остаток от деления элемента массива на 3. Так как элементами массива являются вещественные числа, то используется математическая функция fmod(), которая применяется для вычисления остатка от деления вещественных переменных.
3. Создать проект и реализовать данную задачу в среде Visual C++ 6. 0.
Пример 4. Дана матрица размера . Найти минимальный элемент, расположенный выше главной диагонали, поменять его местами с элементом, расположенным верхнем левом углу матрицы.
Ход выполнения работы
1. Алгоритм решения данной задачи аналогичен алгоритму предыдущей. Надо пройтись по всем элементам матрицы, расположенным выше главной диагонали, и найти среди них наименьший и запомнить его позиции. Затем осуществить обмен соответствующих элементов.
2. Написать программу, соответствующую алгоритму:
| Алгоритм | Программа |
| объявление вещ: а[5][5], p, min; цел: i, j, imin, jmin // ввод массива построчно для i=0 до 5-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j //столбца массива // затем элемент вводится ввод а[i][j] все_для j все_для i // нахождение минимального элемента и //его позиций min=a[0][0], imin=0, jmin=0 для i=0 до 5-1 шаг 1 // в цикле изменяется номер i строки //массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j //столбца массива если i< j и min> a[i][j] min=a[i][j] imin=i jmin=j все_если все_для j все_для i //меняются местами элементы p =a[0][0] a[0][0]= a[imin][jmin] a[imin][jmin]=p // вывод массива построчно для i=0 до 5-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j // столбца массива // затем этот элемент выводится на //экран вывод а[i][j] все_для j все_для i | #include " stdio. h" #include " math. h" #define n 5 int main() { float a[n][n], p; int i, j; // ввод массива построчно for(i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) { printf (" a[%i][%i]=", i, j); scanf (" %f", & a[i][j]); } } // нахождение минимального элемента и // его позиций min=a[0][0], imin=0, jmin=0; for(i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) { if(i< j & & min> a[i][j]) { min=a[i][j]; imin=i; jmin=j; } } } //меняются местами элементы p=a[0][0]; a[0][0]=a[imin][jmin]; a[imin][jmin]=p; // вывод массива построчно for (i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) printf (" %. 2f ", a[i][j]); printf (" \n" ); } return 1; } |
3. Создать проект и реализовать данную задачу в среде Visual C++ 6. 0.
Пример 5. Дан двухмерный массив. Отсортировать в порядке возрастания каждую строку двумерного массива.
Ход выполнения работы
1. Так как каждая строка двухмерного массива является одномерным массивом, то нужно применить алгоритм сортировки одномерного массива к каждой строке.
2. Написать программу, соответствующую алгоритму:
| Алгоритм | Программа |
| объявление вещ: а[5][5], x, цел: i, j, k, flag // ввод массива построчно для i=0 до 5-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j // столбца массива // затем элемент вводится ввод а[i][j] все_для j все_для i // сортируем строки для i=0 до 5-1 шаг 1 // в цикле изменяется номер строки //массива i для j=5-1 до 1 шаг -1 flag=0 //обмена не было для k=0 до j-1 шаг 1 если a[i][k]> a[i][k+1] // меняем местами два //соседних элемента x=a[i][k] a[i][k]=a[i][k+1] a[i][k+1]=x flag=1 //обмен состоялся все_если все_для k если flag=0 выход из цикла по j // не было // обмена все_для j все_для i // вывод массива построчно для i=0 до 5-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 5-1 шаг 1 // в цикле изменяется номер j //столбца массива // затем этот элемент выводится на // экран вывод а[i][j] все_для j все_для i | #include " stdio. h" #include " math. h" #define n 5 int main() { float a[n][n], x; int i, j, k, flag; for(i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) { printf (" a[%i][%i]=", i, j); scanf (" %f", & a[i][j]); } } // сортируем строки for(i=0; i< =n-1; i++) { //сортируется i–я строка for (j=n-1; j> =1; j--) { flag=0; for ( k=0; k< =j-1; k++ ) { if (a[i][k]> a[i][k+1]) { x= a[i][k]; a[i][k]=a[i][k+1]; a[i][k+1]=x; flag=1; } } if(flag==0) break; } } // вывод массива построчно for (i=0; i< =n-1; i++) { for (j=0; j< =n-1; j++) printf (" %. 2f ", a[i][j]); printf (" \n" ); } return 1; } |
3. Создать проект и реализовать данную задачу в среде Visual C++ 6. 0.
Пример 6. Дан двухмерный массив размера 
. Сформировать одномерный массив, каждый элемент которого – произведение нечетных элементов соответствующего столбца двухмерного массива. Указать номер столбца с наименьшим произведением элементов.
Ход выполнения работы
1. Решение задачи можно представить в виде схемы:
 |
Как видим, алгоритм будет состоять из трёх основных этапов: 1) находим произведение нечетных элементов j-го столбца исходного двухмерного массива; 2) записываем найденное произведение в соответствующий j-й элемент одномерного массива (сформированный массив будет содержать ровно столько элементов, сколько столбцов в исходном двухмерном массиве); 3) поиск минимального элемента и его номера в сформированном одномерном массиве.
2. Написать программу, соответствующую алгоритму:
| Алгоритм | Программа |
| объявление вещ: а[6][4], p, b[4], цел: i, j, pmin // ввод массива построчно для i=0 до 6-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 4-1 шаг 1 // в цикле изменяется номер j //столбца массива // затем элемент вводится ввод а[i][j] все_для j все_для i // вычисление произведений для j=0 до 4-1 шаг 1 // в цикле изменяется номер j столбца // массива // находим произведение j-го столбца p=1 для i=0 до 6-1 шаг 1 // в цикле изменяется номер i // строки массива //находим нечетный элемент если остаток от дел a[i][j] на 2 =1 //изменяем произведение p=p*a[i][j] все_если все_для j b[j]=p все_для i // находим минимальный элемент массива // b p=b[0] // номер минимального элемента pmin=0 для i=1 до 4-1 шаг 1 если p< b[i] p=b[i] pmin=i все_если все_для i // вывод массива a построчно для i=0 до 6-1 шаг 1 // в цикле изменяется номер i строки // массива для j=0 до 4-1 шаг 1 // в цикле изменяется номер j // столбца массива // затем этот элемент выводится на // экран вывод а[i][j] все_для j все_для i // вывод массива b для i=0 до 4-1 шаг 1 вывод b[i] все_для i печать pmin | #include " stdio. h" #include " math. h" #define n 6 #define m 4 int main() { float a[n][m], p, b[m]; int i, j, pmin; // ввод массива построчно for(i=0; i< =n-1; i++) { for (j=0; j< =m-1; j++) { printf (" a[%i][%i]=", i, j); scanf (" %f", & a[i][j]); } } // вычисление произведений for(j=0; j< =m-1; j++) { // вычисление произведения // элементов // текущего столбца p=1; for (i=0; i< =n-1; i++) { if(fmod(a[i][j], 2)==1) p=p*a[i][j]; } // запись найденного // произведения в массив b b[j]=p; } //находим минимальный элемент //массива b p=b[0]; pmin=0; for (i=0; i< =m-1; i++) { if(p> b[i]) { p=b[i]; pmin=i; } } // вывод массива a построчно for (i=0; i< =n-1; i++) { for (j=0; j< =m-1; j++) printf (" %. 2f ", a[i][j]); printf (" \n" ); } printf (" \n" ); // вывод массива b for (i=0; i< =m-1; i++) { printf (" %. 2f ", b[i]); } printf (" \n" ); printf (" №min=%i\n", pmin); return 1; } |
Примечание. При нахождении произведений нечетных элементов каждого столбца можно было обойтись без переменной p, для чего нужно сделать замены:
| Операторы в программе | Замена |
| p=1; | b[j]=1; |
| p=p*a[i][j]; | b[j]=b[j]*a[i][j]; |
| b[j]=p; | вместо этого оператора пустая строка |
3. Создать проект и реализовать данную задачу в среде Visual C++ 6. 0.
|
|
|
