Boa tarde Pessoal !
To com um problema pra rodar o Quicksort. Ele ta dando essa mensagem de estouro de pilha quando uso uma quantidade relevante de elementos pra ordenar. Li um tanto de coisa na net mas como tenho pouca prática não entendi se é por causa do método pra escolher
pivô ou se tenho que implementar algo pra aumentar a memória ou se é não deve ser recursivo. Me ajudem por favor... O código é esse:
using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
namespace Trabalho1
{
class Program
{
public static void QuickSort(int[] vetor)
{
QS(vetor, 0, vetor.Length - 1);
}
private static void QS(int[] a, int left, int right)
{
if (right <= left) return;
int i = PT(a, left, right);
int j = i - 1;
int k = i + 1;
QS(a, left, j); // => se trocar left por i-1 e k por i+1 dá erro
QS(a, k, right);
}
private static int PT(int[] a, int l, int r)
{
int i = l - 1, j = r;
int v = a[r], temp;
for (; ; )
{
while (a[++i] < v && i < r) ;// if (i == r) break;
while (v < a[--j] && j > l) ;// if (j == l) break;
if (i >= j) break;
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
temp = a[i];
a[i] = a[r];
a[r] = temp;
return i;
}
private static int PT2(int[] a, int l, int r)
{
int i = l, j = r + 1;
int v = a[l], temp;
for (; ; )
{
while (a[++i] < v && i < r) ;// if (i == r) break;
while (v < a[--j] && j > l) ;// if (j == l) break;
if (i >= j) break;
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
temp = a[j];
a[j] = a[l];
a[l] = temp;
return j;
}
private static Boolean CheckSort(int[] vetor)
{
for (int i = 0; i < vetor.Length - 1; i++)
if (vetor[i] > vetor[i + 1])
return false;
return true;
}
public void Ordenacao(int TAM1)
{
StreamWriter writer = new StreamWriter("Saida50mil.txt", true);
Random r = new Random();
TAM1 = 50000;
int[] VetorA = new int[TAM1];
/*for (int i = 0; i < TAM1; i++)
{
VetorA[i] = i;
}*/
int a = 0;
for (int i = TAM1; i > 0; i--)
{
VetorA[a] = i;
a++;
}
/*for (int i = 0; i < TAM1; i++)
{
int a = r.Next();
VetorA[i] = a;
}
Imprimir(VetorA);*/
//Inicie o tempo
Stopwatch cronometroQuick = new Stopwatch();
cronometroQuick.Reset();
cronometroQuick.Start();
QuickSort(VetorA);
//Timing Parar
cronometroQuick.Stop();
//Escreve resultado
Console.WriteLine("QuickDecrescente - tam: {0} - Tempo decorrido: {1} - Ordenado?{2}", TAM1, cronometroQuick.Elapsed, CheckSort(VetorA));
writer.WriteLine("QuickDescrescnte - tam: {0} - Tempo decorrido: {1} - Ordenado?{2}", TAM1, cronometroQuick.Elapsed, CheckSort(VetorA));
writer.Flush();
writer.Close();
}
static void Main(string[] args)
{
foreach (int tam in new int[] {5000 })
{
Program p = new Program();
p.Ordenacao(tam);
Console.ReadKey();
}
}
}
}
Graciele de Deus Pereira
