Βελτιστοποίηση quicksort

[migf1]

Φίλε μου, ουσιαστικά μου ζητάς να σου κάνω debug τον κώδικά σου, αλλά για αυτές τις δουλειές υπάρχουν οι debuggers.

 

Οπότε, ενεργοποίησε το debug flag σε όποιον compiler χρησιμοποιείς και κάνε το trace με τον debugger σου Αν είσαι με gcc, το debug flag είναι: -g3 (και debugger είναι ο: gdb).

[nikosvas]

Γειά σας. Έχω ένα πρόβλημα με τον mergesort. Θέλω να μετρήσω τα swaps αλλά δεν ξέρω που να βάλω τον counter.Ευχαριστώ.

>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SIZE 100

void mergesort(int a[], int low, int high);
void merge(int a[],int left,int right);
int main()
{
int a[size];
int r;


for(int i=0;i<SIZE;i++)
{
	r=rand();
}


mergesort(a,0,SIZE);

for(int i=0;i<SIZE;i++) //diatrexoume ton pinaka
{
	printf(" \nAfter sorting with mergesort  index %d value %d \n",i,a[i]);
}

}










void mergesort(int a[], int low, int high)
{
int mid;
if(low<high)
{
mid=((low+high)/2);
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high);
}

}

void merge(int a[],int left,int right)
{

 int mid=((left+right)/2);
 int i=0;
 int j=left;
 int k=mid+1;

 int temp[right-left+1]; //prosorinios pisnaks

 //merge array
 while(j<=mid &&k<=right)
	 if(a[j]<a[k])
		 temp[i++]=a[j++];
	 else
		 temp[i++]=a[k++];

	 while(j<=mid)
		 temp[i++]=a[j++];

	 while(k<=right)
		 temp[i++]=a[k++];

	 //ekxoroume ta stoixeio apo ton prosotrino pinaka
	 //ston pinaka stin main
    for(int i=left;i<=right;i++)
		{
		a[i]=temp[i-left];
		}
}

[akisk]

>
for(int i=0;i<SIZE;i++)
       {
               r=rand();
       }

Εδώ κατάλαβες τι έγινε; Βάζεις στο r τυχαίους αριθμούς. Γιατί;;

 

Στη συνέχεια γράφεις

>mergesort(a,0,SIZE);

μόνο που ο a έχει μέσα σκουπίδια και όχι τους random.

 

Αυτό που θέλεις να κάνεις είναι το εξής:

 

>int main()
{       
int i, a[size];

srand((unsigned)time(NULL));

for(i = 0; i < SIZE; i++)
              a[i] = rand();

mergesort(a,0,SIZE);

       for(i = 0; i < SIZE; i++) //diatrexoume ton pinaka
               printf(" \nAfter sorting with mergesort  index %d value %d \n",i,a[i]);
}

 

 

Όσο για τον counter, μια λύση θα ήταν να αλλάξεις τις merge και mergesort από void σε int και να επιστρέφεις τις εναλλαγές με αυτό τον τρόπο στη main.

[nikosvas]

Τον counter τον έκανα έτσι. Πιστέυετε ότι μετράει σωστά τα swaps που όρισα την swapCount καθολική?

>


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SIZE 100

int swapCount=0;


void mergesort(int a[], int low, int high);
void merge(int a[],int left,int right);
int main()
{
int a[size];
int r;
int var;

for(int i=0;i<SIZE;i++)
{
	r=rand();
}

clock_t start;
clock_t diff;
clock_t end;
start= clock();

mergesort(a,0,SIZE);

end = clock();
diff = end - start;

for(int i=0;i<SIZE;i++) //diatrexoume ton pinaka
{
	printf(" \nAfter sorting with mergesort  index %d value %d \n",i,a[i]);
}

printf("Swaps apo merge is %d\n",swapCount);

}










void mergesort(int a[], int low, int high)
{
int mid;
if(low<high)
{
//find middle elemenr
mid=((low+high)/2);
//sort first half
mergesort(a,low,mid);
//sort second one
mergesort(a,mid+1,high);
//merge the halves
merge(a,low,high);
}

}

void merge(int a[],int left,int right)
{

// //input=a  //left=p //right=r
 //i1=i  i2=j  i3=k
 //temp=temp
 int mid=((left+right)/2);
 int i=0;
 int j=left;
 int k=mid+1;

 int temp[right-left+1]; //prosorinios pisnaks

 //merge array
 while(j<=mid &&k<=right)
	 if(a[j]<a[k]){
		 swapCount++; //metrame swaps
		 temp[i++]=a[j++];
		}
	 else{
		 temp[i++]=a[k++];
		  swapCount++;
            }
	 while(j<=mid)
		 temp[i++]=a[j++];
	     swapCount++;

	 while(k<=right)
		 temp[i++]=a[k++];
            swapCount++;
	 //ekxoroume ta stoixeio apo ton prosotrino pinaka
	 //ston pinaka stin main
    for(int i=left;i<=right;i++)
		{
		a[i]=temp[i-left];
		}

}

[nilosgr]

Πεντε συμβουλες:

1. 
    
   
2. Ακου τις συμβουλες των προηγουμενων
   
3. Μην κανεις κολαζ τους κωδικες που βρισκεις απ το google
   
4. Διαβασε την λογικη του αλγοριθμου και γραψε εσυ κωδικα μονος σου
   
5. Τρεξε απλα παραδειγματα στο "χαρτι"
   
6. Συγκρινε τα αποτελεσματα του 3 και του 4, αν ειναι ιδια τελος, αλλιως πηγαινε στο 3