Работа с массивами. Методы сортировки (занятие 1)

1.

Работа с массивами. Методы сортировки.
Продолжающая
Занятие 1
13.02.23

2.

Массивы
Массив представляет набор однотипных данных. После типа переменной идет название
массива, а затем в квадратных скобках его размер. Например, определим массив из 10 чисел:
int arr[10] = { 9,7,2,7,0,8,3,1,6,5 };
Если размер массива не указан явно, то он выводится из количества инициализаторов:
int numbers[] = { 1, 2, 3, 4, 5, 6 };

3.

Инициализация символьных массивов имеет свои особенности . Мы можем передать
символьному массиву как набор инициализаторов, так и строку:
char s1[] = { 'h', 'e', 'l', 'l', 'o' };
char s2[] = "world";
Причем во втором случае массив s2 будет иметь не 5 элементов, а 6, поскольку при инициализации
строкой в символьный массив автоматически добавляется нулевой символ '\0’.
!Не допускается присвоение одному массиву другого массива
После определения массива мы можем обратиться к его отдельным элементам по индексу.
Индексы начинаются с нуля, поэтому для обращения к первому элементу необходимо
использовать индекс 0. Обратившись к элементу по индексу, мы можем получить его значение,
либо изменить его.
arr[0]

4.

Перебор массивов
Используя циклы, можно пробежаться по всему массиву и через индексы обратиться к его элементам:
int arr[] = { 9,7,2,7, 0, 8,3,1,6,5 };
for (int i = 0; i<=9; i++)
{
cout << arr[i] << '\t';
}
Чтобы пройтись по массиву в цикле, вначале надо найти длину массива. Для нахождения длины
применяется оператор sizeof.
Все элементы представляют один и тот же тип и занимают один и тот же размер в памяти. Поэтому с
помощью выражения sizeof(numbers) находим длину всего массива в байтах, а с помощью выражения
sizeof(numbers[0]) - длину одного элемента в байтах. Разделив два значения, можно получить количество
элементов в массиве.
int size = sizeof(numbers) / sizeof(numbers[0]);

5.

Также есть и еще одна форма цикла for, которая предназначена специально для работа с коллекциями, в
том числе с массивами. Эта форма имеет следующее формальное определение:
for (тип переменная : коллекция)
{
инструкции;
}
int numbers[4] = { 1,2,3,4 };
for (int number : numbers)
cout << number << endl;
При переборе массива каждый перебираемый элемент будет помещаться в переменную number,
значение которой в цикле выводится на консоль.
Если нам неизвестен тип объектов в массиве, то мы можем использовать спецификатор auto для
определения типа.

6.

Для удобства перестановки элементов массива можем воспользоваться функцией swap из стандартной
библиотеки С++.
swap( a,b)
#include <iostream>
using namespace std;
int main()
{
int a = 10;
int b = 20;
cout << "Value of a before: " << a << endl;
cout << "Value of b before: " << b << endl;
// swap values of the variables
swap(a, b);
cout << "Value of a now: " << a << endl;
cout << "Value of b now: " << b << endl;
return 0;
}
В результате получим:
Value of a before: 10 Value of b before: 20
Value of a now: 20 Value of b now: 10
https://www.geeksforgeeks.org/swap-in-cpp/

7.

Методы сортировки:
1. Сортировка пузырьком
2. Сортировка перемешиванием (улучшенная сортировка пузырьком)
3. Сортировка расческой (улучшенная сортировка пузырьком)
4. Сортировка вставками
5. Сортировка выбором

8.

Сортировка пузырьком
Сортировка пузырьком — один из самых известных алгоритмов
сортировки. Здесь нужно последовательно сравнивать значения
соседних элементов и менять числа местами, если предыдущее
оказывается больше последующего. Таким образом элементы с
большими значениями оказываются в конце списка, а с
меньшими остаются в начале.

9.

