[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: Nionov  
Форум » Программирование » Web-программирование » Пузырьковая сортировка
Пузырьковая сортировка
RainbowДата: Четверг, 20.06.2019, 00:37 | Сообщение # 1

-= Повелитель кодеров =-
Сообщений: 146
Награды: 0
Репутация: 4279
Статус:
Сортировка пузырьком — это самый простой алгоритм сортировки, который работает путем многократной замены соседних элементов, если они находятся в неправильном порядке.
Пример:
Первый проход:
(5 1 4 2 8) (1 5 4 2 8), здесь алгоритм сравнивает два первых элемента и меняет их местами, так как (5>1).
(1 5 4 2 8) (1 4 5 2 8), меняет элементы местами, так как {displaystyle 5>4}{displaystyle 5>4}(5>4)
(1 4 5 2 8) (1 4 2 5 8), меняет элементы местами, так как {displaystyle 5>2}(5>2)
(1 4 2 5 8) (1 4 2 5 8), ввиду того, что элементы стоят на своих местах ({displaystyle 8>5}8>5), алгоритм не меняет их местами.
Второй проход:
(1 4 2 5 8) (1 4 2 5 8)
(1 4 2 5 8) (1 2 4 5 8), меняет элементы местами, так как (4>2){displaystyle 4>2}
(1 2 4 5 8) (1 2 4 5 8)
Теперь массив полностью отсортирован, но алгоритму это неизвестно. Поэтому ему необходимо осуществить полный проход и определить, что перестановок элементов не было.
Третий проход:
( 1 2 4 5 8) -> ( 1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8) )
(1 2 4 5 8 ) -> (1 2 4 5 8 )

Теперь массив отсортирован, и алгоритм может быть завершён.
Ниже приведена реализация сортировки пузырьком C:

Код
// C программа реализации пузырьковой сортировки

#include <stdio.h>

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

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

void bubbleSort(int arr[], int n)

{

int i, j;

for (i = 0; i < n-1; i++)

// Последние i элементы уже на месте

for (j = 0; j < n-i-1; j++)

if (arr [j]> arr[j+1])

swap(&arr, &arr[j+1]);

}

/* Функция вывода массива на экран */

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("n");

}

// Программа тестирования функций, приведенных выше

int main()

{

int arr[] = {64, 34, 25, 12, 22, 11, 90};

int n = sizeof(arr)/sizeof(arr[0]);

bubbleSort(arr, n);

printf("Sorted array: n");

printArray(arr, n);

return 0;

}[/i][/j]
 
Форум » Программирование » Web-программирование » Пузырьковая сортировка
  • Страница 1 из 1
  • 1
Поиск: