55
правок
Изменения
Нет описания правки
==Сортировка набора, состоящего из 0 и 1==
Дан массив <tex>a[1..n]</tex> из <tex>n</tex> чисел <tex>0</tex> и <tex>1</tex>. Требуется разделить элементы друг от друга так, чтобы сначала оказались все <tex>0</tex>, а в конце <tex>1</tex>.
}}
===Пример===
<tex> [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] </tex><br><tex=> [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] </tex>
===Алгоритм===
Будем поддерживать два указателя. Инициализируем первый индекс <tex>left = 1</tex> и второй индекс <tex>right = n</tex>.
# Уменьшаем <tex>right</tex> на <tex>1</tex> пока не <tex>a[right] = 1</tex>.
# Если <tex>left < right</tex>, то меняем местами <tex>a[left]</tex> и <tex>a[right]</tex>, <tex>left\texttt{++}</tex>, <tex>right\texttt{--}</tex>.
===Псевдокод===
'''int'''[] sort('''int''' a[]a) '''int''' left = 10, right = n- 1;
'''while''' (left < right)
'''while''' (arr[left] == 0 '''and''' left < right)
Дан массив <tex>a[1..n]</tex> из <tex>n</tex> чисел <tex>0</tex>, <tex>1</tex> и <tex>2</tex>. Требуется разделить их друг от друга так, чтобы сначала шли все <tex>0</tex>, потом все <tex>1</tex> и все <tex>2</tex> в конце.
}}
===Пример===
<tex> [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1] </tex><br><tex=> [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2] </tex>
===Алгоритм===
Будем поддерживать три указателя. Инициализация: <tex>lo = 1; mid = 1; hi = n;</tex>.
# <tex>a[mid..hi]</tex> неизвестны
# <tex>a[hi+1..n] = 2</tex>
===Псевдокод===
'''int'''[] sort('''int''' a[]a) '''int''' lo = 10, mid = 10, hi = n- 1;
'''while''' mid <tex>\leqslant</tex> right
'''switch''' (a[mid])
'''return''' a
== См. также ==
