сортировка пузырьком

• Улучшения
• Все реализации

Очень простой, компактный, но медленный алгоритм сортировки. На каждой итерации мы вытягиваем наименьшие(наибольшие) элементы на свои позиции по некоторой аналогии с всплытием пузырьков на поверхность воды.

На каждой итерации(шаге) сортировки осуществляется проход по неотсотированной части массива и если текущий элемент меньше(при сортировке по-убыванию конечно) следующего - то меняем их местами(swap-им) друг с другом. Таким образом после первой итерации наш наименьший элемент "всплывет": окажется в конце последовательности. Затем такая же процедура, но только уже до предпоследнего элемента: последний-то, наименьший из всех - уже стоит на своем месте. И так до (n-1)-ой итерации, после которой в неотсортированной последовательности окажется 1 элемент, который очевидно будет занимать свое законное место там.

Пример. Пусть имеем последовательность из n=5 элементов: x=[3,7,2,5,6]. Будем сортировать по возрастанию. Получим:

1 шаг: цикл по всем элементам. 3>7? нет. Оставляем как есть. 7>2? да. меняем 7 и 2: [3,2,7,5,6]. 7>5? да. Меняем 7 и 5:[3,2,5,7,6]. Далее. 7>6? Да. Меняем 6 и 7:[3,2,5,6,7].

2 шаг: цикл по всем элементам кроме последнего. Аналогично осуществляя, получим в конце:[2,3,5,6,7].

3 шаг: цикл до 3-го элемента в нашем случае. Перестановок не будет, все остается по-прежнему:[2,3,5,6,7].

4 шаг: цикл до второго элемента. Перестановок тоже не будет.

5 шаг: цикл по одному первому элементу. Он не больше своего соседа(2 < 3), поэтому и здесь перестановок не будет. Т.о. алгоритм завершил свою работу и мы получили отсортированную последовательность: [2,3,5,6,7].

Данный алгоритм имеет вид:

for i = 0 to n-1
    j = n-1
    while (j > i)
        if (x[j-1] > x[j])
            swap(x, j-1, j)
        j--
 

Улучшения

Приведенный выше пример как раз наводит на мысль о таком улучшении: после 2-го шага мы уже получили отсортированную последовательность, проходы на 3-ем, 4-ом и 5-ом шаге отработали вхолостую, не сделав уже никаких перестановок конечно. Поэтому их следовало бы уже исключить. Правило такое, если на какой-то итерации не было сделано ни одной перестановки - значит этот проход последний и мы уже имеем отсортированную последовательность. Реализовать это очень просто: на каждой итерации помимо всего прочего устанавливаем некоторый флаг при первой сделанной сортировке:

for i = 0 to n-1
    j = n-1
    sorted = true
    while (j > i)
        if (x[j-1] > x[j])
            swap(x, j-1, j)
            sorted = false
        j--
    if sorted
        break
 

Анализируя алгоритм дальше можно прийти еще к одному выводу: если на некоторой итерации после определенного индекса(=k например) - перестановок уже не было, то их не будет и на всех следующих итерациях. Возвращаясь к нашему примеру - имеем это на 2-ом шаге: после перестановки 3 и 2, других уже больше не было. Т.е. k = 1 в данном случае. Очевидно, что раз на следующих после k элементах перестановок не было, то они уже расположены в правильном порядке.

Соответственно получим следующий алгоритм:

last = -1
for i = 0 to n-1
    j = n-1
    k = i
    if last > 0 && last > i
        k = last
    while (j > k)
        if (x[j-1] > x[j])
            swap(x, j-1, j)
            last = j
        j--
    if last == k
        break
 

Реализации:

заполните необходимые поля!

название:
uri-имя*:
заголовок окна:
ЯП:	[другой...] pseudojavajavascriptpythonC++C#CphpGoqbasicrailsrubysmartytsqlvbnetvisualfoxproxmlactionscriptplsqlpascaloracle8sqlvbfortransmalltalkasmcssdelphigroovylispperlmysqlmatlab
код (double click - редактирование) (Esc - предпросмотр)
описание:
автор:	email:
пароль:	[для последующего редактирования]
	подписаться на комментарии**

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

 сортировка пузырьком в чистом виде, без оптимизации ссылка |режим:

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
template<class T>
void BubbleSort(T* x) {
    for (int i = 0; i < n; i++) {
        for (int j = n-1; j > i; j-- ) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
            }
        }
    }
}

template<class T> void swap(T* x, int i, int j) { T tmp; tmp = x[i]; x[i] = x[j]; x[j] = tmp; } template<class T> void BubbleSort(T* x) { for (int i = 0; i < n; i++) { for (int j = n-1; j > i; j-- ) { if (x[j-1] > x[j]) { swap(x, j-1, j); } } } }

Самая медленная реализация сортировки пузырьком, до каких-либо оптимизаций.
Скорее ради частоты эксперимента и понимания метода.

Производительность: ~ O(n²)
Расход памяти: - (только пара счетчиков цикла и вызов swap-а)

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

 

 Сортировка пузырьком с признаком отсортированности массива. Версия #2 ссылка |режим:

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
template<class T>
void BubbleSort2(T* x) {
    for (int i = 0; i < n; i++) {
        bool sorted = true;
        for (int j = n-1; j > i; j-- ) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
                sorted = false;
            }
        }
        if (sorted) break;
    }
}

template<class T> void swap(T* x, int i, int j) { T tmp; tmp = x[i]; x[i] = x[j]; x[j] = tmp; } template<class T> void BubbleSort2(T* x) { for (int i = 0; i < n; i++) { bool sorted = true; for (int j = n-1; j > i; j-- ) { if (x[j-1] > x[j]) { swap(x, j-1, j); sorted = false; } } if (sorted) break; } }

Модификация базового метода. Если массив после какого-то шага уже получился отсортированным - то процедура завершается, предотвращая холостые проходы.

Производительность: ~ O(n²)
Расход памяти: - (только пара счетчиков цикла и вызов swap-а)

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

 

 Сортировка пузырьком, дальнейшая оптимизация. Версия #3 ссылка |режим:

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
template<class T>
void BubbleSort3(T* x) {
    int last = -1;
    for (int i = 0; i < n; i++) {
        int k = i;
        if (last > 0 && last > i) {
            k = last;
        }
        for (int j = n-1; j > k; j-- ) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
                last = j;
            }
        }
        if (last == k) break;
    }
}

template<class T> void swap(T* x, int i, int j) { T tmp; tmp = x[i]; x[i] = x[j]; x[j] = tmp; } template<class T> void BubbleSort3(T* x) { int last = -1; for (int i = 0; i < n; i++) { int k = i; if (last > 0 && last > i) { k = last; } for (int j = n-1; j > k; j-- ) { if (x[j-1] > x[j]) { swap(x, j-1, j); last = j; } } if (last == k) break; } }

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

Производительность: ~ O(n²)
Расход памяти: - (только пара счетчиков цикла и вызов swap-а)

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0