ταξινόμηση σε C

[voulaji]

Για την πιο κάτω συνάρτηση, θέλω να βρω το αποτέλεσμα της εκτέλεσής της και πως μπορώ να την διαφοροποιήσω ώστε να γίνει πιο αποδοτική.

 

int f (const int a [ ], const unsigned int length)

{

int result = 1;

for (unsigned int i = 0; i < length; ++i )

if (a[i+1] < a )

result = 0;

if (result == 1)

return 1;

else

return 0;

}

[_tasos]

Καλημέρα.

 

Αυτό που κάνει η συνάρτηση είναι να ελέγχει αν ο πίνακας είναι ταξινομημένος με αύξουσα σειρά. Αν είναι ταξινομημένος επιστρέφει τη τιμή 1 αλλιώς τη τιμή 0. Στη C οι τιμές 0 κ 1 αντιστοιχούν στα True κ False.

Το μόνο που μπορείς να κάνεις για να είναι πιο αποδοτική η συνάρτηση είναι να κάνεις τη συνάρτηση να επιστρέφει τη στιγμή που βρίσκει ότι δεν είναι ταξινομημένος ο κώδικας. Π.χ.

 

int f (const int a [ ], const unsigned int length)

{

for (unsigned int i = 0; i < length; ++i )

if (a[i+1] < a )

return 0;

return 1;

}

[voulaji]

Σε ευχαριστώ πολύ για την βοήθεια.

Θα ήθελα να σε ρωτήσω επιπλέον γιατί δεν είναι αποδοτική η υλοποίηση αυτής της συνάρτησης.

Μήπως επειδή παρουσιάζει μεγαλύτερη πολυπλοκότητα;

[Directx]

Ναι!

 

Δεν είναι αποδοτική διότι, καταρχήν ορίζει ένα ουσιαστικά άχρηστο int (result) και ύστερα προσθέτει ένα ακόμα ανούσιο if-else έλεγχο (if result==1 else ...), πράγματα δηλαδή που και μεγαλύτερο κώδικα παράγουν και δεν έχουν κανέναν λόγο ύπαρξης όπως φαίνεται από την δεύτερη έκδοση της ρουτίνας.

 

Μια μικρή παρατήρηση, αν πρόκειται για ANSI-C καλό είναι να τοποθετήσουμε την δήλωση του unsigned int εκτός του for loop.

[bokarinho]

Από ότι καταλαβαίνω μάλλον προσπαθείς να φτιάξεις μία BubbleSort που είναι από τις ευκολότερες και ομορφότερες μεθόδους ταξινόμησης. Ε να λοιπόν ένα πρόγραμμα που ταξινομεί ένα πίνακα με βάση τον αλγόριθμο ταξινόμησης της BubbleSort και τυπώνει τα ανάλογα αποτελέσματα. Η BubbleSort μπορεί να γραφεί ως μία εννιαία συνάρτηση, βέβαια εγώ προτιμώ να χρησιμοποιώ και την βοηθητική BubbleUp η οποία σαρώνει τον πίνακα από το τέλος προς τηνα αρχή και ελέγχει τα διαδοχικά ζευγάρια θέσεων στον πίνακα για το είδος της ταξινόμησης που θέλουμε(asceding, descending) και όπου χρειάζεται ανταλλάσει τα περιεχόμενα τους, μετά στην BubbleSort στην ουσία καλούμε αυτή την συνάρτηση nArraySz-1 φορές όσπου στο τέλος ο πίνακας είναι sorted. Α, το πρόγραμμα χρησιμοποιεί και μία συνάρτηση για να παράγει τυχαιόυς αριθμούς.

 

Κώδικας:

 

>
//---------------------------------------------------------------------------

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

#pragma hdrstop

//---------------------------------------------------------------------------
/* Swap. */

void Swap(int *Item1, int *Item2)
{
int Item = *Item1;
*Item1 = *Item2;
*Item2 = Item;
}
/* Bubble Up. */

void BubbleUp(int TArray[], const int _startIndex, const int _endIndex)
{
int Index = _endIndex;
for(; Index > _startIndex; Index--)
{
	if(TArray[index-1] > TArray[index])
		Swap(&TArray[index-1], &TArray[index]);
}
}

/* Bubble Sort. */

void BubbleSort(int TArray[], int nArraySz)
{
int _Index = 0;
while(_Index < nArraySz-1)
	BubbleUp(TArray, _Index++, nArraySz-1);
}

/* Generate a random number in the [vStart, vEnd). */

int Generator(int vStart, int vEnd)
{
return (int)((rand() /(double)RAND_MAX) * abs(vEnd - vStart) + vStart);
}

void PrintArray(const int TArray[], const int ArraySz)
{
int Idx = 0;
for(; Idx < ArraySz; Idx++)
	printf("%d%s", *(TArray + Idx), Idx != ArraySz -1 ? " " : "\n");
}


#pragma argsused

/* Main Code. */
int main(int argc, char* argv[])
{
static int Index = 0;
int Array[24];
memset((int*)Array, 0, sizeof(Array));
printf("Zero Array:\n");
PrintArray(Array, 24);
srand(time(NULL));
for(; Index < 24; Index++)
	Array[index] = Generator(0, 100);
printf("Initial Array:\n");
PrintArray(Array, 24);
printf("Sorted Array:\n");
BubbleSort(Array, 24);
PrintArray(Array, 24);
printf("Hit enter to continue....\n");
getchar();
return 0;
}
//---------------------------------------------------------------------------

 

Αποτελέσματα:

 

Zero Array:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Initial Array:

0 33 3 35 21 53 19 70 94 27 44 10 69 56 4 16 81 68 76 82 95 21 42 95

Sorted Array:

0 3 4 10 16 19 21 21 27 33 35 42 44 53 56 68 69 70 76 81 82 94 95 95

Hit enter to continue....