Προς το περιεχόμενο

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

nikosvas

Από τον nikosvas
στο Προγραμματισμός

 Share

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

nikosvas Proficient

nikosvas

Δημοσ.
Δημοσ.

Γειά σας καταρχήν. Έχω μία εργασία να κάνω τον bubbleshort στον οποίο μετά από κάθε loop να μειώνεται ο αριθμός των συγκρίσεων και να υπάρχει ένας φρουρός έτσι ώστε όταν δεν υπάρχει swap να σταματά ο αλγόριθμος. Τον τρέχω και δεν κάνει σωστά την ταξινόμιση. Μήπως φταίει η Boolean μεταβλητή swap?

 

 

>


include <stdio.h>
#include <stdbool.h>

#define SIZE 10

void bubblesort(int pin[],int n);

int main()
{

int a[size]= {12,1,3,4,2,19,40,8,5,5};
printf("Before sorting");
for(int i=0;i<SIZE;i++)
{
printf(" value  %d index %d \n",a[i],i);
}//END FOR

bubblesort(a,SIZE);
printf("After sorting");

for(int i=0;i<SIZE;i++)
{
printf(" value  %d index %d \n",a[i],i);
} //END FOR


} //END MAIN



void bubblesort(int pin[],int n)
{
   int i;
   int j;
   bool swap=true;
   int temp;

   for(i=0; swap && i<n-1;i++)
       {
           swap=false;
       }

       for(j=0;j<n-i-1;j++)
           if(pin[j]>pin[j+1]) {
               temp=pin[j];
           pin[j]=pin[j+1];
           pin[j+1]=temp;
           swap=true;
}


}

akisk Veteran

akisk

Δημοσ.
Δημοσ.

Στην 1η for του bubblesort τι ακριβώς κάνεις;

 

Δεν είναι απαραίτητη η χρήση boolean μεταβλητής.

 

>void bubblesort(int pin[],int n)
{
   int j;
   int t = -1; //πλήθος εναλλαγών σε κάθε πέρασμα
   int temp;

   while(i >= 2 && t != 0)
   {
       t = 0;
for (j = 1; j < n; j++)
{
    if (pin[j] > pin[j+1])
    {
	temp = pin[j];
	pin[j] = pin[j+1];
	pin[j+1] = temp;
	t++;
    }
}
n--;
   }
}

nilosgr Mentor

nilosgr

Δημοσ.
Δημοσ. (επεξεργασμένο)

Κατ αρχήν δεν είναι quicksort. Κατά δεύτερον στη βιβλιοθήκη stdbool δεν ορίζεται ο τύπος bool ορίζεται κάποιος άλλος (που καλύτερα να τον 'ανακαλύψεις' μόνος σου). Το bool δουλεύει επειδή είναι στη C++

Ο κώδικας δεν λειτουργεί σωστά επειδή δεν έχεις βάλει αγκύλες {} εκεί που πρέπει...

Επεξ/σία από nilosgr
Star_Light Mentor

Star_Light

Δημοσ.
Δημοσ.

Κατ αρχήν δεν είναι quicksort. Κατά δεύτερον στη βιβλιοθήκη stdbool δεν ορίζεται ο τύπος bool ορίζεται κάποιος άλλος (που καλύτερα να τον 'ανακαλύψεις' μόνος σου). Το bool δουλεύει επειδή είναι στη C++

Ο κώδικας δεν λειτουργεί σωστά επειδή δεν έχεις βάλει αγκύλες {} εκεί που πρέπει...

 

Σωστα στην stdbool ο _Bool ορίζεται. (C99)

 

>
#include<stdio.h>
#include<stdbool.h>

int main(void)
{

_Bool x= 5;

printf("x is %d\n" , x);  // Boolean 0 or 1 value only.On this case print 1  

return 0;

}

migf1 Mentor

migf1

Δημοσ.
Δημοσ.

Και ο bool ορίζεται στο <stdbool.h> (ως macro που γίνεται expand σε _Bool).

 

Οπότε μπορεί κάλλιστα να χρησιμοποιηθεί αντί για _Bool ;)

