Методы сортировки С++ — это алгоритмы сортировки, которые реализованы на языке программирования C++.
Общие сведения о сортировке данных
На сегодняшний день создание программ для персональных компьютеров считается помимо средства, правильное использование которого может способствовать оптимальной работе практически в каждой прикладной области, также может стать и сферой научных разработок. Можно считать очевидным тот факт, что знание алгоритмов может иметь определяющее значение при формировании решений о необходимости структурировать данные. Потоки самой разнообразной информации постоянно увеличиваются в объемах.
Для того чтобы сохранить разную информацию, применяются специальные базы данных. При этом подобные базы, когда в них имеется очень большое количество компонентов, использовать в практических целях становится необычайно сложно, а иногда и вовсе нереально. Не потерять необходимые данные в таких значительных информационных объемах без применения сортировки, также практически нереально.
Сортировка данных способна обеспечить возможность сравнительно быстро и качественно выделить необходимую информацию из предварительно упорядоченного информационного набора. Это означает, что алгоритмы сортировки обладают очень большим значением, в частности в тех случаях, когда выполняется информационная обработка. В сфере программирования отводится особое внимание методикам сортировки и их алгоритмам.
Сегодня существует достаточно много методов сортировки, реализованных по разным алгоритмам и обладающих разнообразным характером и скоростью информационной обработки. Однако следует заметить, что у многих из них присутствует один значительный недостаток, состоящий в том, что период их выполнения увеличивается пропорционально квадрату количества компонентов.
По мнению специалистов приблизительно двадцать пять процентов времени при выполнении централизованной компьютерной обработки занимает сортировка данных. Такое положение дел обусловлено тем фактом, что намного легче найти необходимую информацию в массиве, когда этот массив прошел процедуру предварительной сортировки. Иначе процесс нахождения требуемых данных становится аналогичным поиску иголки в стоге сена. Пользователи используют поиск информации в базе данных фактически все время, и это обстоятельство предполагает применение специальных методов сортировки, поскольку поисковые алгоритмы могут работать значительно более оперативно с базами данных, которые уже были отсортированы.
Методы сортировки С++
Наиболее популярной может считаться сортировка выбором (Selection sort). Для осуществления сортировки массива в порядке возрастания, следует при всех итерациях находить элемент, который обладает самым большим значением. Его необходимо поменять местами с последним элементом. Очередной элемент, имеющий максимальное значение, следует определить уже на предпоследнее место. Данные действия нужно выполнять до тех пор, пока элементы, расположенные на первых местах в массиве, не окажутся расположенными в требуемом порядке. Ниже представлена программа данного метода сортировки, выполненная на языке C++:
void SortAlgo::selectionSort(int data$[]$, int lenD)
{
int j = 0;
int tmp = 0;
for(int i=0; i∠lenD; i++){
j = i;
for(int k = i; k∠lenD; k++){
if(data$[j]$>data$[k]$){
j = k;
}
}
tmp = data$[i]$;
data$[i]$ = data$[j]$;
data$[j]$ = tmp;
}
}
Следующим по популярности методом может считаться пузырьковая сортировка (Bubble sort). Пузырьковая сортировка предполагает выполнение сравнения соседних элементов, и затем их следует поменять местами в случае, если последующий элемент окажется меньше предыдущего. Нужно исполнить целый ряд проходов по массиву данных. При выполнении первого прохода реализуется сравнение первых двух элементов массива. Если они располагаются не в требуемом порядке, то они меняются местами и затем осуществляется сравнение элементов следующей пары. Обмен местами этой пары элементов выполняется на тех же условиях. Такая сортировка исполняется в каждом цикле вплоть до достижения конца массива. Ниже представлена программа, реализующая этот метод сортировки на языке C++:
voìd SortAlgo::bubbleSort(ìnt data$[]$,ìnt lenD)
{
ìnt tmp = 0;
for(int i = 0;i∠lenD;i++){
for(int j = (lenD-1);j>=(i+1);j--){
if(data$[j]$∠data$[j-1]$){
tmp = data$[j]$;
data$[j]$=data$[j-1]$;
$data[j-1]=tmp$;
}
}
}
}
Далее следует рассмотреть реализацию метода сортировки вставками (Insertion sort). При исполнении сортировки вставками необходимо сначала осуществить разбиение массива на следующие области:
- Область, которая является упорядоченной.
- Область, которая является неупорядоченной.
В начальном состоянии все элементы массива должны восприниматься как неупорядоченная область. При выполнении первого проход начальный элемент из неупорядоченной области подлежит изъятию и должен быть помещен в правильном местоположении в упорядоченной области. При всех последующих проходах размеры упорядоченной области будут увеличиваться на один элемент, а размер неупорядоченной области будет уменьшаться также на один элемент.
Основной цикл этого метода сортировки способен функционировать в интервале от единицы до N-1. При выполнении j-й итерации элемент $[ì] $необходимо вставить в требуемоее положение в упорядоченной области. Это может быть реализовано за счет сдвига всех элементов упорядоченной области, больших, чем $[i]$, на одну позицию вправо. Элемент $[ì] $требуется вставить в интервале между теми элементами, которые являются меньшими, чем $[ì]$, и теми, которые больше $[ì]$. Ниже представлена программа, которая реализует данный метод сортировки, на языке программирования C++:
void SortAlgo::insertionSort(int data$[]$, int lenD)
{
ìnt key = 0;
ìnt ì = 0;
for(ìnt j = 1;j∠lenD;j++){
$ key = data[j]$;
ì = j-1;
whìle(i>=0 && data$[ì]$>key){
$data[ì+1] = data[i]$;
ì = ì-1;
$data[ì+1]=key$;
}
}
}
Известны также и другие методы сортировки, но они являются менее эффективными.
