Сортировка массивов
Занесенные в массив данные часто нужно отсортировать по возрастанию или убыванию. Например, в школьном журнале фамилии и имена учащихся отсортированы по алфавиту от «А» до «Я».
Существует несколько алгоритмов сортировки массивов, но мы рассмотрим самый простой из них, который называется сортировкой выбором (Selection Sort).
Суть данного алгоритма заключается в следующем: Сначала мы во всем массиве ищем самый большой элемент и меняем его местами с самым последним элементом массива. Далее мы ищем самый большой элемент в оставшейся части массива (без последнего элемента) и ставим его с предпоследним элементом массива. Далее мы снова ищем максимальный элемент в массиве без последних двух элементов и меняем его с 3-м элементом с конца и так далее, пока весь массив не будет отсортирован.
На рисунке представлен вариант сортировки для массива с 5-ю элементами:
Данный алгоритм хорошо работает для небольших массивов. Однако, если в массиве несколько сотен или даже тысяч элементов, сортировка будет проходить слишком медленно, так как, если в массиве n элементов, количество итераций цикла (N) составит:
Таким образом, если в массиве 1000 элементов, то количество итераций составит:
Если же в массиве 10 000 элементов, то количество итераций увеличится до 50 004 999. Сортировка такого массива займет очень много времени.
Напишем программу, которая будет запрашивать у нас элементы массива, затем отсортирует его и выведет на экран.
Скачайте эту программу, поместите скачанный файл SORT.CPP в папку C:\TCPP\BIN\.
Запустите DOSBox (Как настроить эту программу можно посмотреть ЗДЕСЬ).
Нажмите клавишу F3. Выберите файл SORT.CPP и нажмите клавишу Enter.
На экране появится текст программы:
Рассмотрим эту программу подробнее:
#include<iostream.h>
#include<conio.h> - подключаем два необходимых для работы программы модуля.
void main(){
clrscr(); - Очищаем экран.
int a[10]; - создаем массив с именем a, состоящий из 10 элементов типа int.
for(int i=0;i<10;i++){ - в данном цикле переменная i проходит последовательно значения от 0 до 9. (Подробнее о цикле for можно посмотреть ЗДЕСЬ)
cout<<"Введите "<<i+1<<"-й элемент массива: "; - на каждом шаге цикла программа предлагает ввести соответствующий элемент массива. Мы прибавили к переменной i единицу для того, чтобы сделать нумерацию более «человеческой» (Напоминаю, что в C++ отсчет ведется от 0, а люди считают с единицы: первый, второй и т.д.).
cin>>a[i]; - вводим с клавиатуры число. После нажатия на клавишу Enter, введенное число записывается в соответствующий элемент массива a.
} – конец цикла for.
clrscr(); - очищаем экран
cout<<"Массив до сортировки:\n"; - выводим надпись.
for(i=0;i<10;i++) cout<<a[i]<<" "; - выводим 10 элементов массива до его сортировки.
int N=9,nn,m; - создаем 3 вспомогательные переменные. В переменной N хранится номер ячейки массива a, до которого нужно осуществлять поиск максимального элемента массива. Изначально N равно 9, т.е. номеру последнего элемента массива – сначала будем искать во всем массиве. В переменную nn будем заносить индекс (номер) максимального элемента массива. Переменная m нам понадобится для временного сохранения чисел при перестановки ячеек массива.
while (N>0){ -цикл while. Пока номер последнего элемента массива, до которого ведется поиск, больше нуля (т.е. есть как минимум два элемента массива, среди которых нужно выполнять поиск) будем сортировать (выполнять следующие команды). Подробнее о цикле while можно прочитать ЗДЕСЬ.
int max=-32768; - в переменной max будем хранить найденный на максимальный элемент. Изначально приравниваем переменной max самое маленькое возможное значение.
for (i=0;i<=N;i++){ - «проходим» массиву от 0-го элемента до элемента с номером N.
if (a[i]>max){ - если текущий элемент массива больше значения, хранимого в переменной max, то выполняем следующие действия (подробнее об операторе if можно посмотреть ЗДЕСЬ):
max=a[i]; - приравниваем переменной max значение текущего элемента массива.
nn=i; - сохраняем номер текущего элемента массива в переменной nn.
} – конец оператора if.
} – конец оператора for. После выполнения этого оператора в переменной nn будет храниться номер максимального элемента массива. Далее меняем местами максимальный элемент массива с элементом, до которого осуществлялся поиск.
m=a[N]; - сохраняем значение последнего элемента массива, до которого выполнялся поиск.
a[N]=a[nn]; - присваиваем последнему элементу массива, до которого выполнялся поиск, значение максимального элемента массива.
a[nn]=m; - В тот элемент массива, который имел максимальное значение, помещаем число, которое было в элементе массива, до которого выполнялся поиск (мы его сохранили в переменной m). Теперь два элемента массива поменялись местами.
N--; - уменьшаем значение номера последнего элемента массива, до которого осуществляется поиск, на единицу. Если первый раз мы искали максимальный элемент массива среди элементов с 0 по 9, то теперь будем искать среди элементов с 0 по 8. При следующем прохождении цикла while – с 0 по 7 и т.д., пока не останется два элемента: 0-й и 1-й. Когда N уменьшится до 0, цикл прекратится, т.к. нам не нужно искать среди одного элемента максимальный.
} – конец цикла while.
cout<<"\nМассив после сортировки:\n"; - выводим надпись.
for(i=0;i<10;i++) cout<<a[i]<<" "; - выводим массив после сортировки.
getch(); - ждем нажатия любой клавиши, чтобы выйти из программы.
} – конец функции main и всей программы.
Чтобы запустить программу, нажимаем комбинацию клавиш Alt+R, выбираем в появившемся меню пункт Run и нажимаем клавишу Enter. Ни в коем случае не нажимайте для запуска программы комбинацию клавиш Ctrl+F9 – это закроет DOSBox!
Программа предлагает по очереди ввести элементы массива, например такие, как указано на следующем рисунке:
После того, как мы ввели все 10 элементов массива, программа выведет содержимое массива до сортировки и после:
Как видим, сортировка прошла успешно. При нажатии на любую клавишу программа закроется.
ЗАДАНИЕ: измените программу таким образом, чтобы сортировка осуществлялась не по возрастанию, а по убыванию. Пришлите скриншот или фотографию.