nilosgr Mentor

nilosgr

Δημοσ.
Δημοσ.

Και ο bool ορίζεται στο <stdbool.h> (ως macro που γίνεται expand σε _Bool).

 

Οπότε μπορεί κάλλιστα να χρησιμοποιηθεί αντί για _Bool ;)

Ειχα την εντπωση οτι ηταν BOOL <_<

Anubis13 Grand Master

Anubis13

Δημοσ.
Δημοσ.

Αυτο ειναι bubblesort και ακομα και με το guard γυρναει σε N^2

Ενας τροπος να υλοποιησεις το guard ειναι int flag = 0;

flag = 1; και οπου χρειαζεται αναλογος ελεγχος.

akisk Veteran

akisk

Δημοσ.
Δημοσ.

Κατ αρχήν δεν είναι quicksort. Κατά δεύτερον στη βιβλιοθήκη stdbool δεν ορίζεται ο τύπος bool ορίζεται κάποιος άλλος (που καλύτερα να τον 'ανακαλύψεις' μόνος σου). Το bool δουλεύει επειδή είναι στη C++

Ο κώδικας δεν λειτουργεί σωστά επειδή δεν έχεις βάλει αγκύλες {} εκεί που πρέπει...

Βασικά απλώς λείπει το # στο πρώτο define του.

 

Αυτο ειναι bubblesort και ακομα και με το guard γυρναει σε N^2

Ενας τροπος να υλοποιησεις το guard ειναι int flag = 0;

flag = 1; και οπου χρειαζεται αναλογος ελεγχος.

Περίπου αυτό του έδειξα στο 2ο ποστ με την μεταβλητή t που μετράει τις εναλλαγές!

Πάντως στο best case scenario θέλει Ο(Ν) :mrgreen:

Anubis13 Grand Master

Anubis13

Δημοσ.
Δημοσ.

Βασικά απλώς λείπει το # στο πρώτο define του.

 

 

Περίπου αυτό του έδειξα στο 2ο ποστ με την μεταβλητή t που μετράει τις εναλλαγές!

Πάντως στο best case scenario θέλει Ο(Ν) :mrgreen:

 

Ναι μετα ειδα το ποστ σου..Δεν πειραζει εγω ηθελα να δωσω μονο την ιδεα και οχι τον κωδικα. Ποτε δεν μας αρεσει το best-case σεναριο αλλα δεν νομιζω οτι ειναι αλγοριθμικης φυσεως το θεμα παρα μια απλη ασκηση σε C.

nikosvas Proficient

nikosvas

Δημοσ.
  • Μέλος
Δημοσ.

Καταρχήν όπως λέτε είναι βελτιστοποίηση του bubblesort. Τώρα προσπαθώ να προσθέσω ένα counter για να μετράει τα swaps. Πιστεύετε όπως το έκανα είναι σωστό? Επίσης θέλω να αξιολογήσω τους αλγορίθμους insertion sort, quicksort και bubblesort. Το πρόβλημα είναι ότι

όταν τρέχω τους αλγορίθμους για 1.000.000 στοιχεία μου "κρασάρει" το πρόγραμμα. Τι πιστέυετε ότι φτάει?

 

>
#include <stdbool.h>
#include <stdio.h>
#define SIZE 10

int bubblesort(int pin[],int n,int swapCounter);

int main()
{
int swapCounter=0;
int var;
int a[size]= {12,1,3,4,2,19,40,8,5,5};
printf("Before sorting");
for(int i=0;i<SIZE;i++)
{
printf(" value  %d index %d \n",a[i],i);
}//END FOR

var= bubblesort(a,SIZE,swapCounter);
printf("After sorting");

for(int i=0;i<SIZE;i++)
{
printf(" value  %d index %d \n",a[i],i);
} //END FOR
printf("bubble sort makes %d swaps",var);

} //END MAIN



