Merge sort c

@_zerocool · 21 Απριλίου 2014

Καλησπέρα και χρόνια πολλά.

Δυσκολεύομαι σε ένα πρόγραμμα που έφτιαξα να ενσωματώσω και την merge sort. Μπορεί κανείς να μου εξηγήσει τι κάνω λάθος.

Σημείωση μόνο το σημείο με την merge sort δεν δουλεύει.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>

//Program to determine which algorithm is faster

void bubble_sort (int *table, int l);
void selection_sort (int *table,int l);
void print_table (int *table, int l);


void mergeSort(int numbers[], int *temp[], int array_size);
void m_sort(int numbers[], int *temp[], int left, int right);
void merge(int numbers[], int *temp[], int left, int mid, int right);

int main ()

{
int temp, i, j, N, pos; //for algorithms 

int *arrayFillpointer; //array declaration
int *arrayFillInitialpointer; //array declaration

int count=0; //counter for user interface
FILE *fp;
int t1, t2; //time measures
int s; //decision
int b; // second decision

fp = fopen ("data.txt", "a");


printf ("Give me the amount of numbers to fill the array: ");
scanf (" %d",&N);
printf ("Automated process for comparison:\n Press 1 for automation \n Press 0 for manual: ");
scanf ("%d",&s);
srand(time(NULL));

arrayFillpointer=(int *) malloc(N*sizeof(int));
arrayFillInitialpointer=(int *) malloc(N*sizeof(int));

int arrayFillInitial[N];
int arrayFill[N];

arrayFillpointer=arrayFill;

for (i = 0; i < N; i++) //fill array with numbers
	{
		arrayFill[i] = rand() % 1000;
	}
for (i = 0; i < N; i++) //fill array with numbers
	{
		arrayFillInitial[i] = arrayFill[i];
	}

	
if(s==1)
	{	
		
		//print_table (arrayFillpointer,N);
		t1=time(NULL);
		bubble_sort(arrayFillpointer,N);
		t2=time(NULL);
		fprintf (fp,"Bubble Sort Algorithm: %d \n",N);
		fprintf (fp,"Bubble Sort run for: %d \n", t2-t1);
		printf ("Bubble Sort run for: %d seconds \n", t2-t1);
		//print_table (arrayFillpointer,N);
		
		for (i = 0; i < N; i++) //fill array with numbers
		{
			arrayFill[i] = arrayFillInitial[i];
		}
		
		//print_table (arrayFillpointer,N);
		t1=time(NULL);
		selection_sort(arrayFillpointer,N);
		t2=time(NULL);
		fprintf (fp,"Selection Sort Algorithm: %d \n",N);
		fprintf (fp,"Selection Sort run for: %d \n", t2-t1);
		printf ("Selection Sort run for: %d seconds \n", t2-t1);
		//print_table (arrayFillpointer,N);
		
		for (i = 0; i < N; i++) //fill array with numbers
		{
			arrayFill[i] = arrayFillInitial[i];
		}
		
		//print_table (arrayFillpointer,N);
		t1=time(NULL);
		mergeSort(arrayFillpointer,N);
		t2=time(NULL);
		fprintf (fp,"Merge Sort Algorithm: %d \n",N);
		fprintf (fp,"Merge Sort run for: %d \n", t2-t1);
		printf ("Merge Sort run for: %d seconds \n", t2-t1);
		//print_table (arrayFillpointer,N);
	}
	else 
	{
		printf ("Please Select your algorithm:\n 1 for Bubble Sort and 2 for Selection Sort");
		scanf ("%d",&;
		switch(
		{
		case 1: 
			//print_table (arrayFillpointer,N);
			t1=time(NULL);
			bubble_sort(arrayFillpointer,N);
			t2=time(NULL);
			fprintf (fp,"Bubble Sort Algorithm: %d \n",N);
			fprintf (fp,"Bubble Sort run for: %d \n", t2-t1);
			printf ("Bubble Sort run for: %d seconds \n", t2-t1);
			//print_table (arrayFillpointer,N);
			break;
		case 2:
			//print_table (arrayFillpointer,N);
			t1=time(NULL);
			selection_sort(arrayFillpointer,N);
			t2=time(NULL);
			fprintf (fp,"Selection Sort Algorithm: %d \n",N);
			fprintf (fp,"Selection Sort run for: %d \n", t2-t1);
			printf ("Selection Sort run for: %d seconds \n", t2-t1);
			//print_table (arrayFillpointer,N);
			break;
		default:
			printf ("No valid selection Program terminating");
			break;
		}
	}
	
fclose(fp);
free(arrayFill);
free(arrayFillInitial);
return 0;
}

void bubble_sort (int *table, int l)
{
int i,j,temp,count;
				printf ("Loading Bubble Sort Algorithm for %d array elements...\n",l);
					for (i = 0 ; i <l-1; i++)
					  {
						for (j = l-1 ; j > i ; j--)
						{
						  if (table[j] < table[j-1]) 
						  {
							temp = table[j];
							table[j] = table[j-1];
							table[j-1] = temp;
							count++;
							if (count == 135000000)
							{
							printf("Still sorting please wait...\n");
							}
							if (count == 1300000000)
							{
							printf("Still sorting please wait...\n");
							}
							if (count == 1900000000)
							{
							printf("Still sorting please wait...\n");
							}
						  } 
						}
					  }	
}

void selection_sort (int *table,int l)
{
int i,j,count,temp,pos;
	printf ("Loading Selection Sort Algorithm for %d array elements...\n",l);
	count=0;
	for (i=0; i<l-1; i++) 
		{
			pos = i;
			for (j=i+1; j<l; j++)
				{
					if (table[pos] > table[j])
						{
							pos = j;
							/* swap */
							temp = table[pos];
							table[pos] = table[i];
							table[i] = temp;
							count++;
							if (count == 135000000)
								{
									printf("Still sorting please wait...\n");
								}
							if (count == 1300000000)
								{
									printf("Still sorting please wait...\n");
								}
							if (count == 1900000000)
								{
									printf("Still sorting please wait...\n");
								}
						}
					}
		}
}

void print_table (int *table, int l)
{
printf("Table: ");
int i;

for (i=0; i<l; i++)
	{
	printf("%d,",table[i]);
	}
printf(" \n\n");
}

void mergeSort(int numbers[], int *temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}
 
 
void m_sort(int numbers[], int *temp[], int left, int right)
{
  int mid;
 
  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);
 
    merge(numbers, temp, left, mid+1, right);
  }
}
 
