Перестановки

1.

Перестановки
Задачи с перестановками — это задачи, в которых какие-либо элементы массива или
переменные меняются своими значениями. Тема перестановок рассматривается на
примерах.
Пример. Задать с клавиатуры две переменные (a, b) и поменять их значения
местами. Вывести на экран чему равны эти переменные до и после изменений.
int a = 0, b = 0;
scanf("%d %d", &a, &b);
printf("a = %d, b = %d\n", a, b);
int temp = a;
a = b;
b = temp;
printf("a = %d, b = %d\n", a, b);
Для решения этой задачи нужно использовать дополнительную переменную, которая
позволит временно хранить значение одной из переменных. Если не использовать
дополнительную переменную
a = b;
b = a;
то уже в первой строчке безвозвратно теряется значение переменой a.
Пример. Задать с клавиатуры четыре переменные (a, b, c, d) и циклически
поменять их значения местами (a → b, b → c, c → d, d → a). Вывести на
экран чему равны эти переменные до и после изменений.
int a = 0, b = 0, c = 0, d = 0;
scanf("%d %d %d %d", &a, &b, &c, &d);
printf("a = %d, b = %d, c = %d, d = %d\n", a, b, c, d);
int temp = a;
a = d;
d = c;
c = b;
b = temp;
printf("a = %d, b = %d, c = %d, d = %d\n", a, b, c, d);

2.

При увеличении количества переменных, которые участвуют в обмене значениями,
принцип обмена остается таким же.
Принцип последовательного обмена схематично представлен на Рисунке 1.
Рисунок 1. Принцип обмена переменных значениями
Пример. Поменять местами первую и вторую строки двумерного массива.
#define N 4
#define M 5
int i = 0, j = 0, temp = 0;
int arr[N][M] = {{0}};
for (i = 0; i < N; i++)
for (j = 0; j < M; j++)
arr[i][j] = -9 + rand() % 19;
// цикл обмена значениями
for (j = 0; j < M; j++) {
temp = arr[0][j];
arr[0][j] = arr[1][j];
arr[1][j] = temp;
}
Пример. Поменять местами 1ю строку и 5й столбец массива arr[N][N].
// цикл обмена 1й строки на 5й столбец
for (i = 0; i < N; i++) {
temp = arr[0][i];
arr[0][i] = arr[i][4];
arr[i][4] = temp;
}

3.

Для того чтобы произвести обмен значений нужно определить какие элементы нужно
обменять.
arr[0][0]
arr[0][4]
arr[0][1]
arr[1][4]
arr[0][2]
arr[2][4]
arr[0][3]
arr[3][4]
-------------------------------arr[0][N -1]
arr[N - 1][4]
Можно заметить, что индекс столбца в левой колонке меняется так же, как и индекс
строки в правой колонке. Поэтому общей формулой можно записать:
arr[0][i]
arr[i][4]
Пример. Поменять местами
arr[N][N].
средний столбец и главную диагональ массива
// цикл обмена среднего столбца и главной диагонали
for (i = 0; i < N; i++) {
temp = arr[i][N / 2];
arr[i][N / 2] = arr[i][i];
arr[i][i] = temp;
}
Здесь:
arr[1][N / 2]
arr[0][0]
arr[2][N / 2]
arr[1][1]
arr[3][N / 2]
arr[2][2]
arr[4][N / 2]
arr[3][3]
----------------------------------------arr[N - 1][ N / 2]
Общая формула:
arr[N - 1][ N - 1]
arr[i][N / 2]
arr[i][i]

4.

Пример. Переставить в начало одномерного массива все его положительные
элементы.
#define N 25
int arr[N] = {0}, i = 0;
int temp = 0, h = 0;
for (i = 0, h = 0; i < N; i++) {
if (arr[i] > 0){
temp = arr[i];
arr[i] = arr[h];
arr[h] = temp;
h++;
}
}
Вводим переменную h которая будет отвечать за то, куда мы будем переставлять
положительные элементы. Изначально это будет начало массива (h = 0), но после
каждой перестановки h будет увеличиваться на единицу.

5.

Сортировка одномерного массива.
Метод простого выбора.
Метод заключается в последовательном нахождении минимального или
максимального элемента (в зависимости от того сортируем ли мы массив по
возрастанию или по убыванию) и перестановке его в начало массива.
for (k = 0; k < N - 1; k++) {
// нахождение индекса минимального элемента
ind_max = k;
for (i = 1 + k; i < N; i++)
if (arr[i] > arr[ind_max])
ind_max = i;
// обмен элементов
temp = arr[k];
arr[k] = arr[ind_max];
arr[ind_max] = temp;
}
ind_max – индекс текущего максимального элемента;
k – индекс элемента, который обменивается с максимальным элементом.
На первом шаге мы должны поставить максимальный элемент всего массива на место
1го элемента. То есть поменять arr[0] и arr[ind_max]. Далее мы ищем
новый максимальный элемент в хвостовой части массива (не учитывая arr[0]) и
меняем его местами со вторым элементом массива. То есть меняем arr[1] и
arr[ind_max]. Далее снова ищем максимальный элемент в хвостовой части
массива (не учитывая arr[0] и arr[1]) и меняем его с третьим элементом. То
есть меняем arr[2] и arr[ind_max]. Далее продолжаем находить
максимальные элементы из хвостовой не отсортированной части массива и менять их
с первым не отсортированным элементом пока не достигнем предпоследнего
элемента.

6.

Метод пузырька.
Сортировка методом пузырька предполагает многократное прохождение по массиву и
обмен рядомстоящих элементов массива в том случае, если эти элементы стоят в
неверном порядке.
В нашем случае, переменная count будет отвечать за количество обменов,
совершенных при прохождении вдоль массива. Эта переменная обнуляется, затем
происходит обход массива. Если во время обхода был сделан хотя бы один обмен
элементов местами, то count снова обнуляют и повторяют обход. Если же
переменная после обхода массива осталась равной нулю, то значит, массив уже
отсортирован.
int count = 1; //переменная для подсчета количества обменов
while (count > 0) {
//обнуление количества обменов
count = 0;
//прохождение по массиву
for (i = 0; i < N - 1; i++) {
if(arr[i] > arr[i + 1]) {
//обмен элементов
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
//подсчет количества обменов
count++;
}
}
}