Bitonic Sort

[alves077]

Boa noite,

Não sei bem se devia tirar aqui a minha dúvida, se não for aqui, peço desculpa pelo off-topic.

Estou a estudar o bitonic sort, só que não percebo muito bem como funciona, no caso de o n entradas o nosso n for um número impar, não sei se alguém aqui conhece este tipo de algoritmo, se alguem souber agradecia a ajuda.

Já tive a ver na Internet mas não acho com número ímpar, tens que ir trocando os números um pouco aos pares, mas no caso de impar fica a sobre um número, não se muito como fazer.

Obrigado pela atenção,

alves077

[HappyHippyHippo]

o wikipedia tem um bom exemplo de código http://en.wikipedia.org/wiki/Bitonic_sorter

isto parece mesmo o quick sort ...

[alves077]

Até percebo +/- a lógica, ja tive a ver na Internet, o problema é que tenho que simular para 7 entradas, já percebi quando as entradas são pares, mas quando são ímpares não sei como passar o esquema, se me percebes.

Obrigado pela atenção,

alves077

[HappyHippyHippo]

o código na wiki não diz que só funciona para um numero par de elementos ... já experimentaste correr o algoritmo ??

[Rui Carlos]

Uma forma simples de resolveres o problema é adicionares um elemento ao array, quando tiveres um número ímpar de elementos (de preferência, adicionas um elemento maior do que todos os outros, para no final só teres que remover o último elemento do array).

Mas penso que também podes testar no momento das comparações/swaps se os elementos que queres comparar existem, e se um deles não existir, passas à frente.

Também penso que se não usares uma destas soluções, até precisas de arrays de dimensão 2^n. Mas confesso que já não olhava para este algoritmo há uns anos, pelo que já não me recordo de todos os detalhes do seu funcionamento.

[alves077]

A minha questão é antes de implementar o código em si, queria perceber bem como funciona, e não estou a perceber como funciona com numero ímpar de elementos. Com número para percebo as comparações, elas batem certo. Mas com ímpar já não consigo perceber como se faz. Antes de implementar tenho que perceber isto bem. Mais do que código queria perceber o algoritmo em si.

Obrigado pela atenção,

alves077

[pmg]

Para perceberes como funciona, pensa que a comparação é feita com o próprio elemento quando este não tem par. Se a comparação for "estritamente maior" ou "estritamente menor" o algoritmo não vai fazer a troca entre o mesmo elemento.

[alves077]

Desculpem voltar a abrir este tópico, mas não consegui perceber muito bem este algoritmo.

Em caso de for impar, mesmo que ele compare com ele próprio não fica ordenado.

Por exemplo a sequência 33 11 30 21 20 43 10 4 2 1 3

Deixando o 3 a comparar com ele próprio, como é possível isto sair ordenado? Sinceramente acho que alguma coisa me está a escapar, porque não percebe que a partir de uma rede de ordenamento bitonic isto fica ordena. Ainda não percebi muito bem onde posso por comparador, se me entendem, parece que este algoritmo depende da sequência de entrada. Alguém que me possa ajudar agradecia.

Obrigado pela atenção,

alves077

Edited June 6, 2012 at 06:59 PM by alves077

[Rui Carlos]

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm

[alves077]

Obrigado pela atenção,

Mas ja tive a ver esse site e mesmo assim têm pormenores que nao consegui perceber. Um deles é a disposição dos comparadores? Se é ao meu belo prazer...

Se depende da sequência, não sei bem...

Depois se o número de entradas for ímpar, também não consigo resolver..

[pmg]

Em cada passagem pelo algoritmo troca os elementos com a letra correspondente se estiverem fora de ordem. Os elementos impares (mais geralmente, os elementos sem par, nao sao trocados)

0: 33 11 30 21 20 43 10 04 02 01 03
    a  a  b  b  c  c  d  d  e  e  f (f)
