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

1.

ПУЗЫРЬКОВАЯ СОРТИРОВКА

2.

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

3.

АЛГОРИТМ ПУЗЫРЬКОВОЙ СОРТИРОВКИ

4.

РЕАЛИЗАЦИЯ АЛГОРИТМА ПУЗЫРЬКОВОЙ
СОРТИРОВКИ
#include <stdio.h>
#define max 1000
void bubbleSort(int* array, int n);
void swap(int *a, int *b);
int main() {
int n;
int array[max];
printf("Введите количество элементов
массива: ");
scanf("%d", &n);
printf("Введите элементы массива\n");
for(int i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
bubbleSort(array, n);
for(int i = 0; i < n; i++) {
printf("%d ", array[i]);
}
return 0;
}
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void bubbleSort(int* array, int n) {
for(int i = 0; i < n - 1; i++) {
for(int j = 0; j < n - i - 1; j++) {
if(array[j] > array[j+1]) {
swap(&array[j], &array[j+1]);
}
}
}
}

5.

ХАРАКТЕРИСТИКИ АЛГОРИТМА
Затраты по времени
- худший случай: O(n2)
- средний результат: O(n2)
- лучший случай: O(n)
Характерно для оптимизированного
алгоритма, то есть надо добавить
флаг, который будет отслеживать
Количество обменов при первом проходе
Затраты по памяти:
- O(1)

6.

- Является устойчивым алгоритмом сортировки
Тоесть если наш массив до сортировки был [1, 9 , 4’ , 7 , 4’’] то после
сортировки он будет [1, 4’, 4’’, 7, 9]
- Алгоритм всегда выполняет n2 – n проверок т.к внешний цикл будет
2
выполнен n – 1 раз, а внутренний n / 2 раз.
-Является детерменированным алгоритмом.