Сортировка массивов методом выбора

Массивы

Массив – совокупность элементов одинакового типа, объединённых общим именем; для доступа к элементам необходимо указать имя массива и один или несколько индексов, однозначно определяющих порядковый номер элемента в массиве. Количество индексов у элементов массива зависит от размерности массива – элементы одномерного массива (вектора) имеют по одному индексу, элементы двумерного массива (матрицы) – два индекса, можно использовать и массивы большей размерности.

Строка – одномерный массив, элементами которого являются символы.

В языке С++ с массивами и строками можно работать двумя способами:

1. использование стандартных языковых возможностей и встроенных средств компилятора для работы с массивами (встроенные массивы) – этот способ достался языку С++ в наследство от языка С и практически не изменился;

2. использование типов (классов, шаблонов), определённых в стандартной библиотеке С++ специально для обработки массивов и строк. Для работы с массивами различных типов рекомендуется использовать шаблонный класс vector (например, типы vector<int>, vector<double> и т.д.), для работы со строками (символьными массивами) имеется отдельный тип string (или wstring при использовании кодировки Unicode).

Оба способа имеют свои плюсы и минусы.

Формальное определение массива выглядит следующим образом:

тип_переменной название_массива [длина_массива]

После типа переменной идет название массива, а затем в квадратных скобках его размер. Например, определим массив из 4 чисел:

int numbers[4];

Данный массив имеет четыре числа, но все эти числа имеют неопределенное значение. Однако мы можем выполнить инициализацию и присвоить этим числам некоторые начальные значения через фигурные скобки:

int numbers[4] = {1,2,3,4};

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

int numbers[4] = {1, 2, 3, 4, 5, 6};

Здесь массив имеет размер 4, однако ему передается 6 значений.

Если размер массива не указан явно, то он выводится из количества инициализаторов:

int numbers[] = {1, 2, 3, 4, 5, 6};

В данном случае в массиве есть 6 элементов.

Свои особенности имеет инициализация символьных массивов. Можно передать символьному массиву как набор инициализаторов, так и строку:

char s1[] = {'h', 'e', 'l', 'l', 'o'};

char s2[] = "world";

Причем во втором случае массив s2 будет иметь не 5 элементов, а 6, поскольку при инициализации строкой в символьный массив автоматически добавляется нулевой символ '\0'.

При этом не допускается присвоение одному массиву другого массива:

int nums1[] = {1,2,3,4,5};

int nums2[] = nums1; // ошибка

nums2 = nums1; // ошибка

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

#include <iostream>

using namespace std;

int main()

{

int numbers[4] = {1,2,3,4};

int first_number = numbers[0];

cout << first_number << endl; // 1

numbers[0] = 34; // изменяем элемент

cout << numbers[0] << endl; // 34

return 0;

}

Число элементов массива также можно определять через константу:

const int n = 4;

int numbers[n] = {1,2,3,4};

Перебор массивов

Используя циклы, можно пробежаться по всему массиву и через индексы обратиться к его элементам:

#include <iostream>

using namespace std;

int main()

{

int numbers[4] = {1,2,3,4};

int size = sizeof(numbers)/sizeof(numbers[0]);

for(int i=0; i < size; i++)

cout << numbers[i] << endl;

return 0;

}

Чтобы пройтись по массиву в цикле, вначале надо найти длину массива. Для нахождения длины применяется оператор sizeof. По сути длина массива равна совокупной длине его элементов. Все элементы представляют один и тот же тип и занимают один и тот же размер в памяти. Поэтому с помощью выражения sizeof(numbers) находим длину всего массива в байтах, а с помощью выражения sizeof(numbers[0]) - длину одного элемента в байтах. Разделив два значения, можно получить количество элементов в массиве. А далее с помощью цикла for перебираем все элементы, пока счетчик i не станет равным длине массива. В итоге на консоль будут выведены все элементы массива:

Но также есть и еще одна форма цикла for, которая предназначена специально для работа с коллекциями, в том числе с массивами. Эта форма имеет следующее формальное определение:

for(тип переменная : коллекция)

{

инструкции;

}

Используем эту форму для перебора массива:

#include <iostream>

using namespace std;

int main()

{

int numbers[4] = {1,2,3,4};

for(int number : numbers)

std::cout << number << std::endl;

return 0;

}

При переборе массива каждый перебираемый элемент будет помещаться в переменную number, значение которой в цикле выводится на консоль.

Если нам неизвестен тип объектов в массиве, то можно использовать спецификатор auto для определения типа:

for(auto number : numbers)

std::cout << number << std::endl;

В следующем примере одномерный массив из n элементов (n<=10) заполняется случайными числами в интервале [-100, 100], попутно вычисляется максимальный элемент массива и его позиция в массиве.

Пример - заполняем массив случайными числами,

// находим наибольшее и его позицию (если несколько – позицию первого)

#include <iostream>

#include <ctime> // для инициализации датчика случайных чисел

using namespace std;

int main()

{ int n, i, c[10], c_max=-101, i_max=0;

srand(time(0));// начальная установка датчика случайных чисел

// при вводе размеров массива рекомендуем проверять правильность

do {cout<<"n=?"; cin>>n;} while (n>10||n<1);

for(int i=0;i<n;i++){

c[i]=rand()%201-100;// числа приводятся к интервалу [-100,100]

cout<<c[i]<<" ";

if (c[i]>c_max) {c_max=c[i]; i_max=i;}

}

cout<<endl<<"maximum "<<c_max<<" in position "<<i_max+1<<endl;

system("pause");

}

Далее уместно рассмотреть новый вид цикла for, введённый в С++ 11, который получил название for по диапазону. Его использование поясним на простом примере – программа выводит элементы заданного массива, используя непривычный синтаксис.

Пример – демонстрация цикла for по диапазону

#include <iostream>

using namespace std;

int main() {

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

for (int x : a) {

cout << x << " ";

}

return 0;

}

Сортировка массивов методом выбора

Сортировка массива — это процесс распределения всех элементов массива в определённом порядке.

Сортировка данных может сделать поиск внутри массива более эффективным не только для людей, но и для компьютеров. Например, рассмотрим случай, когда нам нужно узнать, отображается ли определённое имя в списке имён. Чтобы это узнать, нужно проверить каждый элемент массива на соответствие с нашим значением. Поиск в массиве с множеством элементов может оказаться слишком неэффективным (затратным).

Сортировка обычно выполняется путём повторного сравнения пар элементов массива и замены значений, если они отвечают определённым критериям. Порядок, в котором эти элементы сравниваются, зависит от того, какой алгоритм сортировки используется. Критерии состоят из того, как будет сортироваться массив (например, в порядке возрастания или в порядке убывания).

Чтобы поменять два элемента местами, можно использовать функцию swap() из стандартной библиотеки C++, которая определена в заголовочном файле algorithm. В C++11 swap() был перенесён в заголовочный файл utility:

#include <iostream>

#include <algorithm> // для std::swap. В C++11 используйте заголовок <utility>

using namespace std;

int main()

{

int a = 3;

int b = 5;

cout << "Before swap: a = " << a << ", b = " << b << '\n';

swap(a, b); // меняем местами значения переменных a и b

cout << "After swap: a = " << a << ", b = " << b << '\n';

}

Результат выполнения программы выше: