Задача флага Нидерландов — различия между версиями
Oxygen3 (обсуждение | вклад) |
Oxygen3 (обсуждение | вклад) |
||
Строка 8: | Строка 8: | ||
===Пример=== | ===Пример=== | ||
− | Исходный массив: <tex> a = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]</tex> | + | Исходный массив: <tex> a = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]</tex> <br> |
Полученный массив: <tex> sort(a) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] </tex> | Полученный массив: <tex> sort(a) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] </tex> | ||
Строка 40: | Строка 40: | ||
===Пример=== | ===Пример=== | ||
− | Исходный массив: <tex> a = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]</tex> | + | Исходный массив: <tex> a = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]</tex><br> |
Полученный массив: <tex> sort(a) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2] </tex> | Полученный массив: <tex> sort(a) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2] </tex> | ||
Версия 00:56, 8 июня 2015
Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а и их общие цвета шли в порядке как на данном флаге.
Содержание
Сортировка набора, состоящего из 0 и 1
Задача: |
Дан массив | из чисел и . Требуется разделить элементы друг от друга так, чтобы сначала оказались все , а в конце .
Пример
Исходный массив:
Полученный массив:
Алгоритм
Будем поддерживать два указателя. Инициализируем первый индекс
и второй индекс .У будем делать следующее пока
- Увеличиваем на пока не .
- Уменьшаем на пока не .
- Если , то меняем местами и , , .
Псевдокод
int[] sort(int[] a) int left = 0, right = n - 1 while (left < right) while (arr[left] == 0 and left < right) left++ while (arr[right] == 1 and left < right) right-- if (left < right) swap(a[left], a[right]) left++ right-- return a
Сортировка набора, состоящего из 0, 1 и 2
Задача: |
Дан массив | из чисел , и . Требуется разделить их друг от друга так, чтобы сначала шли все , потом все и все в конце.
Пример
Исходный массив:
Полученный массив:
Алгоритм
Будем поддерживать три указателя. Инициализация:
.У будем делать следующее пока
- Если , то меняем местами и , , .
- Если , то .
- Если , то меняем местами и , .
Инвариант работы алгоритма:
- неизвестны
Псевдокод
int[] sort(int[] a)
int lo = 0, mid = 0, hi = n - 1
while mid
right
switch (a[mid])
case 0:
swap(a[lo++], a[mid++])
break
case 1:
mid++
break
case 2:
swap(a[mid], a[hi--])
break
return a