Ερωτήσεις για C

Star_Light · 16 Νοεμβρίου 2012

Να κανω μια ερωτηση σχετικα με τον Bubble sort?

>
#include <stdio.h>
void bubble_sort(int []);
#define LEN 10

int main( void )
{

 int array[LEN] = { 5 , 1 , 4 , 2 , 7 , 6 , 3 , 0 , 12 , -3 } , counter =0 ;

 printf(" Before sorting ");

 for(; counter<LEN; counter++)
 printf(" %d " , array[counter]);

 bubble_sort(array);

 printf(" After sorting ");

 counter = 0;

 while( counter < LEN )
 {
 printf(" %d " , array[counter]);
 counter++;
}

 return 0;
}
void bubble_sort(int array[])
{
int i, j, temp;

for (i = (LEN - 1); i > 0 ; i--)
{
for (j = 1; j <= i; j++)
{

 if (array[j-1] > array[j])
 {
 temp = array[j-1];
 array[j-1] = array[j];
 array[j] = temp;
 }

}
}
return;
}

Εφοσον οι συγκρισεις γινονται με ολα τα στοιχεια του πινακα καθε φορα.... οπως λεει και στην Wiki

and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared.

http://en.wikipedia....iki/Bubble_sort

Εχω την εντυπωση ωστοσο οτι ο παραπανω κωδικας δεν το κανει αυτο...... ειδικα οταν το i μειωνεται σε 3 και στο εσωτερικο loop δεν μπαινει για j = 4 αρα και το array[4] δεν συγκρινεται με το array[3]. Εκτος και αν εχω καταλαβει λαθος τον αλγοριθμο. Πραγμα πιθανο οπως αρχιζω να υποπτευομαι.

P.S Ο αριθμος που θα διατρέξουμε την λιστα χωρις τον αριθμο των συγκρισεων των ζευγαριων δεν ειναι στανταρ εξαρχης ετσι?

P.S2 Αν ειναι δυνατον να τρωμε ηττα στον bubble sort

ZAKKWYLDE · 17 Νοεμβρίου 2012

Έχεις κάνει νομίζω ένα λίγο περίεργο BubbleSort. Έχω την εντύπωση πως h wikipedia εννοεί κάτι του στυλ:

>
void sort(int *a) {
   int temp = 0;
   for (int i = 0; i < alength; i++) {
       for (int j = i; j < alength; j++) {
          if (a[i] > a[j]) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
          }
      }
   }
}

Star_Light · 17 Νοεμβρίου 2012

