Пузырьковая сортировка

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

Пузырьковая сортировка основана на сравнении двух соседних элементов. Если элемент слева больше, чем справа, они меняются местами. Для реализации алгоритма понадобятся 2 цикла: первый проходит весь массив от начала до конца, а второй — внутренний — проходит массив сначала и до отсортированной части. Таким образом, одна итерация внутреннего цикла ставит на место только один элемент. Он будет последним элементом массива. Внутри этого цикла и осуществляется сравнение пар соседних элементов.

Асимптотическая сложность алгоритма — O(N²).

Далее приводится реализация алгоритма пузырьковой сортировки на разных языках программирования.

#include <stdio.h>
#include <stdlib.h>

void exchange_bubble_sort(int ar[], int length)
{
	for (int i = 1; i < length; i++) { for (int j = length - 1; j >= i; j--) {
			if (ar[j - 1] > ar[j]) {
				int temp = ar[j - 1];
				ar[j - 1] = ar[j];
				ar[j] = temp;
			}
		}
	}
}

int main(void)
{
	int length = sizeof(arr) / sizeof(*arr);

	show("Array: ", arr, length);

	exchange_bubble_sort(arr, length);

	show("Sorted array: ", arr, length);

	return 0;
}

internal class Program
{
    static void ExchangeBubbleSort(T[] arr) where T:IComparable
    {
        int length = arr.Length;
        
        for(int j=0; j<length; j++)
        {
            for(int i=0; i<length-j-1; i++)
            {
                if (arr[i].CompareTo(arr[i+1])==1)
                {
                    T temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }
    }

    static void Main(string[] args)
    {
        int[] arr = { 12, 5, 4, 9, 8, 10, 0, 2, 1, 3, -1 };
        
        Console.WriteLine($"Array: {string.Join(" ", arr)}");

        ExchangeBubbleSort(arr);

        Console.WriteLine($"Sorted array: {string.Join(" ", arr)}");

        
        Console.ReadKey();
    }
}

<?php
function ExchangeBubbleSort(array &$arr) {
    $length=count($arr);

    for($i=1; $i<$length; $i++) { for($j=$length-1; $j>=$i; $j--) {
            if ($arr[$j-1]>$arr[$j]) {
                $temp=$arr[$j-1];
                $arr[$j-1]=$arr[$j];
                $arr[$j]=$temp;
            }
        }
    }
}

function exchangeBubbleSort(arr) {
    if (Array.isArray(arr)) {
       const len=arr.length;

       for(let i=1; i<len; i++) { for(let j=len-1; j>=i; j--) {
             if (arr[j-1]>arr[j]) {
                let temp=arr[j-1];
                arr[j-1]=arr[j];
                arr[j]=temp;
             }
          }
       }
    }
    else {
        throw new Error("Argument must be of type Array");
    }
}