Сортировка Пузырьком.

А лгоритм:

• Для сортировки используется 2 цикла , один вложен в другой . Один используется на шаге , другой на под-шаге.

• Суть алгоритма - это сравнение двух элементов. Элементы будут сравниваться парами : 1 и 2, 2и 3,3 и 4,4 и 5,6 и 7 и т.д. При сравнении пар, если предыдущий элемент оказался больше чем последующий - то их меняют местами. Например если второй элемент равен 5, а третий 2, то они их поменяют местами.

• Сортировка методом пузырька делится на шаги. В каждом шаге выполняется попарное сравнение. В результате каждого шага наибольшие элементы начинают выстраиваться с конца массива. То есть после первого шага самый большой по значению элемент массива будут стоять на последнем месте. Во втором шаге работа производится со всеми элементами кроме последнего. Опять находится самый большой элемент и ставится в конец массива, с которым производится работа. Третий шаг повторяет второй и так до тех пор, пока массив не будет отсортирован.

Сложность: .

Алгоритм устойчивый.

Сортировка на том же месте.

Эффективен только при малых массивах данных.

Шейкерная сортировка.

Алгоритм:

• Шейкерная сортировка одна из модификаций пузырьковой сортировки. Она отличается тем, что вместо того, чтобы повторно проходить по списку слева на право, она проходит поочередно сначала слева на право, а затем справа на лево.

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

Сложность: .

Алгоритм устойчивый.

Сортировка на том же месте.

Эффективен как и при малых так и при больших массивах данных.

Сортировка выбором.

Алгоритм:

• находим минимальное значение в текущем списке

• производим обмен этого значения со значением на первой неотсортированной позиции

• теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

Сложность: .

Алгоритм может быть устойчивым и неустойчивым.

Сортировка на том же месте.

Эффективен как и при малых так и при больших массивах данных.(???)

Сортировка включением(метод вставки).

Алгоритм:

• Массив делится на две части: в первой все элементы отсортированы, во второй нет. На первом шаге считаем, что первый элемент массива отсортирован.

• Выбираем первый элемент после отсортированной части и вставляем его в нужное место в отсортированной части (используем любой метод поиска и вставки элемента в массив). И так до тех пор пока не кончится массив.

Сложность: .

Алгоритм устойчивый.

Сортировка на том же месте.

Эффективен на небольших наборах данных.

Эффективен на наборах данных, которые уже частично отсортированы;

Может сортировать список по мере его получения.

Может быть реализована с помощью списков.