Έχεις κάνει νομίζω ένα λίγο περίεργο BubbleSort. Έχω την εντύπωση πως h wikipedia εννοεί κάτι του στυλ:
>
void sort(int *a) {
int temp = 0;
for (int i = 0; i < alength; i++) {
for (int j = i; j < alength; j++) {
if (a[i] > a[j]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}

Οχι η συνάρτηση που υλοποιει τον αλγοριθμο ειναι ενταξει. Απλα ειναι η βελτιωμένη έκδοση που βοηθα να γινουν λιγοτεροι έλεγχοι αλλα οχι και λιγοτερες αντιμεταθεσεις. Ψαχνω απλα να βρω πως θα διαμορφωνεται το εξωτερικο loop που εχει να κάνει με τα περάσματα - φάσεις ... πχ αν ειναι γνωστο εκ των προτερων το σε ποσες φάσεις θα σταματήσει ο αλγοριθμος την δουλεια του ή απλα βάζουμε εμεις μέχρι το μέγιστο μηκος πίνακα.

ChRis6 · 17 Νοεμβρίου 2012

>
void bubble_sort( int a[] , int left , int right ){
int temp;

 for( int i = left ; i < right ; i++ ){
   for( int j = right ; j < i ; j-- ){

  if( a[j] < a[j - 1]){
    temp = a[j-1];
    a[j-1] = a[j];
    a[j] = temp;
  }
   }
 }
}

Για να κάνεις λιγότερους ελέγχους πρέπει να είσαι σίγουρος οτι δεν χρειάζονται.Δηλαδή ακόμα και όταν είναι ταξινομημένος ο πίνακας,πάλι θα κάνεις συγκρίσεις. Στη μέση περίπτωση χρειάζεται n^2 / 2 συγκρίσεις , ενώ στη χειρότερη n* ( n - 1 )/2 .

Αν σε κάποια επανάληψη δεν φτάσει το πρόγραμμα στο if, τότε ο πίνακας είναι ταξινομημένος.

Star_Light · 17 Νοεμβρίου 2012

>
void bubble_sort( int a[] , int left , int right ){
int temp;

for( int i = left ; i < right ; i++ ){
for( int j = right ; j < i ; j-- ){

 if( a[j] < a[j - 1]){
 temp = a[j-1];
 a[j-1] = a[j];
 a[j] = temp;
 }
}
}
Για να κάνεις λιγότερους ελέγχους πρέπει να είσαι σίγουρος οτι δεν χρειάζονται.Δηλαδή ο αλγόριθμος ακόμα και όταν είναι ταξινομημένος ο πίνακας,πάλι θα κάνει συγκρίσεις. Στη μέση περίπτωση χρειάζεται n^2 / 2 συγκρίσεις , ενώ στη χειρότερη n* ( n - 1 )/2 .

Αν σε κάποια επανάληψη δεν φτάσει το πρόγραμμα στο if, τότε ο πίνακας είναι ταξινομημένος.

Αυτο το κάνει μονο στην περιπτωση που μιλαμε για την non-optimized εκδοση του αλγοριθμου ετσι δεν ειναι?

Aκριβως εκει στοχευει και η μείωση του i πριν μπει στο εσωτερικο loop και βάζοντας το j < i μεσα εκει μετα .

ChRis6 · 17 Νοεμβρίου 2012

Ναι αυτό που έγραψα είναι ο βασικός αλγοριθμος.Εγώ πιο πάνω προτείνω αυτο:

>

...
int done = 0;

for( int i = 0; i < length && !done ; i++ ){
int swap_made = 0;
for( ... ){

 /* an kanw swap den eimai etoimos */
 if( need_swap() )
 swap_made = 1;
}
if( !swap_made )
 done = 1;
}

ΑΠΑΙΣΙΑ ΣΤΟΙΧΙΣΗ.

migf1 · 17 Νοεμβρίου 2012

Για να κάνεις όσες μετρήσεις θέλεις Κώστα...

>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>    // C99

#define MAXELEMS    10

typedef struct StatsBubble {
   int nIterations;
   int nComparisons;
   int nSwaps;
} StatsBubble;

/* --------------------------------------------------- */
bool statsBubble_init( StatsBubble *stats )
{
   if ( !stats )
       return false;

   memset( stats, 0, sizeof(StatsBubble) );
   return true;
}

/* --------------------------------------------------- */
void statsBubble_print( const StatsBubble *stats, const char *title )
{
   if ( stats ) {
       if ( title )
           printf( "%s", title );
       printf( "iterations: %d | comparisons: %d | swaps: %d",
           stats->nIterations, stats->nComparisons, stats->nSwaps
       );
   }
   putchar('\n');
}

/* --------------------------------------------------- */
bool swap_int( int *n1, int *n2)
{
   if ( !n1 || !n2 )
       return false;

   int temp = *n1;
   *n1 = *n2;
   *n2 = temp;

   return true;
}
/* --------------------------------------------------- */
bool arrInt_copy( int dst[], const int src[], int maxelems )
{
   if ( !dst || !src || maxelems < 1 )
       return false;

   memmove( dst, src, maxelems*sizeof(int) );
   return true;
}
/* --------------------------------------------------- */
void arrInt_print( const int arrInt[], int maxelems, const char *title )
{
   if ( !arrInt || maxelems < 1 ) {
       puts( "*** internal error" );
       return;
   }

   if ( title )
       printf( "%s", title );
   for (int i=0; i < maxelems; i++)
       printf( "%d " , arrInt[i] );
   putchar( '\n' );
}
/* ---------------------------------------------------
* Normal (Wikipedia)
*/
bool arrInt_sort_bubble( int arrInt[], int maxelems, StatsBubble *stats )
{
   bool swapped;

   if ( !arrInt || maxelems < 1 )
       return false;

   if ( stats )
       statsBubble_init(stats);

   do {
       swapped = false;
       for (int i=1; i < maxelems; i++)
       {
           // increase comparisons-counter in stats (due to the if that follows)
           if ( stats )
               (stats->nComparisons)++;

           if ( arrInt[i-1] > arrInt[i] )
           {
               swap_int( &arrInt[i-1], &arrInt[i] );
               swapped = true;
               // increase swaps-counter in stats
               if ( stats )
                   (stats->nSwaps)++;
           }
           // increase iteration-counter in stats (due to inner for-loop)
           if ( stats )
               (stats->nIterations)++;
       }
       // increase iteration-counter in stats (due to outer while-loop)
       if ( stats && swapped )
           (stats->nIterations)++;
   } while ( swapped );

   return true;
}
/* ---------------------------------------------------
* Optimized (Wikipedia)
*/
bool arrInt_sort_bubbleO( int arrInt[], int maxelems, StatsBubble *stats )
{
   if ( !arrInt || maxelems < 1 )
       return false;

   if ( stats )
       statsBubble_init(stats);

   int n = maxelems;
   do {
       int newn = 0;
       for (int i=1; i < n; i++)
       {
           // increase comparisons-counter in stats (due to the if that follows)
           if ( stats )
               (stats->nComparisons)++;

           if ( arrInt[i-1] > arrInt[i] ) {
               swap_int( &arrInt[i-1], &arrInt[i]);
               newn = i;
               // increase swaps-counter in stats
               if ( stats )
                   (stats->nSwaps)++;
           }
           // increase iteration-counter in stats (due to inner for-loop)
           if ( stats )
               (stats->nIterations)++;
       }

       n = newn;

       // increase iteration-counter in stats (due to outer while-loop)
       if ( stats && n != 0)
           (stats->nIterations)++;
   } while (0 != n);

   return true;
}
/* ---------------------------------------------------
* Optimized (StarLight)
*/
bool arrInt_sort_bubbleO_starlight( int arrInt[], int maxelems, StatsBubble *stats )
{
   if ( !arrInt || maxelems < 1 )
       return false;

   if ( stats )
       statsBubble_init(stats);

   for (int i = maxelems-1; i > 0 ; i--)
   {
       for (int j=1; j <= i; j++)
       {
           // increase comparisons-counter in stats (due to the if that follows)
           if ( stats )
               (stats->nComparisons)++;

           if ( arrInt[j-1] > arrInt[j] ) {
               swap_int( &arrInt[j-1], &arrInt[j] );
               // increase swaps-counter in stats
               if ( stats )
                   (stats->nSwaps)++;
           }
           // increase iteration-counter in stats (due to inner for-loop)
           if ( stats )
               (stats->nIterations)++;
       }
       // increase iteration-counter in stats (due to outer for-loop)
       if ( stats )
           (stats->nIterations)++;
   }
   return true;
}
/* --------------------------------------------------- */
int main( void )
{
   StatsBubble stats;
   int arr[MAXELEMS] = {5, 1, 4, 2, 7, 6, 3, 0, 12, -3};
   int arrTemp[MAXELEMS] = {0};

   puts( "________BUBBLE SORT______\n" );
   arrInt_print( arr, MAXELEMS, "Initial data: " );

   // normal version
   arrInt_copy( arrTemp, arr, MAXELEMS );
   arrInt_sort_bubble( arrTemp, MAXELEMS, &stats );
   arrInt_print( arrTemp, MAXELEMS, "\nAfter normal version:\n" );
   statsBubble_print( &stats, "STATS: " );

   // optimized version
   arrInt_copy( arrTemp, arr, MAXELEMS );
   arrInt_sort_bubbleO(arrTemp, MAXELEMS, &stats);
   arrInt_print( arrTemp, MAXELEMS, "\nAfter optimized version:\n" );
   statsBubble_print( &stats, "STATS: " );

   exit(0);
}

Έξοδος...

>
________BUBBLE SORT______

Initial data: 5 1 4 2 7 6 3 0 12 -3

After normal version:
-3 0 1 2 3 4 5 6 7 12
STATS: iterations: 99 | comparisons: 90 | swaps: 25

After optimized version:
-3 0 1 2 3 4 5 6 7 12
STATS: iterations: 54 | comparisons: 45 | swaps: 25

migf1 · 20 Νοεμβρίου 2012

Με αφορμή το προηγούμενο μου ποστ, θέλω να ρωτήσω αν τα iterations πρέπει να μετράνε ή όχι και σαν comparisons.

Παράδειγμα...

>
int arr[MAXLEN ] = {bla, bla}

for (int i=0; i < MAXLEN-1; i++)  // iteratons
   if ( arr[i] > arr[i+1] )   // comparisons
       // bla bla

Έχουμε MAXLEN-1 iterations και από 0 έως MAXLEN-1 comparisons, ανάλογα το κατά πόσο είναι ταξινομημένα τα arr.

Όταν θέλουμε να μετρήσουμε τα συνολικά comparisons που κάνει ο αλγόριθμος, πρέπει ή όχι να συμπεριλάβουμε και τα comparisons που γίνονται στο controlling conditional του loop (δηλαδή του i)?

Επίσης, αν έχουμε recursive αλγόριθμο, είναι ακριβές ή όχι να θεωρήσουμε πως τα recursive function-calls αντιστοιχούν σε iterations;

EDIT:

Λάθος, και τα comparisons σταθερά MAXLEN-1 είναι, το διόρθωσα. Η απορία παραμένει ωστόσο.

imitheos · 20 Νοεμβρίου 2012

>
int arr[MAXLEN ] = {bla, bla}

for (int i=0; i < MAXLEN-1; i++)  // iteratons
   if ( arr[i] > arr[i+1] )   // comparisons
       // bla bla
Όταν θέλουμε να μετρήσουμε τα συνολικά comparisons που κάνει ο αλγόριθμος, πρέπει ή όχι να συμπεριλάβουμε και τα comparisons που γίνονται στο controlling conditional του loop (δηλαδή του i)?

Δηλαδή εννοείς να θεωρείς comparison το "i < MAXLEN - 1" ?

Ετυμολογικά είναι σύγκριση αλλά τι σχέση έχει με τον Χ αλγόριθμο που εξετάζουμε ?

migf1 · 20 Νοεμβρίου 2012

Ναι, δες για παράδειγμα 2 αλγόριθμους για Insertion sort, έναν vanilla κι ένα optimized...

Insertion Sort Vanilla:

>
void sort_insertion_vanilla( int arr[], int maxelems )
{
   int  item, iHole;

   // outer loop
   for (int i=1; i < maxelems; i++) {
       item  = arr[i];
       iHole = i;

       // inner loop (shifting)
       while ( iHole > 0 && arr[iHole-1] > item ) {
           arr[iHole] = arr[iHole-1];
           iHole = iHole-1;
       }
       arr[iHole] = item;
   }
}

Το outer loop σίγουρα το μετράμε στα iterations, αλλά το inner loop το μετράμε στα iterations, στα comparisons ή και στα δυο;

Στην optimized version περιπλέκεται ακόμα περισσότερο το πράγμα

Insertion Sort Optimized

>
void sort_insertionO( int arr[], int maxelems )
{
   int i, m;
   int hi, lo, tmp;

   // outer loop
   for (i=1; i < maxelems; i++)
   {
       lo = 0;
       hi = i;
       m  = i / 2;

       // inner loop
       do {
           if ( arr[i] > arr[m] )
               lo = m + 1;
           else if ( arr[i] < arr[m] )
               hi = m;
           else
               break;

           m = lo + ((hi - lo) / 2);
       } while ( lo < hi );

       // shifting
       if ( m < i ) {
           tmp = arr[i];
           memmove( &arr[m + 1], &arr[m], sizeof(int) * (i - m) );
           arr[m] = tmp;
       }
   }
}

Τι μετράμε ως iteration, και τι ως comparison?

ΥΓ. Άμα πάμε σε QuickSort να δεις χαμός που γίνεται.

defacer · 20 Νοεμβρίου 2012

Όταν θέλουμε να μετρήσουμε τα συνολικά comparisons που κάνει ο αλγόριθμος, πρέπει ή όχι να συμπεριλάβουμε και τα comparisons που γίνονται στο controlling conditional του loop (δηλαδή του i)?

Όχι, μόνο αυτά που έχουν να κάνουν με τα δεδομένα εισόδου. Το αν θα έχεις κανένα ή ένα ή πολλά άλλα άσχετα comparisons θα επηρρεάσει π.χ. την τιμή της σταθεράς Μ με τη βοήθεια της οποίας ορίζεται το Big-O, αλλά μέχρι εκεί.

Επίσης, αν έχουμε recursive αλγόριθμο, είναι ακριβές ή όχι να θεωρήσουμε πως τα recursive function-calls αντιστοιχούν σε iterations;

Μάλλον όχι αν και δεν κατάλαβα σίγουρα τι εννοείς. Όταν κάνεις π.χ. mergesort για N αντικείμενα θα κάνεις στην απλούστερη περίπτωση Ν/2 recursive calls, αλλά προφανώς αν αυτά μετρούσαν "κανονικά" θα την έβγαζες O(N) -- που δεν είναι. Καθένα από αυτά τα N/2 calls θα κάνει είτε δουλειά και καθόλου επιπλέον recursion είτε επιπλέον recursion και καθόλου δουλειά.

imitheos · 20 Νοεμβρίου 2012

Ναι, δες για παράδειγμα 2 αλγόριθμους για Insertion sort, έναν vanilla κι ένα optimized...

Insertion Sort Vanilla:

Το outer loop σίγουρα το μετράμε στα iterations, αλλά το inner loop το μετράμε στα iterations, στα comparisons ή και στα δυο;

Στα comparisons σίγουρα. Για iterations όντως είναι λίγο μπερδευτικό. Το inner loop δεν βλέπω να προσδίδει κάτι στην πολυπλοκότητα γιατί το μόνο που κάνει είναι να τρέχει το comparison και το πιθανό swap οπότε εγώ δεν θα το μετρούσα σαν iteration. Στο μυαλό μου δηλαδή το έχω σκεφτεί πως αν κάνουμε unroll το loop μας μένει μόνο το comparison οπότε δεν μετράει για iteration γιατί το συμπεριλάβαμε ήδη σαν comparison. Δεν ξέρω όμως ποια είναι η δόκιμη συμπεριφορά και είναι πολύ πιθανό να σφάλλω.

migf1 · 20 Νοεμβρίου 2012

Όχι, μόνο αυτά που έχουν να κάνουν με τα δεδομένα εισόδου. Το αν θα έχεις κανένα ή ένα ή πολλά άλλα άσχετα comparisons θα επηρρεάσει π.χ. την τιμή της σταθεράς Μ με τη βοήθεια της οποίας ορίζεται το Big-O, αλλά μέχρι εκεί.

Οπότε στους 2 κώδικες που παρέθεσα, ποια μετράνε ως iterations και ποια ως comparisons?

Μάλλον όχι αν και δεν κατάλαβα σίγουρα τι εννοείς. Όταν κάνεις π.χ. mergesort για N αντικείμενα θα κάνεις στην απλούστερη περίπτωση Ν/2 recursive calls, αλλά προφανώς αν αυτά μετρούσαν "κανονικά" θα την έβγαζες O(N) -- που δεν είναι. Καθένα από αυτά τα N/2 calls θα κάνει είτε δουλειά και καθόλου επιπλέον recursion είτε επιπλέον recursion και καθόλου δουλειά.

Τα O(n) και O(n/2) δεν είναι ισοδύναμα; Από ότι θυμάμαι, τα constants γίνονται drop-off στο simplification.

Στα comparisons σίγουρα. Για iterations όντως είναι λίγο μπερδευτικό. Το inner loop δεν βλέπω να προσδίδει κάτι στην πολυπλοκότητα γιατί το μόνο που κάνει είναι να τρέχει το comparison και το πιθανό swap οπότε εγώ δεν θα το μετρούσα σαν iteration. Στο μυαλό μου δηλαδή το έχω σκεφτεί πως αν κάνουμε unroll το loop μας μένει μόνο το comparison οπότε δεν μετράει για iteration γιατί το συμπεριλάβαμε ήδη σαν comparison. Δεν ξέρω όμως ποια είναι η δόκιμη συμπεριφορά και είναι πολύ πιθανό να σφάλλω.

Ομοίως κι εγώ (δεν ξέρω) για αυτό και ρώτησα. Θέλοντας να κάνουμε ένα πρόγραμμα που να παραθέτει για τον κάθε αλγόριθμο 3 counters: iterations, comparisons, swaps (άντε και rcalls, για recursive-function-calls) όπως αυτό που έγραψα στον StarLight για την bubble-sort, πως θα βρούμε πως πρέπει να αντιμετωπίσουμε αυτές τις ποσότητες;

Π.χ. το shifting πάει στα comparisons ή στα swaps (π.χ. σαν ήταν iterations) ή και στα 2;

Το google δεν με έχει βοηθήσει μέχρι στιγμής.

EDIT:

Σχετικά με το shifting, έχει κι άλλη περιπλοκή... αλλιώς είναι manually κι αλλιώς με memmove, τι μετράει που ρε γαμότο;

defacer · 20 Νοεμβρίου 2012

Οπότε στους 2 κώδικες που παρέθεσα, ποια μετράνε ως iterations και ποια ως comparisons?

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

Τα O(n) και O(n/2) δεν είναι ισοδύναμα; Από ότι θυμάμαι, τα constants γίνονται drop-off στο simplification.

Ισοδύναμα είναι, αλλά η mergesort είναι O(NlogN) ακριβώς επειδή μπαίνει μέσα μια συνάρτηση του N/2 στην εξίσωση, π.χ. δες εδώ σελίδα 3.

migf1 · 20 Νοεμβρίου 2012

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

Οκ

Ισοδύναμα είναι, αλλά η mergesort είναι O(NlogN) ακριβώς επειδή μπαίνει μέσα μια συνάρτηση του N/2 στην εξίσωση, π.χ. δες εδώ σελίδα 3.

Let me re-phrase, είναι ακριβές (ασφαλές) να θεωρήσουμε τα recursive-function-calls σαν να ήταν iterations ενός θεωρητικού outer-loop; Τυχόν εσωτερικά iterations (π.χ. κάποιων κανονικών loop που ενδεχομένως περιέχει η συνάρτηση) θα τα προσθέτουμε έτσι κι αλλιώς in-place.

Π.χ.

>
void recurse(int *count)
{
   (*count)++;        // recursive call
   if ( *count > 100 )
       return;

   for (int i=0; i < 10; i++) {
        (*count)++;    // inner iteration
   }
   recurse( count );
}
...
int count = 0;
recurse( &count );
printf( "iterations: %d\n", count );

Επεξ/σία 20 Νοεμβρίου 2012 από migf1

Σύνδεση

Ερωτήσεις για C

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

Star_Light

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Δημοφιλή Μηνύματα

imitheos

migf1

defacer

Δημοσιευμένες Εικόνες

ZAKKWYLDE

Star_Light

ChRis6

Star_Light

ChRis6

migf1

migf1

imitheos

migf1

defacer

imitheos

migf1

defacer

migf1

imitheos

migf1

defacer

Σύνδεση