Сортировка пузырьком — различия между версиями
Vasin (обсуждение | вклад) |
Vasin (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
'''Сортировка простыми обменами''', '''сортиро́вка пузырько́м''' (англ. ''bubble sort'') — простой алгоритм сортировки. Сложность алгоритма: O(''n''²). | '''Сортировка простыми обменами''', '''сортиро́вка пузырько́м''' (англ. ''bubble sort'') — простой алгоритм сортировки. Сложность алгоритма: O(''n''²). | ||
| + | |||
| + | == Алгоритм == | ||
| + | Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма. | ||
Версия 02:28, 6 мая 2011
Алгоритм сортировки — это алгоритм для упорядочивания элементов. Поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Сложность алгоритма: O(n²).
Алгоритм
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
