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

Сортировка подсчетом

Внутренняя сортировка

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

Этот простой метод основан на том, что j-й ключ в сортирован­ной последовательности превышает ровно j-1 ключ. В первой фазе алгоритм подсчитывает для каждого ключа число ключей, которые меньше его. Значение счетчика для ключа и есть тот номер позиции в сортированной таблице, который он должен занять.

void CountSort(int n, int t[]){

// t – сортируемый массив целых чисел длиной n

int i,j;

int *c=new int[n]; // массив счетчиков

// обнулим счетчики

for(i=0; i<n; i++) c[i]=0;

// фаза подсчета

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

for(j=0; j<i; j++){

if(t[i]>t[j]){

c[i]++;

} else {

c[j]++;

}

}

}

// фаза расстановки

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

while(i!=c[i]){ // до тех пор, пока t[i] не займет

// окончательного положения

swap(t[i],t[c[i]]); // обмен местами эл-тов таблицы

swap(c[i],c[c[i]]); // обмен местами счетчиков

}

}

}

Ключ t_i в исходной последовательности сравнивается с iпредшест­вующими ключами и, следовательно, общее число сравнений равно

то есть пропорционально N².

Просматривая исходную последовательность ключей t, начиная с t₀, находим среди них наименьший и меняем местами с t₀, затем повторяем процесс начиная с t₁, находим наименьший и меняем местами с t₁, и так далее до конца таблицы. Ниже представлен текст функции, выполняющей сортировку простым выбором.

void SimpleChoice(int n, int t[]){

int i,j,k;

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

k=i;

// к моменту завершения цикла по j, k будет индексом

// наименьшего ключа на отрезке i…N-1

for(j=i+1;j<n;j++){

if(t[j]<t[k]){

k=j;

}

}

swap(t[i], t[k]);

}

}

В этом случае время также пропорционально N², так как при поиске наименьшего ключа на отрезке i…N-1,потребуется выполнить N-i-1сравнений. Суммируя по i, получим величину, пропорциональную N².