Алгоритмические языки и программирование

Часть 1

Алгоритмы сортировки массивов
Сортировка (sorting — классификация, упорядочение) — последовательное расположение на группы чего-либо в зависимости от выбранного критерия (по возрастанию, по убыванию, не возрастанию, не убыванию).

Формулировка задачи:
Дан массив целых чисел размером в n элементов. Необходимо отсортировать массив по возрастанию.
Алгоритмы сортировки массивов

Для решения данной задачи будем составлять различные реализации функции Sort(int * mas, int n).
Разберем следующие алгоритмы:
Сортировка выбором
Сортировка пузырьком (см. ранее)
Сортировка вставками
Алгоритмы сортировки массивов

Сортировка выбором
Алгоритм сортировки выбором:
На первом проходе цикла выбирается минимальный элемент из текущей последовательности и меняется местами с первым элементом последовательности.
На следующей итерации цикла поиск минимального элемента осуществляется со второй позиции, после меняется местами найденный минимальный элемент со вторым в списке.
Такую процедуру выполняем до конца массива, пока он весь не будет отсортирован.

Сортировка выбором (Selection sort)
void Sort(int * mas, int n){
int i;
for(i = 0; i < (n-1); i++){
int min_i = i; /*номер текущего меньшего элемента из неотсортированных*/
int j;
for(j = (i+1); j < n; j++){
if(mas[j] < mas[min_i])
min_i = j;
}
/* меньший элемент другой, из неотсортированной части
поменять местами*/
if(min_i != i){
int buf = mas[i];
mas[i] = mas[min_i];
mas[min_i] = buf;
}
}
}

Сортировка вставками
Сортировка вставками — достаточно простой алгоритм.
Алгоритм сортировки вставками, состоит из 3 простых шагов:
1. Ищем в нашей последовательности данных минимальный элемент.
2. Перемещаем найденный элемент на первое место, остальные элементы сдвигаем вправо.
3. Теперь уже среди N-1 элемента ищем минимальный и проделываем такие же действия.

void Sort(int *mas, int n) // сортировка вставками
{
int i;
int buf, // временная переменная для хранения значения элемента сортируемого массива
item; // индекс предыдущего элемента
for (i= 1; i < n; i++){
buf = mas[i];
item = i-1;
while(item >= 0 && mas[item] > buf){
mas[item + 1] = mas[item];
mas[item] = buf;
item--;
}
}
}
// пока индекс не равен 0 и предыдущий элемент массива больше текущего
Cортировка вставками
(Insertion sort)

Лабораторные работы