void merge(int numbers[], int *temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;
 
  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;
 
  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }
 
  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }
 
  for (i=0; i <= num_elements; i++)
  {
    numbers[right] = temp[right];
    right = right - 1;
  }
}

imitheos · 21 Απριλίου 2014

Καλησπέρα και χρόνια πολλά.

Δυσκολεύομαι σε ένα πρόγραμμα που έφτιαξα να ενσωματώσω και την merge sort. Μπορεί κανείς να μου εξηγήσει τι κάνω λάθος.

Σημείωση μόνο το σημείο με την merge sort δεν δουλεύει.

Μακάρι να μην δούλευε μόνο αυτό

void mergeSort(int numbers[], int *temp[], int array_size);
void m_sort(int numbers[], int *temp[], int left, int right);
void merge(int numbers[], int *temp[], int left, int mid, int right);

Εδώ δηλώνεις ότι το δεύτερο όρισμα θα είναι πίνακας δεικτών σε ακέραιο ενώ οι κλήσεις σου δείχνουν ότι ήθελες ένα απλό δείκτη δηλαδή int *temp χωρίς τα άγκιστρα (ή αν θες διαφορετικά ένα απλό πίνακα int temp[] που είναι το ίδιο).

int *arrayFillpointer; //array declaration
int *arrayFillInitialpointer; //array declaration


arrayFillpointer=(int *) malloc(N*sizeof(int));
arrayFillInitialpointer=(int *) malloc(N*sizeof(int));

int arrayFillInitial[N];
int arrayFill[N];

arrayFillpointer=arrayFill;

Εφόσον ο αριθμός των στοιχείων δεν είναι από πριν γνωστός μπορείς είτε να χρησιμοποιήσεις VLAs ή δείκτες και να εκχωρήσεις μνήμη με την malloc. Εσύ για κάποιο λόγο κάνεις και τα δύο και μάλιστα βάζεις τον δείκτη να δείχνει στην VLA ενώ προηγούμενα του έχεις εκχωρήσει μνήμη με αποτέλεσμα να χάνεται εκείνη η μνήμη.

for (i = 0; i < N; i++) //fill array with numbers
{
arrayFill[i] = rand() % 1000;
}
for (i = 0; i < N; i++) //fill array with numbers
{
arrayFillInitial[i] = arrayFill[i];
}

Το σώμα του δεύτερου if δεν μπορεί να ενσωματωθεί στο πρώτο ?

