Задача флага Нидерландов — различия между версиями

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

Версия 00:55, 8 июня 2015

Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а и их общие цвета шли в порядке как на данном флаге.

Сортировка набора, состоящего из 0 и 1

Задача:
Дан массив [math]a[0..n-1][/math] из [math]n[/math] чисел [math]0[/math] и [math]1[/math]. Требуется разделить элементы друг от друга так, чтобы сначала оказались все [math]0[/math], а в конце [math]1[/math].


Пример

Исходный массив: [math] a = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0][/math] Полученный массив: [math] sort(a) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] [/math]

Алгоритм

Будем поддерживать два указателя. Инициализируем первый индекс [math]left = 0[/math] и второй индекс [math]right = n - 1[/math].

У будем делать следующее пока [math]left \lt right[/math]

  1. Увеличиваем [math]left[/math] на [math]1[/math] пока не [math]a[left] = 0[/math].
  2. Уменьшаем [math]right[/math] на [math]1[/math] пока не [math]a[right] = 1[/math].
  3. Если [math]left \lt right[/math], то меняем местами [math]a[left][/math] и [math]a[right][/math], [math]left\texttt{++}[/math], [math]right\texttt{--}[/math].

Псевдокод

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

Задача:
Дан массив [math]a[0..n-1][/math] из [math]n[/math] чисел [math]0[/math], [math]1[/math] и [math]2[/math]. Требуется разделить их друг от друга так, чтобы сначала шли все [math]0[/math], потом все [math]1[/math] и все [math]2[/math] в конце.


Пример

Исходный массив: [math] a = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1][/math] Полученный массив: [math] sort(a) = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2] [/math]

Алгоритм

Будем поддерживать три указателя. Инициализация: [math]lo = 0; mid = 0; hi = n - 1[/math].

У будем делать следующее пока [math]mid \leqslant right[/math]

  1. Если [math]a[mid] = 0[/math], то меняем местами [math]a[lo][/math] и [math]a[mid][/math], [math]lo\texttt{++}[/math], [math]mid\texttt{++}[/math].
  2. Если [math]a[mid] = 1[/math], то [math]mid\texttt{++}[/math].
  3. Если [math]a[mid] = 0[/math], то меняем местами [math]a[mid][/math] и [math]a[hi][/math], [math]hi\texttt{--}[/math].

Инвариант работы алгоритма:

  1. [math]a[0..lo-2] = 0[/math]
  2. [math]a[lo-1..mid-2] = 1[/math]
  3. [math]a[mid-1..hi-1][/math] неизвестны
  4. [math]a[hi..n-1] = 2[/math]

Псевдокод

int[] sort(int[] a)
    int lo = 0, mid = 0, hi = n - 1
    while mid [math]\leqslant[/math] 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

См. также

Источники информации