Сортировка массива методом пузырька

Язык C

Пузырьковая сортировка в C позволяет расположить числа в порядке возрастания или в порядке убывания, а также сортировать строки. Алгоритм пузырьковой сортировки неэффективен, так как его сложность как в среднем, так и в наихудшем случае равна O(n2).

Алгоритм пузырьковой сортировки

Начните с нулевого индекса, сравните элемент со следующим (a[0] &a[1] (a-имя массива)) и поменяйте местами, если a[0] >a[1]. Теперь сравните a[1] и a[2] и поменяйтесь местами, если a[1] >a[2]. Повторяйте этот процесс до конца массива. После этого самый большой элемент присутствует в конце. Все это известно как пропуск. В первом проходе мы обрабатываем элементы массива из [0,n-1].

Повторите первый шаг, но обработайте элементы массива [0, n-2], потому что последний, то есть a[n-1], присутствует в своем правильном положении. После этого шага самые большие два элемента присутствуют в конце. Повторите этот процесс n-1 раз.

Программа пузырьковой сортировки на языке Си

/* Код сортировки пузырьков */
#include<stdio.h>

int main()
{
int array[100], n, c, d, swap;

printf(«Введите количество элементов\n»);
scanf(«%d», &n);

printf(«Введите %dцелых чисел\n», n);

for (c = 0; c < n; c++)
scanf(«%d», &array[c]);

for (c = 0 ; c < n — 1; c++)
{
for (d = 0 ; d < n — c — 1; d++)
{
if (array[d] >array[d+1]) /* Для убывания порядка используйте'<‘ insteadof ‘>’ */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}

printf(«Сортированный список в порядке возрастания:n»);

for (c = 0; c < n; c++)
printf(«%d\n», array[c]);

return 0;
}

Вывод программы:

Введите 6 целых чисел
2
-4
7
8
4
7

Сортированный список в порядке возрастания:

-4
2
4
7
7
8

Выбор сортировки в C

Сортировка выбора в C для сортировки чисел массива в порядке возрастания. С небольшой модификацией он упорядочивает числа в порядке убывания.

Алгоритм сортировки выбора (для возрастающего порядка)

Найдите минимальный элемент в массиве и замените его элементом в 1 — й позиции.
Снова найдите минимальный элемент в оставшемся массиве[2, n] и замените его элементом на 2-й позиции, теперь у нас есть два элемента на их правильных позициях.

Мы должны сделать это n-1 раз, чтобы отсортировать массив.

Программы сортировки в C

#include<stdio.h>
int main()
{
int array[100], n, c, d, position, t;

printf(«»Введите количество элементов\n»);
scanf(«%d», &n);

printf(«Введите %d целых чисел\n», n);

for (c = 0; c < n; c++)
scanf(«%d», &array[c]);

for (c = 0; c< (n — 1); c++) // нахождение минимального элемента (n-1) раз
{
position = c;

for (d = c + 1; d < n; d++)
{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
t = array[c];
array[c] = array[position];
array[position] = t;
}
}

printf(«Сортированный список в порядке возрастания:\n»);

for (c = 0; c < n; c++)
printf(«%d\n», array[c]);

return 0;
}

Выход программы:

Введите 10 целых чисел
12
8
-6
2
4
5
3
7
4
2

Сортированный список в порядке возрастания:

-6
2
2
3
4
5
7
8
12

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

Программа сортировки пузырьков на языке Си с помощью функции

#include <stdio.h>
voidbubble_sort(long [], long);

int main()
{
longarray[100], n, c;

printf(«Введите количество элементов:\n»);
scanf(«%ld», &n);

printf(«Введите %dцелых чисел:», n);

for (c = 0; c < n; c++)
scanf(«%ld», &array[c]);

bubble_sort(array, n);

printf(«Сортированный список в порядке возрастания: \n»);

for (c = 0; c < n; c++)
printf(«%ld\n», array[c]);

return 0;
}

voidbubble_sort(long list[], long n)
{
long c, d, t;

for (c = 0 ; c < n — 1; c++) {
for (d = 0 ; d < n — c — 1; d++) {
if (list[d] > list[d+1]) {
/* Замена*/
t = list[d];
list[d] = list[d+1];
list[d+1] = t;
}
}
}
}

Мы можем использовать алгоритм пузырьковой сортировки, чтобы проверить, отсортирован ли массив или нет. Если замена не происходит, то массив сортируется. Мы можем улучшить его наилучшую сложность до O(n).

#include <stdio.h>
intis_Array_Sorted(int [], int);

int main()
{
inta[100], n, c;

printf(«Введите количество элементов:\n»);
scanf(«%d», &n);

printf(«Введите %d целых чисел\n», n);

for (c = 0; c < n; c++)
scanf(«%d», &a[c]);

if (is_Array_Sorted(a, n))
printf(«Массив отсортирован.\n»);
else
printf(«Массив не отсортирован.\n»);

return 0;
}

intis_Array_Sorted(int a[], int n) {
int c, d, sorted = 1, t;

for (c = 0 ; c < n — 1; c++) {
for (d = 0 ; d < n — c — 1; d++) {
if (a[d] > a[d+1]) {
t = a[d];
a[d] = a[d+1];
a[d+1] = t;
return 0;
}
}
}
return 1;
}

Оцените статью
Образовательный портал WELCOME4U.RU
Добавить комментарий

Adblock
detector