| dbo:abstract | - The Dutch national flag problem is a computational problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: red, white, and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order. The solution to this problem is of interest for designing sorting algorithms; in particular, variants of the quicksort algorithm that must be robust to repeated elements may use a three-way partitioning function that groups items less than a given key (red), equal to the key (white) and greater than the key (blue). Several solutions exist that have varying performance characteristics, tailored to sorting arrays with either small or large numbers of repeated elements. (en)
- Le problème du drapeau hollandais est un problème de programmation, présenté par Edsger Dijkstra, qui consiste à réorganiser une collection d'éléments identifiés par leur couleur, sachant que seules trois couleurs sont présentes (par exemple, rouge, blanc, bleu, dans le cas du drapeau des Pays-Bas). Étant donné un nombre quelconque de balles rouges, blanches et bleues alignées dans n'importe quel ordre, le problème est à les réarranger dans le bon ordre : les bleues d'abord, puis les blanches, puis les rouges. Au départ les balles sont disposées dans un ordre quelconque. À la fin, toutes les balles de la même couleur doivent être rangées ensemble et l'ordre entre les couleurs doit être respecté, ainsi que l'ordre que les balles de même couleur avaient les unes par rapport aux autres dans l'agencement initial : on trouve par exemple d'abord tous les objets bleus, puis tous les objets blancs et enfin tous les objets rouges et si une balle rouge apparaissait avant une autre balle rouge, elle doit apparaître dans cet ordre dans l'agencement final (on appelle un tel algorithme de tri un algorithme stable). L'espace mémoire auxiliaire doit aussi être optimisé. La solution est à la base d'algorithmes de tris, en particulier de variantes de quicksort qui doivent être stables. Autrement dit on cherche à définir un algorithme qui regroupe des items en trois catégories, ceux qui sont plus petits, ceux qui sont plus grands, et ceux qui sont égaux à un élément spécifique sans trop bouleverser l'ordre initial. (fr)
- O problema da bandeira da Holanda é um proposto por Edsger Dijkstra em 1976 relacionado a algoritmos de ordenamento. Supõe-se que numa urna sejam postas bolas pintadas de azul, vermelho ou branco (cores da bandeira da Holanda) em qualquer quantidade, desde que haja uma de cada cor. O problema propõe que o algoritmo deva ser capaz de agrupar todas as bolas de uma mesma cor em sequência e as sequências de cores estejam ordenadas. Desta maneira, no vetor ordenado das bolas desta urna estariam posicionadas primeiro todas as vermelhas, depois todas as brancas e, por fim, todas as azuis. No entanto, o algoritmo é limitado a acessar a cor de cada bola apenas uma única vez, visando a um menor número de comparações, acessos e, por conseguinte, um crescimento assintótico menos punitivo. A maioria das respostas deste desafio é bastante familiar com o algoritmo do quicksort. Segue a solução proposta (adaptada) pelo próprio Dijkstra: vetor urna[N] // sendo N o tamanho do arrayver = 1, bra = N, azu = N// ver é o índice do último elemento da sequência de bolas vermelhas// bra é o índice do último elemento da sequência de bolas brancas// azu é o índice do primeiro elemento da sequência de bolas azuis enquanto b >= v: cor = checar cor de urna[bra] se cor é vermelha: trocar(urna[ver], urna[bra]) ver = ver + 1 senao-se cor é branca: bra = bra - 1 senao-se cor é azul: trocar(urna[bra], urna[azul]) bra = bra - 1 azu = azu - 1 (pt)
|
| dbo:thumbnail | |
| dbo:wikiPageExternalLink | |
| dbo:wikiPageID | |
| dbo:wikiPageLength | - 4828 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID | |
| dbo:wikiPageWikiLink | |
| dbp:wikiPageUsesTemplate | |
| dcterms:subject | |
| gold:hypernym | |
| rdf:type | |
| rdfs:comment | - The Dutch national flag problem is a computational problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: red, white, and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order. (en)
- Le problème du drapeau hollandais est un problème de programmation, présenté par Edsger Dijkstra, qui consiste à réorganiser une collection d'éléments identifiés par leur couleur, sachant que seules trois couleurs sont présentes (par exemple, rouge, blanc, bleu, dans le cas du drapeau des Pays-Bas). Étant donné un nombre quelconque de balles rouges, blanches et bleues alignées dans n'importe quel ordre, le problème est à les réarranger dans le bon ordre : les bleues d'abord, puis les blanches, puis les rouges. (fr)
- O problema da bandeira da Holanda é um proposto por Edsger Dijkstra em 1976 relacionado a algoritmos de ordenamento. Supõe-se que numa urna sejam postas bolas pintadas de azul, vermelho ou branco (cores da bandeira da Holanda) em qualquer quantidade, desde que haja uma de cada cor. O problema propõe que o algoritmo deva ser capaz de agrupar todas as bolas de uma mesma cor em sequência e as sequências de cores estejam ordenadas. Desta maneira, no vetor ordenado das bolas desta urna estariam posicionadas primeiro todas as vermelhas, depois todas as brancas e, por fim, todas as azuis. No entanto, o algoritmo é limitado a acessar a cor de cada bola apenas uma única vez, visando a um menor número de comparações, acessos e, por conseguinte, um crescimento assintótico menos punitivo. (pt)
|
| rdfs:label | - Dutch national flag problem (en)
- Problème du drapeau hollandais (fr)
- Problema da bandeira dos Países Baixos (pt)
|
| owl:sameAs | |
| prov:wasDerivedFrom | |
| foaf:depiction | |
| foaf:isPrimaryTopicOf | |
| isdbo:wikiPageDisambiguates of | |
| isdbo:wikiPageWikiLink of | |
| isrdfs:seeAlso of | |
| isfoaf:primaryTopic of | |