int bubblesort(int pin[],int n,int swapC)
{
int i;
int j;
bool swap=true;
int temp;

for(i=0; swap && i<n-1;i++)
	{
		swap=false;


	for(j=0;j<n-i-1;j++)
		if(pin[j]>pin[j+1]) {
			//arxizei swap
			temp=pin[j];
		pin[j]=pin[j+1];
		pin[j+1]=temp;
		++swapC;
		//telos swap
		swap=true;
}//end if
}//end for
return swapC;

}

 

Όπως όρισα την συνάρτηση quicksort

>

int quicksort (int a[], int lo, int hi,int swapC) //to swapC einai counter
{
//  lo is the lower index, hi is the upper index
//  of the region of array a that is to be sorted
   int i=lo, j=hi, h;

   // comparison element x
   int x=a[(lo+hi)/2];

   //  partition
   do
   {

	while (a[i]<x)
		i++;
       while (a[j]>x)
	    j--;

       if (i<=j)
       {
           h=a[i];
		a[i]=a[j];//swaping
	    a[j]=h;

		++swapC;

           i++; j--;
       }
   } while (i<=j);

   //  recursion
   if (lo<j) quicksort(a, lo, j,swapC);
   if (i<hi) quicksort(a, i, hi,swapC);

return swapC;
}

 

Όπως όρισα τον insertion sort

 

 

>

int insertionSort(int pin[],int n,int swapC)
{

int j;
int i;
int temp;
for(j=1;j<n;j++)
	{
	i=j-1;
    temp=pin[j];
		while((temp<pin[i]) && (i>=0)) {//arxiei swap
			pin[i+1]=pin[i];
			i--;
			++swapC;
		}//end while

	}//end for
return swapC;

}

migf1 Mentor

migf1

Δημοσ.
Δημοσ.

...

Επίσης θέλω να αξιολογήσω τους αλγορίθμους insertion sort, quicksort και bubblesort. Το πρόβλημα είναι ότι

όταν τρέχω τους αλγορίθμους για 1.000.000 στοιχεία μου "κρασάρει" το πρόγραμμα. Τι πιστέυετε ότι φτάει?

...

Πως τα ορίζεις αυτά τα 1.000.000 στοιχεία; Αν τα ορίζεις σε στατικό πίνακα, το πιθανότερο είναι να εξαντλείς το stack-space... δοκίμασε να τα ορίζεις σε πίνακα που τον δημιουργείς δυναμικά με malloc() (και τον κάνεις free() όταν τελειώνεις).

 

ΥΓ. Δεν έχω αυτή τη στιγμή την ευχέρεια να κοιτάξω τον κώδικά σου (συν ότι είναι αλλοπρόσαλλα στοιχισμένος, οπότε δύσκολο να ευκαιρήσω να τον κοιτάξω, γενικώς :P )

.

nikosvas Proficient

nikosvas

Δημοσ.
  • Μέλος
Δημοσ.

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

 

>
#include <stdbool.h>
#include <stdio.h>
#define SIZE 10

int bubblesort(int pin[],int n,int swapCounter);

int main()
{
int swapCounter=0;
int var;
int a[size]= {12,1,3,4,2,19,40,8,5,5};
printf("Before sorting");
for(int i=0;i<SIZE;i++)
{
printf(" value  %d index %d \n",a[i],i);
}//END FOR

var= bubblesort(a,SIZE,swapCounter);
printf("After sorting");

for(int i=0;i<SIZE;i++)
{
printf(" value  %d index %d \n",a[i],i);
} //END FOR
printf("bubble sort makes %d swaps",var);

} //END MAIN



int bubblesort(int pin[],int n,int swapC)
{
       int i;
       int j;
       bool swap=true;
       int temp;

       for(i=0; swap && i<n-1;i++)
               {
                       swap=false;


               for(j=0;j<n-i-1;j++)
                       if(pin[j]>pin[j+1]) {
                               //arxizei swap
                               temp=pin[j];
                       pin[j]=pin[j+1];
                       pin[j+1]=temp;
                       ++swapC;
                       //telos swap
                       swap=true;
}//end if
}//end for
return swapC;

}

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

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

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

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!

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

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
 Share
Προς την λίστα θεμάτων
  • Δημιουργία νέου...