#include <iostream>
using namespace std;
int main()
{
int arr[] = { 9,7,2,7, 0, 8,3,1,6,5 };
int n = 9;
int t;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 9; j++) {
if (arr[j] > arr[j + 1]) {
int b = arr[j]; // создали дополнительную
переменную
arr[j] = arr[j + 1]; // меняем местами
arr[j + 1] = b; // значения элементов
}
}
}
for (int number:arr)
{
cout << number << '\t';
}
}

10.

Сортировка перемешиванием
(шейкерная сортировка)
Шейкерная сортировка отличается от пузырьковой тем, что
она двунаправленная: алгоритм перемещается не строго слева
направо, а сначала слева направо, затем справа налево.
Почитать про шейкерную сортировку:
https://purecodecpp.com/archives/1895
https://codelessons.ru/cplusplus/algoritmy/shej
ker-sortirovka-v-c-princip-raboty.html

11.

#include <iostream>
using namespace std;
int main()
{
const int n = 10;
int arr[n] = { 9,7,2,7, 0, 8,3,1,6,5 };
int right = n - 1; // n - размер массива
int left = 1;
while (left<=right)
{
for (int i = left; i <= right; i++) {
if (arr[i - 1] > arr[i]) {
swap(arr[i - 1], arr[i]);
}
}
right--;
for (int i = right; i >= left; i--) {
if (arr[i] < arr[i - 1]) {
swap(arr[i], arr[i - 1]);
}
}
left++;
} ;
for (int number:arr)
{
cout << number << '\t';
}

12.

Сортировка вставками
При сортировке вставками массив постепенно перебирается
слева направо. При этом каждый последующий элемент
размещается так, чтобы он оказался между ближайшими
элементами с минимальным и максимальным значением.
https://habr.com/ru/post/181271/

13.

#include <iostream>
using namespace std;
int main()
{
const int n = 10;
int arr[n] = { 9,7,2,7, 0, 8,3,1,6,5
};
for (int i = 1; i < n; i++)
for (int j = i; j > 0 && arr[j 1] > arr[j]; j--) // пока j>0 и элемент j1 > j, arr-массив int
swap(arr[j - 1], arr[j]);
// меняем местами элементы j и j-1
for (int number:arr)
{
cout << number << '\t';
}
}

14.

Сортировка выбором
Сначала нужно рассмотреть подмножество массива
и найти в нём максимум (или минимум). Затем
выбранное значение меняют местами со значением
первого неотсортированного элемента. Этот шаг нужно
повторять до тех пор, пока в массиве не закончатся
неотсортированные подмассивы.
https://purecodecpp.com/archives/2562

15.

include <iostream>
using namespace std;
int main()
{
const int n = 10;
int arr[n] = { 9,7,2,7, 0, 8,3,1,6,5
};
int min = 0;
for (int i = 0; i < n; i++)
{
min = i;
for (int j = i + 1; j < n; j++)
min = (arr[j] < arr[min]) ? j
: min;
if (i != min)
swap(arr[i], arr[min]);
}
for (int number:arr)
{
cout << number << '\t';
}
}

16.

Сортировка расческой
Сортировка расчёской — улучшение сортировки пузырьком. Её идея состоит в
том, чтобы «устранить» элементы с небольшими значения в конце массива,
которые замедляют работу алгоритма. Если при пузырьковой и шейкерной
сортировках при переборе массива сравниваются соседние элементы, то при
«расчёсывании» сначала берётся достаточно большое расстояние между
сравниваемыми значениями, а потом оно сужается вплоть до минимального.
Первоначальный разрыв нужно выбирать не случайным образом, а с учётом
специальной величины — фактора уменьшения, оптимальное значение которого
равно 1,247. Сначала расстояние между элементами будет равняться размеру
массива, поделённому на 1,247; на каждом последующем шаге расстояние будет
снова делиться на фактор уменьшения — и так до окончания работы алгоритма.
https://thecode.media/comb-sort/

17.

Домашнее задание:
Посмотреть в интернете методы сортировки, которых не было в сегодняшней
презентации. Выбрать самый оптимальный по вашему мнению, описать его преимущества,
почему выбрали именно его. И реализовать в массиве размером 10 или более элементов.