 |
|
Основные принципы метода
1. Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки возрастает относительно количества элементов.
2. Алгоритм не использует дополнительной памяти: все операции происходят "на месте".
Давайте, определим, насколько устойчив данный метод? Рассмотрим последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них. Результат ее сортировки можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a.
Таким образом, входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя не очень оптимально. Однако, такую сортировку можно использовать для массивов имеющих небольшие размеры.
| Предыдущая | Оглавление | Следующая | |||
| Предыдущая | Оглавление | Следующая | |||
"Пузырьковая" cортировка.
Идея метода состоит в следующем: шаг сортировки заключается в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. Для реализации расположим массив сверху вниз, от нулевого элемента - к последнему. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию.
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
Пример кода.
| #include <iostream>#include <stdlib.h>#include <time.h>using namespace std;template <typename T>void bubbleSort(T a[], long size){ long i, j; T x; for(i=0;i<size;i++){ // i - номер прохода for(j=size-1;j>i;j--){ // внутренний цикл прохода if(a[j-1]>a[j]){ x=a[j-1]; a[j-1]=a[j]; a[j]=x; } } }} void main(){ srand(time(NULL)); const long SIZE=10; int ar[SIZE]; // до сортировки for(int i=0;i<SIZE;i++){ ar[i]=rand()%100; cout<<ar[i]<<"\t"; } cout<<"\n\n"; bubbleSort(ar,SIZE); // после сортировки for(int i=0;i<SIZE;i++){ cout<<ar[i]<<"\t"; } cout<<"\n\n";} |