Jump to content
Fórum Script Brasil
  • 0

Linguagem C - bubbleSort


heyJames

Question

QUERIA QUE  ALGUÉM ME AJUDASSE, E  DESCOBRISSE  porque MEU CÓDIGO ESTAR  DANDO  ERRO. Ele ta errando na ultima entrada do  exemplo a seguir! 

Problema bubbleSort: 

Uma das operações mais freqüentes em computação é ordenar uma seqüência de objetos. Por- tanto, não é surpreendente que essa operação seja também uma das mais estudadas.

Um algoritmo bem simples para ordenação é chamado Bubblesort. Ele consiste de vários turnos. A cada turno o algoritmo simplesmente itera sobre a seqüência trocando de posição dois elementos consecutivos se eles estiverem fora de ordem. O algoritmo termina quando nenhum elemento trocou de posição em um turno.

O nome Bubblesort (ordenação das bolhas) deriva do fato de que elementos menores ("mais leves") movem-se na direção de suas posições finais na seqüência ordenada (movem-se na direção do início da seqüência) durante os turnos, como bolhas na água. A figura abaixo mostra uma implementação do algoritmo em pseudo-código: 

Para i variando de 1 a N faça
	Para j variando de N - 1 a i faça
		Se seq[j - 1] > seq[j] então
			Intercambie os elementos seq[j - 1] e seq[j]
		Fim-Se
	Fim-Para
	Se nenhum elemento trocou de lugar então
		Final do algoritmo
	Fim-Se
Fim-Para

Por exemplo, ao ordenar a seqüência [5, 4, 3, 2, 1] usando o algoritmo acima, quatro turnos são necessários. No primeiro turno ocorrem quatro intercâmbios: 1 x 2, 1 x 3, 1 x 4 e 1 x 5; no segundo turno ocorrem três intercâmbios: 2 x 3, 2 x 4 e 2 x 5; no terceiro turno ocorrem dois intercâmbios: 3 x 4 e 3 x 5; no quarto turno ocorre um intercâmbio: 4 x 5; no quinto turno nenhum intercâmbio ocorre e o algoritmo termina.

Embora simples de entender, provar correto e implementar, o algoritmo bubblesort é muito ineficiente: o número de comparações entre elementos durante sua execução é, em média, diretamente proporcional a N2, onde N é o número de elementos na seqüência.

Você foi requisitado para fazer uma "engenharia reversa" no bubblesort, ou seja, dados o comprimento da seqüência, o número de turnos necessários para a ordenação e o número de intercâmbios ocorridos em cada turno, seu programa deve descobrir uma possível seqüência que, quando ordenada, produza exatamente o mesmo número de intercâmbios nos turnos.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois inteiros N e M que indicam respectivamente o número de elementos (1 ≤ N ≤ 100.000) na seqüência que está sendo ordenada, e o número de turnos (0 ≤ M ≤ 100.000) necessários para ordenar a seqüência usando bubblesort. A segunda linha de um caso de teste contém M inteiros Xi, indicando o número de intercâmbios em cada turno i (1 ≤ Xi ≤ N - 1, para 1 ≤ i ≤ M).

O final da entrada é indicado por N = M = 0.

A entrada deve ser lida da entrada padrão.

Saída

Para cada caso de teste da entrada seu programa deve produzir uma linha na saída, contendo uma permutação dos números {1, 2, . . . , N }, que quando ordenada usando bubblesort produz o mesmo número de intercâmbios no mesmo número de turnos especificados na entrada. Ao imprimir a permutação, deixe um espaço em branco entre dois elementos consecutivos. Se mais de uma permutação existir, imprima a maior na ordem lexicográfica padrão para seqüências de números (a ordem lexicográfica da permutação a1, a2, . . . aN é maior do que a da permutação b1, b2, . . . bN se para algum 1 ≤ i ≤ N temos ai > bi e o prefixo a1, a2, . . . ai-1 é iqual ao prefixo b1, b2, . . . bi-1) .

Em outras palavras, caso exista mais de uma solução, imprima aquela onde o primeiro elemento da permutação é o maior possível. Caso exista mais de uma solução satisfazendo essa restrição, imprima, dentre estas, aquela onde o segundo elemento é o maior possível. Caso exista mais de uma solução satisfazendo as duas restrições anteriores, imprima, dentre estas, a solução onde o terceiro elemento é o maior possível, e assim sucessivamente.

Para toda entrada haverá pelo menos uma permutação solução.

A saída deve ser escrita na saída padrão.

Exemplo

 

Entrada:
3 1
1
5 4
4 3 2 1
6 5
2 2 2 2 1
0 0

Saída:
2 1 3
5 4 3 2 1
6 5 1 2 3 4

Segue meu código:

#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int N, int M, int turno[]) {
    int seq[100000];
    int i, j;


    // Inicializa a sequência com os valores em ordem crescente
    for (i = 0; i < N; i++) {
        seq[i] = i+1;

    }

    // Realiza os intercâmbios nos turnos correspondentes
    for (i = 0; i < M; i++) {
        int numSwaps = turno[i];
        for (j = 0; j < numSwaps; j++) {
            int temp = seq[j];
            seq[j] = seq[j + 1];
            seq[j + 1] = temp;
        }
    }

    printf("%d P", seq[i]);

    // Imprime a sequência resultante
    for (i = 0; i < N; i++) {
        printf("%d ", seq[i]);
    }
    printf("\n");
}

int main() {
    int N, M;
    int turno[100000];

    while (1) {
        scanf("%d %d", &N, &M);
        if (N == 0 && M == 0) {
            break;
        }
        int i;
        for (i = 0; i < M; i++) {
            scanf("%d", &turno[i]);
        }

        bubbleSort(N, M, Xi);
    }

    return 0;
}
 

Link to comment
Share on other sites

1 answer to this question

Recommended Posts

  • 0

"Para i variando de 1 a N faça
    Para j variando de N - 1 a i faça
        Se seq[j - 1] > seq[j] então
            Intercambie os elementos seq[j - 1] e seq[j]
        Fim-Se
    Fim-Para

slope game
    Se nenhum elemento trocou de lugar então
        Final do algoritmo
    Fim-Se
Fim-Para"

How to continue?

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



  • Forum Statistics

    • Total Topics
      152.1k
    • Total Posts
      651.8k
×
×
  • Create New...