Виды алгоритмов сортировки Сортировка пузырьком / Bubble sort

жүктеу/скачать 121,16 Kb.

бет	1/12
Дата	16.10.2023
өлшемі	121,16 Kb.
	#115872

1 2 3 4 5 6 7 8 9 ... 12

Виды алгоритмов сортировки
Сортировка пузырьком / Bubble sort
Сортировка пузырьком — это простейший и один из самых известных алгоритмов сортировки. Идея заключается в последовательном сравнении значений соседних элементов. Если текущий элемент больше следующего, меняем их местами. Алгоритм необходимо повторять до тех пор, пока массив не будет отсортирован.

Плюсы и минусы
Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.
Пример реализации на Kotlin:
private fun bubbleSort(array: IntArray) {
if (array.isEmpty()) return

var swap = true

while (swap) {
swap = false
for (i in 1 until array.size) {
if (array[i] < array[i - 1]) {
val temp = array[i - 1]
array[i - 1] = array[i]
array[i] = temp
swap = true
}
}
}
}
Пример реализации на С++:
#include
// Вспомогательная функция для замены значений двух индексов в массиве
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Функция для печати `n` элементов массива `arr`
void printArray(int arr[], int n)
{
for (inti=0;iprintf("%d ", arr[i]);
}
}
// Функция для выполнения пузырьковой сортировки заданного массива `arr[]`
void bubbleSort(int arr[], int n)
{
// `n-1` проходит
for (int k=0;k{
// последние `k` элементов уже отсортированы, поэтому внутренний цикл может
// не смотреть на последние `k` элементов
for (int i=0;i{
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
// алгоритм может быть остановлен, если внутренний цикл не производил никакого обмена
}
}
int main(void)
{
int arr[] = { 3, 5, 8, 4, 1, 9, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printArray(arr, n);
return 0;
}

жүктеу/скачать 121,16 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9 ... 12