Сортировка пузырьком
Сортировка пузырьком
Идея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала.
Отсортируем массив {1, 5, 2, 7, 6, 3}
Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы
1, 2, 5, 7, 6, 3
Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами
1, 2, 5, 6, 7, 3
3 нарушает порядок, меняем местами с 7
1, 2, 5, 6, 3, 7
Возвращаемся к началу массива и проделываем то же самое
1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7
Говорят, что это похоже на "всплытие" более "лёгких" элементов, как пузырьков, отчего алгоритм и получил такое название.
void bubbleSort(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = 1; j < size; j++) {
if (a[j] > a[j-1]) {
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
}
Этот алгоритм всегда будет делать (n-1)2 шагов, независимо от входных данных. Даже если массив отсортирован, всё равно он будет пройден (n-1)2 раз. Более того, будут в очередной раз проверены уже отсортированные данные.
Пусть нужно отсортировать массив 1, 2, 4, 3
1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
После того, как были поменяны местами элемента a[2] и a[3] нет больше необходимости проходить этот участок массива. Примем это во внимание и переделаем алгоритм
void bubbleSort2(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = i; j > 0; j--) {
if (a[j] < a[j-1]) {
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
}
Ещё одна реализация
void bubbleSort2b(int *a, size_t size) {
size_t i, j;
int tmp;
for (i = 1; i < size; i++) {
for (j = 1; j <= size-i; j++) {
if (a[j] < a[j-1]) {
tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
}
В данном случае будет уже вполовину меньше шагов, но всё равно остаётся проблема сортировки уже отсортированного массива: нужно сделать так, чтобы отсортированный массив функция просматривала один раз. Для этого введём переменную-флаг: он будет опущен (flag = 0), если массив отсортирован. Как только мы наткнёмся на нарушение порядка, то флаг будет поднят (flag = 1) и мы начнём сортировать массив как обычно.
void bubbleSort3(int *a, size_t size) {
size_t i;
int tmp;
char flag;
do {
flag = 0;
for (i = 1; i < size; i++) {
if (a[i] < a[i-1]) {
tmp = a[i];
a[i] = a[i-1];
a[i-1] = tmp;
flag = 1;
}
}
} while (flag);
}
В этом случае сложность также порядка n2, но в случае отсортированного массива будет всего один проход.
Теперь усовершенствуем алгоритм. Напишем функцию общего вида, чтобы она сортировала массив типа void. Так как тип переменной не известен, то нужно будет дополнительно передавать размер одного элемента массива и функцию сравнения.
int intSort(const void *a, const void *b) {
return *((int*)a) > *((int*)b);
}
void bubbleSort3g(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i;
void *tmp = NULL;
char flag;
tmp = malloc(item);
do {
flag = 0;
for (i = 1; i < size; i++) {
if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) {
memcpy(tmp, ((char*)a + i*item), item);
memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item);
memcpy(((char*)a + (i-1)*item), tmp, item);
flag = 1;
}
}
} while (flag);
free(tmp);
}
Функция выглядит некрасиво – часто вычисляется адрес текущего и предыдущего элемента. Выделим отдельные переменные для этого.
void bubbleSort3gi(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) {
size_t i;
void *tmp = NULL;
void *prev, *cur;
char flag;
tmp = malloc(item);
do {
flag = 0;
i = 1;
prev = (char*)a;
cur = (char*)prev + item;
while (i < size) {
if (cmp(cur, prev)) {
memcpy(tmp, prev, item);
memcpy(prev, cur, item);
memcpy(cur, tmp, item);
flag = 1;
}
i++;
prev = (char*)prev + item;
cur = (char*)cur + item;
}
} while (flag);
free(tmp);
}
Теперь с помощью этих функций можно сортировать массивы любого типа, например
void main() {
int a[10] = {1, 0, 9, 8, 7, 6, 2, 3, 4, 5};
int i;
bubbleSort3gi(a, sizeof(int), 10, intSort);
for (i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
_getch();
}
Сортировка многомерного массива
Сортировка статического многомерного массива по существу не отличается от сортировки одномерного. Можно воспользоваться тем свойством, что статический одномерный и многомерный массивы имеют одинаковое представление в памяти.
void main() {
int a[3][3] = {1, 9, 2, 8, 3, 7, 4, 6, 5};
int i, j;
bubbleSort3gi(a, sizeof(int), 9, intSort);
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", a[i][j]);
}
}
}
Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m.
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bubbleSort2d(int **a, size_t m, size_t n) {
int tmp;
size_t i, j, k, jp, ip;
size_t size = m*n;
char flag;
do {
flag = 0;
for (k = 1; k < size; k++) {
//Вычисляем индексы текущего элемента
j = k / m;
i = k - j*m;
//Вычисляем индексы предыдущего элемента
jp = (k-1) / m;
ip = (k-1) - jp*m;
if (a[i][j] > a[ip][jp]) {
tmp = a[i][j];
a[i][j] = a[ip][jp];
a[ip][jp] = tmp;
flag = 1;
}
}
} while(flag);
}
#define SIZE_X 3
#define SIZE_Y 4
void main() {
int **a = NULL;
int i, j;
a = (int**) malloc(sizeof(int*) * SIZE_X);
for (i = 0; i < SIZE_X; i++) {
a[i] = (int*) malloc(sizeof(int) * SIZE_Y);
for (j = 0; j < SIZE_Y; j++) {
a[i][j] = rand();
printf("%8d ", a[i][j]);
}
printf("\n");
}
printf("\nafter sort\n");
bubbleSort2d(a, SIZE_X, SIZE_Y);
for (i = 0; i < SIZE_X; i++) {
for (j = 0; j < SIZE_Y; j++) {
printf("%8d ", a[i][j]);
}
printf("\n");
}
for (i = 0; i < SIZE_X; i++) {
free(a[i]);
}
free(a);
_getch();
}
Во-вторых, можно сначала переместить массив в одномерный, отсортировать одномерный массив, после чего переместить его обратно в двумерный.
void bubbleSort3gi2d(void **a, size_t item, size_t m, size_t n, int (*cmp)(const void*, const void*)) {
size_t size = m*n, sub_size = n*item;
size_t i, j, k;
void *arr = malloc(size * item);
char *p1d = (char*)arr;
char *p2d = (char*)a;
//Копируем двумерный массив типа void в одномерный
for (i = 0; i < m; i++) {
memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size);
}
bubbleSort3gi(arr, item, size, cmp);
//Копируем одномерный массив обратно в двумерный
for (i = 0; i < m; i++) {
memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size);
}
}
Если вас смущает эта функция, то воспользуйтесь типизированной. Вызов, из предыдущего примера
bubbleSort3gi2d((void**)a, sizeof(int), SIZE_X, SIZE_Y, intSort);
