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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: .

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

Алгоритм[править | править вики-текст]

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде, отсюда и название алгоритма).

Реализация[править | править вики-текст]

Реализация алгоритма на Swift

func bubbleSort<T: Comparable>(inout list: [T]) -> [T] {
        let size = list.count
        for i in 0..<size {
            let swapped = false
            let pass = (size - 1) - i
            for j in 0..<pass {
                let key = list[j]
                if key > list[j + 1] {
                    let temp = list[j + 1]
                    list[j + 1] = key
                    list[j] = temp
                    swapped = true
                }
            }
            
            if !swapped {
                break
            }
        }
        return list
    }

Реализация алгоритма на С++

void bubble_sort(int *a, int length)
{
     for (int i = 0; i < length-1; i++) {
        bool swapped = false;
         for (int j = 0; j < length-i-1; j++) {
             if (a[j] > a[j+1]) {
                 int b = a[j]; 
                 a[j] = a[j+1];
                 a[j+1] = b;
                 swapped = true;
             }
         }
         
         if(!swapped)
            break;
     }
 }

Реализация алгоритма (устойчивая) на Java.

public static <T extends Comparable<T>> void sort(T[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j].compareTo(arr[j + 1]) > 0) {
                T tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = true;
            }
        }            
        
        if(!swapped)
            break;
    }
}

Реализация алгоритма на Python

def bubble_sort(a):
    for i in reversed(range(len(a))):
        for j in range(1, i + 1):
            if a[j-1] > a[j]:
                a[j], a[j-1] = a[j-1], a[j]

Реализация алгоритма на PHP

 1 $a=array(5,4,3,1,2);
 2 for($j=0; $j < count($a)-1; $j++) {
 3     $swapped=false;
 4 	$i=0;
 5     while ($i < count($a)-1)  {
 6         if( $a[$i] > $a[$i+1]) {
 7             $c=$a[$i];
 8 	        $a[$i]=$a[$i+1];
 9 	        $a[$i+1]=$c;
10 	        $swapped=true;
11        }
12        ++$i;
13     } 
14     
15     if( !$swapped )
16         break;
17 }
18 print_r($a);


Реализация алгоритма на JavaScript

var int = [5, 4, 2, 3, 1];

//Вызывает сомнение необходимость уменьшать длину массива на единицу при использовании строгой проверки в цикле for!
//Предлагается: 'for (var j = 0, len = int.length; j < len; j++)'

for (var j = 0, len = int.length - 1; j < len; j++) {
    var swapped = false;
    var i = 0;
    while (i < len) {
        if (int[i] > int[i + 1]) {
            var c = int[i];
            int[i] = int[i + 1];
            int[i + 1] = c;
            swapped = true;
        }
        i++;
    }
    
    if(!swapped)
        break;
}
console.log(int);

Сложность: .

Наихудший случай:

  • Число сравнений в теле цикла равно .
  • Число сравнений в заголовках циклов равно .
  • Суммарное число сравнений равно .
  • Число присваиваний в заголовках циклов равно .
  • Число обменов равно , что в раз больше, чем в сортировке выбором.

Наилучший случай (на вход подаётся уже отсортированный массив):

  • Число сравнений в теле цикла равно .
  • Число сравнений в заголовках циклов равно .
  • Суммарное число сравнений равно .
  • Число обменов равно .

Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на -ой позиции. При втором проходе, следующий по значению максимальный элемент находится на месте. И так далее. Таким образом, на каждом следующем проходе число обрабатываемых элементов уменьшается на 1 и нет необходимости «обходить» весь массив от начала до конца каждый раз.

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

Введение индикатора (флажка F) действительно произошедших во внутреннем цикле обменов уменьшает число лишних проходов в случаях с частично отсортированными массивами на входе. Перед каждым проходом по внутреннему циклу флажок сбрасывается в 0, а после действительно произошедшего обмена устанавливается в 1. Если после выхода из внутреннего цикла флажок равен 0, то обменов не было, то есть массив отсортирован и можно досрочно выйти из программы сортировки.

Псевдокод ещё более улучшенного алгоритма с проверкой действительно произошедших обменов во внутреннем цикле.

На входе: массив , состоящий из элементов, с нумерацией от до

 ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1                       FOR J=1 TO N-1 STEP 1
   F=0                                             F=0 
   ЦИКЛ ДЛЯ I=1 ДО N-J ШАГ 1                       FOR I=1 TO N-J STEP 1 
     ЕСЛИ A[I] > A[I+1] ТО ОБМЕН A[I],A[I+1]:F=1     IF A[I]>A[I+1] THEN SWAP A[I],A[I+1]:F=1
   СЛЕДУЮЩЕЕ I                                     NEXT I  
   ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА                      IF F=0 THEN EXIT FOR
 СЛЕДУЮЩЕЕ J                                     NEXT J

В случае досрочного выхода из сортировки в этом алгоритме делается один избыточный проход без обменов.

Наихудший случай (не улучшается):

  • Число сравнений в теле цикла равно .
  • Число сравнений в заголовках циклов .
  • Суммарное число сравнений равно .
  • Число присваиваний в заголовках циклов равно .
  • Число обменов равно .

Наилучший случай (улучшается):

  • Число сравнений в теле цикла равно .
  • Число сравнений в заголовках циклов .
  • Суммарное число сравнений равно .
  • Число обменов равно .

Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе (операция сравнения ≈3.4мкс, обмена ≈2.3мкс) сортировкой выбором составило ≈40сек., ещё более улучшенной сортировкой пузырьком ≈30сек, а быстрой сортировкой ≈0,027сек.

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

Алгоритм можно немного улучшить, сделав следующее:

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

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

Псевдокод объединённого алгоритма сортировки пузырьком и сортировки выбором (устойчивая реализация):

 FOR J=1 TO N-1 STEP 1
    F=0
    MIN=J
    FOR I=J TO N-J STEP 1 
       IF Y[I]>Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1
       IF Y[I]<Y[MIN] THEN MIN=I
       NEXT I
    IF F=0 THEN EXIT FOR
    IF MIN<>J THEN SWAP Y[J],Y[MIN]
    NEXT J

Пример работы алгоритма[править | править вики-текст]

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Анимация, показывающая пример работы алгоритма.
Наглядная демонстрация алгоритма.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.
(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как
(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как
(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)
(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как
(1 2 4 5 8) (1 2 4 5 8)

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

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)

Теперь массив отсортирован и алгоритм может быть завершён.

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]