2016-03-28 18 views
-4

Zaman karmaşıklığını karşılaştırmak için büyük girişler için sayma sıralamalarını uygulamak istedim. Aşağıdaki kodu yazdım. (int boyutu = 50; boyut < = 500; beden = beden + 100) gibi küçük girdiler için iyi çalışır, ancak boyut boyutunu artırdığımda (int boy = 10000; boyut < = 100000; beden = boyut + 50000) Doğru çıktı alınamıyor. yardımına ihtiyacım var.Büyük veri kümesi için sayma türü çalışmıyor

#include <iostream> 
#include<ctime> 
#include<cstdlib> 
#include<iomanip> 
using namespace std; 
void counting_sort(int a[], int size) 
{ 
int i, j, k; 
int idx = 0; 
int low, high; 

low = high = a[0]; 
for(i = 1; i < size; i++) 
    { 
low = (a[i] < low) ? a[i] : low; 
high = (a[i] > high) ? a[i] : high; 
} 

k = high - low + 1; 
int *c = new int [k]; 
for(i = 0; i < k; i++) c[i] = 0; 
for(i = 0; i < size; i++) c[a[i] - low]++; 
for(i = low; i <= high; i++) 
    for(j = 0; j < c[i - low]; j++) a[idx++] = i; 
      for (int i = 0; i < size; i++) 
      { 
     cout << a[i] << " "; 
      } delete [] c; 
    } 

    int main() 
    { 
      srand(time(0)); 
      int*a; 
      double t1, t2; 
      for(int size = 50; size<=500; size= size+100) 
      { 
      a= new int[size]; 
       for(int i=0;i<size;i++) 
      { 
       a[i]=rand()%10000; 
      } 
      t1=clock(); 
      counting_sort(a, size-1); 
      t2=clock(); 
      cout << setw(10) << (t2 - t1)/CLK_TCK << "sec\n" << endl; 
      delete[]a; 
     } 

} 
+1

_Aşağıdaki diğer bir sorun da ..._ - "başka bir sorun" ayrı bir soru gönderisinin sebebidir, lütfen birbirleriyle alakasız şeyleri bir araya getirmeyin. Yine de, diğer bir problemle ilgili olarak, 't1' (eğer bir 't1 = clock() ile;' 'counting_sort()' 'a çağırmadan hemen önce onu ilan edip, asla ayarlamayacaksanız, sonuçların nasıl görüneceğini merak ediyorum. o. – mah

cevap

0

Ideone problem. Visual Studio tamam çalışıyor. Ayrıca, , değil size-1

+0

Yanıtladığınız için teşekkürler, ancak boyut veya beden-1 kullanıldığında değişiklik yapılmadı. –

+0

IDE'nin değiştirilmesi değişiklik yapar. Genel olarak kod tamam. 'size-1', __ için uygun olan herhangi bir değişiklik yapmazsınız, ancak çıktı dosyasındadırlar. – aaalex88

İlgili konular