if(s==1)
{
bubble_sort(arrayFillpointer,N);
selection_sort(arrayFillpointer,N);

Καλείς την συνάρτηση με όρισμα τον arrayFillpointer το οποίο δεν είναι λάθος μια και τον έχεις βάλει να δείχνει στον δυναμικό πίνακα arrayFill αλλά γιατί δεν περνάς κατευθείαν την arrayFill και να καταργήσεις τους δείκτες (ή αντίστοιχα να καταργήσεις τις VLA) ?

mergeSort(arrayFillpointer,N);

Η συνάρτηση δηλώνεται να έχει 3 ορίσματα ενώ εδώ έχεις παραλείψει τον πίνακα temp και την καλείς με δύο.

free(arrayFill);
free(arrayFillInitial);

Εδώ παίρνεις segmentation fault γιατί προσπαθείς να κάνεις free τους πίνακες αντί για τους δείκτες (και αν το αλλάξεις και βάλεις τους δείκτες, πάλι θα βαρέσει γιατί όπως είπαμε έχει αλλάξει τον ένα δείκτη και τον έχει βάλει να δείχνει στον πίνακα).

void selection_sort (int *table,int l)
{
for (i=0; i<l-1; i++) {
    pos = i;
    for (j=i+1; j<l; j++) {
        if (table[pos] > table[j]) {
            pos = j;
            temp = table[pos];
            table[pos] = table[i];
            table[i] = temp;
        }
    }
}
}

Βάζοντας να εμφανίζονται τα αποτελέσματα, η selection sort δεν έδωσε το σωστό αποτέλεσμα. Όταν βρίσκεις ότι το table[pos] είναι μεγαλύτερο αλλάζεις σωστά τον pos να έχει την τιμή j. Μετά όμως γιατί αλλάζεις τις τιμές ? Σε αυτό το σημείο πρέπει να θέσεις μόνο τον pos. Η αλλαγή θα γίνει αφού έχει τελειώσει όλο το for(j) δηλαδή μέσα στο σώμα του for(i) και τότε το αποτέλεσμα μου το έβγαλε σωστά.

Όλα τα προβλήματα που είχες στην merge sort δεν θα υπήρχαν αν καθόσουν λίγο να ασχοληθείς με το πως δουλεύει ο αλγόριθμος και να να γράψεις τις συναρτήσεις αντί να τις πάρεις αυτολεξί από εδώ ή κάποιο παρόμοιο link.

@_zerocool · 21 Απριλίου 2014

Καταρχήν σε ευχαριστώ πολύ. Πάω να επεξεργαστώ αυτά που μου είπες και να σου εξηγήσω τι έκανα και που και επανέρχομαι.

@_zerocool · 23 Απριλίου 2014

Με βάση αυτά που μου πρότεινες έκανα κάποιες διορθώσεις. Για δες:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>

//Program to determine which algorithm is faster
void bubble_sort (int *table, int l);
void selection_sort (int *table,int l);
void print_table (int *table, int l);
void mergeSort(int *temp, int array_size);
void m_sort(int *numbers, int left, int right);
void merge(int *numbers, int left, int mid, int right);

int main ()
{
int temp, i, j, N, pos; //for algorithms 
int *arrayFillpointer; //array declaration
int *arrayFillInitialpointer; //array declaration
int count=0; //counter for user interface
FILE *fp;
int t1, t2; //time measures
int s; //decision
int b; // second decision
fp = fopen ("data.txt", "a");

printf ("Give me the amount of numbers to fill the array: ");
scanf (" %d",&N);
printf ("Automated process for comparison:\n Press 1 for automation \n Press 2 for manual: ");
scanf ("%d",&s);
srand(time(NULL));
arrayFillpointer= malloc(N*sizeof(int));
arrayFillInitialpointer= malloc(N*sizeof(int));
for (i = 0; i < N; i++) 
	{
		arrayFillpointer[i] = rand() % 1000; //fill array with  random numbers
		arrayFillInitialpointer[i] = arrayFillpointer[i]; //copy array to maintain original randomness
	}
	
if(s==1)
	{	
		//print_table (arrayFillpointer,N);
		t1=time(NULL);
		bubble_sort(arrayFillpointer,N);
		t2=time(NULL);
		fprintf (fp,"Bubble Sort Algorithm: %d \n",N);
		fprintf (fp,"Bubble Sort run for: %d \n", t2-t1);
		printf ("Bubble Sort run for: %d seconds \n", t2-t1);
		//print_table (arrayFillpointer,N);
		
		for (i = 0; i < N; i++) //fill array with numbers
		{
			arrayFillpointer[i] = arrayFillInitialpointer[i];
		}
		
		//print_table (arrayFillpointer,N);
		t1=time(NULL);
		selection_sort(arrayFillpointer,N);
		t2=time(NULL);
		fprintf (fp,"Selection Sort Algorithm: %d \n",N);
		fprintf (fp,"Selection Sort run for: %d \n", t2-t1);
		printf ("Selection Sort run for: %d seconds \n", t2-t1);
		//print_table (arrayFillpointer,N);
		
		for (i = 0; i < N; i++) //fill array with numbers
		{
			arrayFillpointer[i] = arrayFillInitialpointer[i];
		}
		
		//print_table (arrayFillpointer,N);
		t1=time(NULL);
		mergeSort(arrayFillpointer,N);
		t2=time(NULL);
		fprintf (fp,"Merge Sort Algorithm: %d \n",N);
		fprintf (fp,"Merge Sort run for: %d \n", t2-t1);
		printf ("Merge Sort run for: %d seconds \n", t2-t1);
		//print_table (arrayFillpointer,N);
	}
else 
	{
		printf ("Please Select your algorithm:\n1 for Bubble Sort\n2 for Selection Sort\n3 for Merge sort\n");
		scanf ("%d",&;
		switch(
		{
		case 1: 
			//print_table (arrayFillpointer,N);
			t1=time(NULL);
			bubble_sort(arrayFillpointer,N);
			t2=time(NULL);
			fprintf (fp,"Bubble Sort Algorithm: %d \n",N);
			fprintf (fp,"Bubble Sort run for: %d \n", t2-t1);
			printf ("Bubble Sort run for: %d seconds \n", t2-t1);
			//print_table (arrayFillpointer,N);
			break;
		case 2:
			//print_table (arrayFillpointer,N);
			t1=time(NULL);
			selection_sort(arrayFillpointer,N);
			t2=time(NULL);
			fprintf (fp,"Selection Sort Algorithm: %d \n",N);
			fprintf (fp,"Selection Sort run for: %d \n", t2-t1);
			printf ("Selection Sort run for: %d seconds \n", t2-t1);
			//print_table (arrayFillpointer,N);
			break;
		case 3:
			print_table (arrayFillpointer,N);
			t1=time(NULL);
			mergeSort(arrayFillpointer,N);
			t2=time(NULL);
			fprintf (fp,"Merge Sort Algorithm: %d \n",N);
			fprintf (fp,"Merge Sort run for: %d \n", t2-t1);
			printf ("Merge Sort run for: %d seconds \n", t2-t1);
			print_table (arrayFillpointer,N);
			break;
		default:
			printf ("No valid selection Program terminating");
			break;
		}
	}
	
fclose(fp);
//free(arrayFill);
//free(arrayFillInitial);
return 0;
}

void bubble_sort (int *table, int l)
{
int i,j,temp,count;
				printf ("Loading Bubble Sort Algorithm for %d array elements...\n",l);
					for (i = 0 ; i <l-1; i++)
					  {
						for (j = l-1 ; j > i ; j--)
						{
						  if (table[j] < table[j-1]) 
						  {
							temp = table[j];
							table[j] = table[j-1];
							table[j-1] = temp;
							count++;
							if (count == 135000000)
							{
							printf("Still sorting please wait...\n");
							}
							if (count == 1300000000)
							{
							printf("Still sorting please wait...\n");
							}
							if (count == 1900000000)
							{
							printf("Still sorting please wait...\n");
							}
						  } 
						}
					  }	
}

void selection_sort (int *table,int l)
{
int i,j,count,temp,pos;
	printf ("Loading Selection Sort Algorithm for %d array elements...\n",l);
	count=0;
	for (i=0; i<l-1; i++) 
		{
			pos = i;
			for (j=i+1; j<l; j++)
				{
					if (table[pos] > table[j])
						{
							pos = j;
						}
				}
			/* swap */
			temp = table[pos];
			table[pos] = table[i];
			table[i] = temp;
			count++;
			if (count == 135000000)
			{
			printf("Still sorting please wait...\n");
			}
			if (count == 1300000000)
			{
			printf("Still sorting please wait...\n");
			}
			if (count == 1900000000)
			{
			printf("Still sorting please wait...\n");
			}
		}
}

void print_table (int *table, int l)
{
printf("Table: ");
int i;

for (i=0; i<l; i++)
	{
	printf("%d,",table[i]);
	}
printf(" \n\n");
}


void mergeSort(int *numbers, int array_size)
{
  printf ("Loading Merge Sort Algorithm for %d array elements...\n",array_size);
  m_sort(numbers, 0, array_size - 1);
}
 
  
  void m_sort(int *numbers, int left, int right)
{
  int mid;
 
  if (left < right)
  {
    mid = (right + left) / 2;
    m_sort(numbers, left, mid);
    m_sort(numbers, mid+1, right);
 
    merge(numbers, left, mid, right);
  }
}

 
void merge(int *numbers, int left, int mid, int right)
{
  int B[right-left+1]; //temp table
    int i=left, k=0; 
    int j=mid+1;
    while (i <= mid && j <= right) 
        if (numbers[i] <= numbers[j]) 
            B[k++] = numbers[i++];
        else
            B[k++] = numbers[j++];
        
        while (i <= mid)
            B[k++] = numbers[i++];

        while (j <= right)
            B[k++] = numbers[j++];
			
		for (i=left; i <= right; i++) //copy temp table to original table
		numbers[i] = B[i-left];
}

imitheos · 23 Απριλίου 2014

Με βάση αυτά που μου πρότεινες έκανα κάποιες διορθώσεις. Για δες:
arrayFillpointer= malloc(N*sizeof(int));
arrayFillInitialpointer= malloc(N*sizeof(int));
//free(arrayFill);
//free(arrayFillInitial);

Εφόσον αποφάσισες να δουλέψεις με δείκτες αντί για VLAs, τότε οι κλήσεις της free πρέπει να εκτελεστούν. Εφόσον το πρόγραμμα τελειώνει έτσι και αλλιώς μετά τις free δεν έγινε και τίποτα γιατί το λειτουργικό θα επανακτήσει την μνήμη αλλά είθισται να υπάρχει μία free για κάθε μία malloc.

Δεν κοίταξα τον κώδικα τον συναρτήσεων για να δω αν όντως υλοποιούν τον εκάστοτε αλγόριθμο αλλά οι τιμές εμφανίζονταν ταξινομημένες οπότε υποθέτω δουλεύουν καλά.

παπι · 24 Απριλίου 2014

Μα γιατι δεν τους μαθαινουν καποιο IDE;;;;;;;;;;

Kercyn · 24 Απριλίου 2014

count++;
            if (count == 135000000)
            {
            printf("Still sorting please wait...\n");
            }
            if (count == 1300000000)
            {
            printf("Still sorting please wait...\n");
            }
            if (count == 1900000000)
            {
            printf("Still sorting please wait...\n");
            }

Τι είναι αυτά;

παπι · 24 Απριλίου 2014

Υποτιθεται progress "status".

Kercyn · 24 Απριλίου 2014

Ναι αλλά γράφουν όλα το ίδιο

Και τι διάλο τι μεγέθη έχουν οι πίνακες;

@_zerocool · 24 Απριλίου 2014

ναι status. Έχεις κάποιον άλλον τρόπο καλύτερο; Ποιο IDE προτείνεις;

Kercyn · 24 Απριλίου 2014

Θα μπορούσες να γράφεις μια φορά "sorting data" ή κάτι τέτοιο έξω απ' το loop. Για C εγώ χρησιμοποιούσα το Pelles C.

παπι · 24 Απριλίου 2014

ναι status. Έχεις κάποιον άλλον τρόπο καλύτερο; Ποιο IDE προτείνεις;

Προτασεις για C δεν εχω. Συχαινομαι αυτη τη γλωσσα. Αλλα το IDE ειναι αρκετα γενικο, τοσο γενικο που εαν μαθεις καποιο, τοτε δεν θα εχεις κανενα προβλημα να μεταπηδησεις σε καποιο αλλο.

imitheos · 24 Απριλίου 2014

		for (i = 0; i < N; i++) //fill array with numbers
		{
			arrayFillpointer[i] = arrayFillInitialpointer[i];
		}

Κάθε φορά που έγραφα ξεχνούσα να αναφέρω να διαβάσεις την βοήθεια της συνάρτησης memcpy.

ναι status. Έχεις κάποιον άλλον τρόπο καλύτερο; Ποιο IDE προτείνεις;

Ένας μπακάλικος και εύκολος τρόπος είναι να τυπώνεις εναλλάξ κάποιο ascii χαρακτήρα. Οι κλασσικοί είναι \ - | / ώστε να δημιουργείται το εφέ μιας γραμμής που γυρνάει γύρω-γύρω.

Προτασεις για C δεν εχω. Συχαινομαι αυτη τη γλωσσα. Αλλα το IDE ειναι αρκετα γενικο, τοσο γενικο που εαν μαθεις καποιο, τοτε δεν θα εχεις κανενα προβλημα να μεταπηδησεις σε καποιο αλλο.

Διώξτε το κύριο είναι μπασκετάκιας

Σύνδεση

Merge sort c

Προτεινόμενες αναρτήσεις

@_zerocool

imitheos

@_zerocool

@_zerocool

imitheos

παπι

Kercyn

παπι

Kercyn

@_zerocool

Kercyn

παπι

imitheos

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

Σύνδεση