1: 11 33 21 30 20 43 04 10 01 02 03
    a  b  b  a  c  d  d  c  e  f  f (e)
2: 11 21 33 30 10 04 43 20 01 02 03
    a  a  b  b  c  c  d  d  e  e  f (f)
3: 11 21 30 33 04 10 20 43 01 02 03
    a  b  c  d  d  c  b  a  e  f  g (gfe)
4: 11 20 10 04 33 30 21 43 01 02 03
    a  b  a  b  c  d  c  d  e  f  e (f)
5: 10 04 11 20 21 30 33 43 01 02 03
    a  a  b  b  c  c  d  d  e  e  f (f)
6: 04 10 11 20 21 30 33 43 01 02 03
    a  b  c  d  e  f  g  h  h  g  f (edcba)
7: 04 10 11 20 21 03 02 01 43 33 30
    a  b  c  d  a  b  c  d  e  f  g (gfe)
8: 04 03 02 01 21 10 11 20 43 33 30
    a  b  a  b  c  d  c  d  e  f  e (f)
9: 02 01 04 03 11 10 21 20 30 33 43
    a  a  b  b  c  c  d  d  e  e  f (f)
10: 01 02 03 04 10 11 20 21 30 33 43

[Rui Carlos]

Tens nesse site uma implementação em Java. É só adaptares.

A alternativa passa por adicionares elementos ao array, sempre que o tamanho do array não for uma potência de 2.

pmg, isso não me parece o bitonic sort. Logo para começar, porque as trocas não são sempre efectuadas na mesma direcção. Depois, não estás a trocar os elementos correctos. No caso do bitonic sort, a estratégia que propõe não vai funcionar.

EDIT: aparentemente esse é um método alternativo de implementar o BS, e como ordena sempre os elementos na mesma direcção, a estratégia de não trocar os elementos se não tiverem "par" já funciona.

Mas faz-me um pouco de confusão chamar a isso também BS, pois deixamos de ter sequência de elementos bitónicas.

[alves077]

Obrigado pela ajuda pmg, acho que percebi mais ou menos, e realmente bate certo. Mas se puderem só tirar mais uma dúvida agradecia. Como tu vês onde colocar um comparador, isto é a ordem com que comparas é alguma regra pré-definida?

Rui consigo com esta rede de ordenação encontrar sub-redes de ordenamento bitónico? Senão fazes ideia como posso fazer de maneira que use o bitonic sort?

Obrigado pela atenção,

alves077

Edited June 7, 2012 at 12:30 AM by alves077

[pmg]

Em 07/06/2012 às 01:18, alves077 disse:

Como tu vês onde colocar um comparador, isto é a ordem com que comparas é alguma regra pré-definida?

Para por os comparadores simplesmente segui a segunda imagem no artigo da Wikipedia 🙂

Mas o texto explica como colocar os comparadores, tanto na versao mais complicada (a primeira) como na segunda (mais simples).

Olhando para a imagem

podes reparar que para ordenar 2 elementos so precisas de 1 quadrado azul de tamano 2;

para ordenar 3 ou 4 precisas de 1 quadrado azul de tamanho 4 (e 2 de tamanho 2);

para ordenar 5, 6, 7, ou 8 precisas de 1 quadrado azul de tamanho 8 (e 2 de tamanaho 4, ...);

etc ...

cada quadrado novo segue regras especificas quanto aos comparadores.

Na minha resposta anterior, os "niveis" que eu coloquei correspondem a grupos de comparadoes da imagem.

[alves077]

Pelo que percebo consigo fazer com as duas versões, mas como fizeste consigo recolher sub-redes ordenamento bitonico?

Se fizer na primeira versão já não bate certo, se por os comparadores tal como está na imagem, mas já me dá sub-sequencias bitónicas. Pela segunda fica ordenado mas pelo o meio não encontro nenhuma sub-rede bitonica.

Obrigado pela atenção,

alves077

Edited June 7, 2012 at 10:02 PM by alves077