Сортировка пузырьком (Bubble Sort) + Реализация С++

Идея сортировки пузырьком состоит в том, что на каждой итерации попарно сравниваются элементы и если элементы находятся в неправильном порядке, происходит их обмен.
Время работы O(n^2)
Алгоритм:

1. Начинаем с конца массива, берем элемент a[j], где j=n-1 и сравниваем попарно элементы a[j] и a[j-1]
2. Если a[j]<a[j-1], то swap(a[j],a[j-1]), т.е. более легкий элемент всплывает
3. Уменьшаем j и повторяем до тех пор, пока выполняетсяс j>i

Графическая иллюстрация (стырено с algolist):

Реализация:

template < typename Type >
void Bubble_Sort(Type mas[], unsigned long size){
 for (unsigned long i=0; i< size; i++)
  for (unsigned long j=size-1; j > i; j--)
   if (mas[j]< mas[j-1])
    swap (mas[j],mas[j-1]);
}

Posted in: Алгоритмы, Сортировки, CPP