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