Bubblesort Aps
Por: Cleidson Schrute • 24/11/2015 • Trabalho acadêmico • 1.149 Palavras (5 Páginas) • 311 Visualizações
Este trabalho foi desenvolvido com base em um programa em linguagem C++ que o Professor Olavo Ito nos passou, é um programa de ordenação de números com os seguintes métodos: BubbleSort, QuickSort, SelectionSort e InsertionSort. Nós precisamos traduzir o programa que nos foi passado para a linguagem C# ou JAVA e escolher três dos quatro métodos passados. Escolhemos traduzir o programa para C# por ter maior conhecimento nessa linguagem, e escolhemos os métodos BubbleSort, SelectionSort e InsertionSort, por considerarmos que estes são os métodos que apresentam maior diferença entre os quatro.
Inicialmente iremos dar uma pequena introdução de cada método, para que se tenha um melhor entendimento, porém se deseja se ter um conhecimento mais amplo do assunto, sugerimos que procure em livros, ou artigos com foco no ensino do mesmos.
Método Bubble:
static void BubbleSort(int[] v, int tamanho)
{
// Cria uma instancia para contar o tempo de execução do método.
Stopwatch bs = new Stopwatch();
// Inicia a contagem.
bs.Start();
int i, j = tamanho, k, c = 0;
bool trocou = true;
do
{
tamanho--;
trocou = true;
for (i = 0; i < tamanho; i++)
{
if (v[i] > v[i + 1])
{
int aux = 0;
aux = v[i];
v[i] = v[i + 1];
v[i + 1] = aux;
trocou = false;
c++;
Console.Write(c + " - ");
//salva dados no arquivo txt.
dados.Write(c + " - ");
for (k = 0; k < j; k++)
{
Console.Write(v[k] + " ");
//salva dados no arquivo txt.
dados.Write(v[k] + " - ");
}
Console.WriteLine();
//salva dados no arquivo txt.
dados.WriteLine();
}
}
} while (trocou == false);
// Para a contagem do tempo.
bs.Stop();
// Exibe o tempo gasto.
Console.WriteLine("\nTempo gasto: " + bs.Elapsed + " Numero de linhas: "+c);
//salva dados no arquivo txt.
dados.Write("Tempo gasto: " + bs.Elapsed + " Numero de linhas: " + c);
dados.WriteLine();
}
Método Insertion:
static void InsertionSort(int[] v, int tamanho)
{
Stopwatch iS = new Stopwatch();
iS.Start();
int i, j, k, chave, c = 0;
for (j = 1; j < tamanho; j++)
{
chave = v[j];
i = j - 1;
while ((i >= 0) && (v[i] > chave))
{
v[i + 1] = v[i];
i--;
}
c++;
Console.Write(c + " - ");
//salva dados no arquivo txt.
dados.Write(c + " - ");
v[i + 1] = chave;
for (k = 0; k < j; k++)
{
Console.Write(v[k] + " ");
//salva dados no arquivo txt.
dados.Write(v[k] + " - ");
}
Console.WriteLine("\n");
//salva dados no arquivo txt.
dados.WriteLine();
}
c++;
Console.Write(c + " - ");
//salva dados no arquivo txt.
dados.Write(c + " - ");
for (k = 0; k < j; k++)
{
Console.Write(v[k] + " ");
//salva dados no arquivo txt.
dados.Write(v[k] + " - ");
}
Console.WriteLine();
//salva dados no arquivo txt.
dados.WriteLine();
iS.Stop();
Console.WriteLine("\nTempo gasto: " + iS.Elapsed + " Numero de linhas: " + c);
//salva dados no arquivo txt.
dados.Write("Tempo gasto: " + iS.Elapsed + " Numero de linhas: " + c);
dados.WriteLine();
}
Método Selection:
static void SelectionSort(int[] v, int tam)
{
Stopwatch ss = new Stopwatch();
ss.Start();
int i, j, k, min, c = 0;
for (i = 0; i < (tam - 1); i++)
{
min = i;
for (j = (i + 1); j < tam; j++)
{
if (v[j] < v[min])
{
min = j;
}
}
if (i != min)
{
c++;
Console.Write(c + " - ");
//salva dados no arquivo txt.
dados.Write(c + " - ");
int swap = v[i];
v[i] = v[min];
v[min] = swap;
for (k = 0; k < tamanho; k++)
{
Console.Write(v[k] + " ");
//salva dados no arquivo txt.
dados.Write(v[k] + " - ");
}
Console.WriteLine("");
//salva dados no arquivo txt.
dados.WriteLine();
}
}
ss.Stop();
Console.WriteLine("\nTempo gasto: " + ss.Elapsed + " Numero de linhas: " + c);
//salva dados no arquivo txt.
dados.Write("Tempo gasto: " + ss.Elapsed + " Numero de linhas: " + c);
dados.WriteLine();
}
Para a criação de números aleatórios sem repetição dos números usamos o seguinte processo:
for (i = 0; i < tamanho; i++)
{
bool jaExiste;
do
{
jaExiste = false;
vds[i] = rdn.Next(0, 1000);
for (int k = 0; k < i; k++)
{
if (vds[k] == vds[i])
jaExiste = true;
...