Пузырьковая сортировка

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

for (int i=0; i<size-1; i++) {

for (int j=size-1; j>0; j--) {

//Сравниваем два соседних элемента

if (numbers[j-1] > numbers[j]) {

//Меняем их местами, если

//они стоят не в том порядке

int temp = numbers[j];

numbers[j] = numbers[j-1];

numbers[j-1] = temp;

}

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

Сортировка методом вставок должна быть хорошо знакома людям, играющим в карты. Представьте себе, что вам раздали карты для игры. Карты следует расставить по старшинству: слева – старшие карты, а справа – младшие. Другими словами, задача заключается в том, чтобы отсортировать полученные карты в порядке убывания. Наши действия таковы:

первую карту отодвигаем влево.
берем вторую карту и ставим ее либо перед первой, либо после нее в зависимости от старшинства.
берем третью карту и также в зависимости от старшинства ставим ее либо перед первыми двумя, либо между ними, либо после них.
действия продолжаем, пока не расставим все карты.

Отсюда и название метода – «Сортировка вставками». После очередной вставки отсортированная часть массива увеличивается на 1. Таким образом, программа имеет вид:

//Вставляем элементы, начиная со второго

for (int i=1; i<size; i++) {

<Вставить элемент с номером i

относительно элементов 0,…,i-1>

}

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

//Вставляем элементы, начиная со второго

for (int i=1; i<size; i++) {

//Индекс вставляемого элемента

int j=i;

//Ищем позицию, куда вставить элемент

while (numbers[j]<numbers[j-1] && j!=0) {