Программа C для сортировки пузырьком: сортировка пузырьком на C

Введение

Сортировка массива занимает огромное место в информатике. Его полезность замечают, когда есть необходимость упорядочить данные в определенном порядке. Существуют различные виды алгоритмов сортировки. Наиболее распространенным и широко используемым алгоритмом сортировки является пузырьковая сортировка.

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

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

Этот алгоритм сравним с пузырьками в воде, поскольку он отфильтровывает верхнюю часть пузырьков, похожих на массив. Среди всех алгоритмов, используемых для сортировки, пузырьковая сортировка является самой простой и самой медленной с временной сложностью O (n ^ 2). Однако алгоритм можно оптимизировать за счет использования флаговой переменной, которая выходит из цикла после завершения обмена. Наилучший случай для пузырьковой сортировки может быть O (n), когда массив отсортирован.

Например, возьмем несортированный массив из пяти чисел, как показано ниже.

13, 32, 26, 34, 9

Пузырьковая сортировка начнет учитывать первые два элемента и сравнит их, чтобы проверить, какой из них больше. В данном случае 32 больше 13. Так что эта часть уже отсортирована по y. Далее мы сравниваем 32 с 26. Итак, мы находим, что 32 больше, чем 26, поэтому их нужно поменять местами. Новый массив будет выглядеть так

13, 26, 32,34,9

Далее сравниваем 32 и 34. Мы знаем, что они уже отсортированы. Таким образом, мы переходим к двум последним переменным 34 и 9. Поскольку 34 больше 9, их нужно поменять местами.

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

13, 26. 32,9,34

После второй итерации массив будет иметь вид

13, 26, 9,32,34

После третьей итерации массив станет

13,9,26,32,34

После четвертой итерации массив будет полностью отсортирован

9, 13,26,32,34

Обязательно к прочтению: Идеи проектов на C

Алгоритм

Здесь мы предполагаем, что массив состоит из n элементов. Кроме того, мы предполагаем, что функция обмена значениями меняет местами все значения, чтобы номера массива были отсортированы.

запустить пузырьковую сортировку (массив)

для всех элементов списка

если массив[i]> массив[i+1]

обмен значениями (массив [i], массив [i+1])

конец, если

конец для

возвращаемый массив

конец пузырьковой сортировки

Читайте: Сортировка в структуре данных: категории и типы

Псевдокод

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

Псевдокод алгоритма BubbleSort можно записать следующим образом.

процедура BubbleSort (массив: элементы массива)

итерация = массив.счетчик;

для k = 0 для итерации-1 выполните:

флаг = ложь

для l=0 для повторения-1 выполните:

если (массив[l]> массив[l+1]), то

обмен значениями (массив [l], массив [l+1])

флаг = правда

конец, если

конец для

Если (не поменять местами), то

Перерыв

Конец, если

Конец для

Завершить массив возврата процедуры

Давайте попробуем пример программы пузырьковой сортировки на C :

# включить<stdio.h>

пустая функция

{

массив целых чисел [10], i, j, число

для (я=0; я<=9; я++)

{

scanf("%d", &массив[i])

}

для (я = 0; я <= 9; я ++)

{

для (j=0;j<=9-i;j++)

{

если (массив[j]>массив[j+1])

{

число = массив [j];

массив[j]=массив[j+1];

массив[j+1]=число;

}

}

}

printf("Отсортированный массив /n");

для (я = 0; я <= 9; я ++)

{

printf("%d",&массив[i])

}

}

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

Внутри внешнего цикла есть еще один цикл. Он начинается с j=0 и выполняется до тех пор, пока не станет меньше или равно восьми. Внутри есть условный оператор if, который сравнивает и проверяет, больше ли массив [j], чем массив [j+1]. Если условие выполнено, значения массива [j] и массива [j+1] меняются местами друг с другом.

Для этой цели используется переменная с именем num. Сначала массив [j] присваивается num, затем массив [j+1] присваивается массиву [j] и, наконец, num присваивается массиву [j+1]. Этот процесс будет продолжаться до тех пор, пока все элементы массива не будут отсортированы в порядке возрастания. После этого отсортированный массив печатается.

Оптимизированная реализация пузырьковой сортировки

У нас есть оптимизированный алгоритм пузырьковой сортировки для улучшения результатов. Использование переменной флага выполняет оптимизацию. Переменная флага будет содержать 1, если есть обмен, иначе он вырвется из цикла. Ниже представлена ​​оптимизированная программа пузырьковой сортировки на C.

#include<stdio.h>

пустая функция

{

массив целых чисел [10], i, j, num, flag=0;

для (я=0; я<=9; я++)

{

scanf("%d", &массив[i])

}

для (я = 0; я <= 9; я ++)

{

для (j=0;j<=9-i;j++)

{

если (массив[j]>массив[j+1])

{

число = массив [j];

массив[j]=массив[j+1];

массив[j+1]=число;

флаг=1;

}

если (! флаг)

{

перерыв;

}

}

}

printf("Отсортированный массив /n");

для (я = 0; я <= 9; я ++)

{

printf("%d",&массив[i])

}

}

Данная программа выполняется аналогично обычной программе пузырьковой сортировки. Единственным изменением является использование переменной флага. Изначально флаг установлен в 0. Однако, если происходит перестановка, флаг становится 1. Это означает, что массив все еще требует еще одной проверки. С другой стороны, если флаг не равен 1, что означает, что подкачки не было, мы выходим из внутреннего цикла, предполагая, что массив уже отсортирован. После выполнения мы получим тот же результат, что и обычная пузырьковая сортировка.

Сложность времени

Наилучшая временная сложность для сортировки пузырьком составляет O (n). Это происходит, когда массив уже отсортирован. Худший случай — O(n*n), когда массив не отсортирован.

Читайте: 12 лучших программ шаблонов на Java, которые вы должны проверить сегодня

Что дальше?

Если вам интересно узнать больше о Java, разработке программного обеспечения с полным стеком, ознакомьтесь с дипломом PG upGrad & IIIT-B по разработке программного обеспечения с полным стеком, который предназначен для работающих профессионалов и предлагает более 500 часов интенсивного обучения, 9+ проектов. и задания, статус выпускника IIIT-B, практические практические проекты и помощь в трудоустройстве в ведущих фирмах.