Dutch national flag (3-way partition)
Në shqip: Problemi i flamurit holandez
ShpjegimiSQ
Rendit një varg me vetëm tre vlera (p.sh. 0, 1, 2) në një kalim, me tre tregues: një për 0-at, një për 2-shat dhe një që lëviz. Klasik në intervista dhe bazë për quicksort me shumë përsëritje.
EnglishEN
Sort an array with only three values (e.g. 0, 1, 2) in one pass with three pointers: one for 0s, one for 2s and one moving. A classic interview question and the basis of quicksort with many duplicates.
Si ta mendosh
Si të ndash topat e kuq, të bardhë dhe blu në një kalim të vetëm.
Lexoje në anglisht
Like separating red, white and blue balls in a single pass.
Shembull kodipython
ul, mes, la = 0, 0, len(v) - 1
while mes <= la:
if v[mes] == 0: v[ul], v[mes] = v[mes], v[ul]; ul += 1; mes += 1
elif v[mes] == 2: v[mes], v[la] = v[la], v[mes]; la -= 1
else: mes += 1