• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

MACkie

Duvida Insertion-Sort

5 mensagens neste tópico

Boas.

É a minha estreia aqui e pelas piores razões. Tou a programar o Insertion-Sort em C# mas a ordenação não funciona. O output é igual ao input. O objectivo é ordenar e escrever o output para um ficheiro txt.

Código:

class insertionsort
    {
        public static void InsertSort(IComparable[] array)
        {
            StreamWriter sw = new StreamWriter("C:\\Array.txt");
            int i, j;

                for (i = 0; i < array.Length; i++)
                {
                    IComparable value = array[i];
                    j = i - 1;
                    
                    while ((j >= 0) && (array[j].CompareTo(value) > 0))
                    {
                        array[j + 1] = array[i];
                        j--;
                    }
                    array[j + 1] = array[i];
                    sw.Write(array[i] + "\r\n");
                }

                sw.Close();
        }
    }

Pequena observação: no final do ciclo, o array inicial (desordenado) fica ordenado, certo?

Onde encontrarem o erro, agradeço que informem... tou a começar a fritar!  :wallbash:

PS: Quero aprender, não quero que o façam por mim - como muita gente por esses fóruns do mundo...

Obrigado,

MACkie

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

while ((j >= 0) && (array[j].CompareTo(value) > 0))

{

    array[j + 1] = array[ i];

Penso que não era bem isto que tu querias. Repara, array[ i] = value é sempre o mesmo valor dentro do while... tu queres é deslocar os elementos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não percebi... :S

Ao longo do ciclo o value não toma o valor do array? Por exemplo, array[1]..array[2]..array[5]...?

EDIT: Isto já funciona.. vou tentar perceber o que eu "inventei" para aqui e já faço um re-edit a dizer.

Meti um ciclo for para correr o array e mandar para o ficheiro:

for (int c = 0; c < array.Length; c++)

                {

                    sw.Write(array[c] + "\r\n");

                }

E mais algumas alterações que tavam a causar conflito (por exemplo: array[j + 1] = array[j] ao invés de array).

Obrigado Njay,

MACkie

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ao longo do ciclo for sim... mas eu referia-me ao while (a não ser que essa classe IComparable de C# seja mágica, não sei, não percebo de C#). Dentro do while tens que ir deslocando os elementos "para a frente", só que em vez disso o que tás a fazer é colocar alguns iguais ao value (= array[ i]). Ou não entendeste o algoritmo ou não estás a ver bem o que implementaste. Tenta correr esse algoritmo numa folha de papel para as 1ªs 2 ou 3 iterações.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só deves fazer o output no fim do processamento porque no ciclo onde percorres o array, quando i passa a 3 só tens a garantia que os 3 primeiros elementos do array estão ordenados entre si - não significa que não há elementos menores do que estes 3 no resto do array. Ou seja, se o array fosse [3,4,2,1], quando termina o processamento de i = 2, o array está [2,3,4,1].

Eu também não sei C#, por isso é dificil analisar o código. Mas entendendo que é parecido com java, penso que a classe IComparable só significa que o array passado na função tem de ser de um tipo que tenha o método compareTo(), ou seja, podem ser comparados entre si.

Visto que já corrigiste o problema, depois coloca o código a funcionar...

Neste caso não acontece, mas o valor de "value" podia ser alterado se tivermos um array de objectos duma classe. Se for como em java, ao fazermos  value = array e não com uma cópia. Por isso, se array[i ] fosse alterado, value também era. Isto não acontece para tipos primitivos: int , char , boolean, double... onde são sempre efectuadas cópias. Para classes, existe o clone().

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora