heapsort

#include
#include

//Αγαπητό μου ημερολόγιο,

int heap_size;


int * readArray(char *filename, int *n)
{
FILE *fp;
int * array, i;

if ((fp = fopen(filename, "r")) == NULL)
{
fprintf(stderr, "Unable to open %s!\n", filename);
exit(1);
}

fscanf(fp, "%d\n", n);

if ((array = (int*) malloc((*n) * sizeof(int))) == NULL)
{
fprintf(stderr, "Out of memory!\n");
exit(1);
}

for (i = 0; i < *n; i++)
fscanf(fp,"%d ", &array[i]);

fclose(fp);
return(array);
}

void combine(int level, int *heap)
{
/* τίποτε από όλα αυτά δεν έχει αντίκτυπο, όλα τους δημιουργούν έναν παφλασμό στην επιφάνεια της γαλήνιας χμμμ Γκαουσιανής επιφάνειας , απόλυτα προβλεπόμενο, καθόλα τυπικό, μετρημένο και ήδη καταχωρημένο από παλιά σε κάποια γιγαντιαία μαύρη καταβόθρα δεδομένων. Αυτό ο κόσμος το ξέρει. Και γι αυτό θα τελειώσει. */

int left, right, temp, current_level;

left=2*level+1;
right=2*level+2;
current_level=level;


if ((left <= heap_size) && (heap[left] > heap[current_level]))
current_level = left;

if ((right <= heap_size) && (heap[right] > heap[current_level]))
current_level = right;

if (current_level != level)
{
temp = heap[level];
heap[level]=heap[current_level];
heap[current_level]=temp;
combine (current_level, heap); //call function recursively for lower subtree
/*το ίδιο και αυτή η συνάρτηση. Κάποια στιγμή, αφού καταβροχθίσει τον εαυτό της όλο και περισσότερο κάθε φορά, ξανά και ξανά, πάλι και πάλι, θα έρθει η στιγμή της να τελειώσει. Και τότε θα πρέπει να δικαιολογήσει την ύπαρξή της, οπότε θα αρζίσουν οι συμβάσεις. "Αυτό είναι heap και αυτό δεν είναι".
Για τις συμβάσεις θα σας πω ένα μυστικό. Είναι όλες ΨΕΜΑΤΑ μεγάλα, αισχρά, πονηρά, σάπια, βδελυρά, σιχαμερά, μιαρά ΨΕΜΑΤΑ. Μαζεύονται κάθε τόσο καιρό οι ελίτ του πνεύματος και αποφασίζουν τι θα είναι τί... μας το σερβίρουν με μακαρονάδα και λένε είναι ΣΥΜΒΑΣΗ.
Σε αυτή την συνάρτηση θα δώσετε στην τύχη αριθμούς, θα τους ανακατέψει και θα σας πει οτι είναι heap... Νααααααααααααααα μας και μας, κανένως είδους heap δεν θα λύσει το πρόβλημα*/
}
};

void constructheap(int n, int *heap)
{
/* Ξαναξεκινώ λοιπόν.
Αγαπημένο μου ημερολόγιο,
σου γράφω και πάλι σήμερα με την πεποίθηση οτι ο κόσμος τελειώνει. Ο κόσμος τελειώνει γιατί δεν έχει πια κανένα νόημα. Μην περιμένετε λοιπόν βιβλικές καταστροφές, ή ακόμα καλύτερα να με εκθέσετε αν δεν έρθουν, ο κόσμος θα τελειώσει ακόμα και αν δεν γίνει τίποτε από αυτά.
Ένας γιατρός σήμερα έκανε μια διάγνωση και έγραψε ένα φάρμακο.
Ένας φιλόλογος διόρθωσε μια έκθεση και ένας προγραμματιστής έγραψε ένα πρόγραμμα... */

int i, middle;
heap_size = n;
if (n % 2 == 0)
middle = n/2;
else
middle = n/2-1;

for (i=middle; i>=0; i--)
combine(i,heap);
/*Και τι έγινε; Ο κύκλος πήρε άλλη μια στροφή και ως κύκλος που είναι δεν φθείρεται και θα συνεχίσει να στροφάρει αδιάφορα και αύριο και μεθαύριο. */

};

int deletemax_sort(int *heap)
/* και οι τελευταίοι έσονται πρώτοι*/
{ int max;
if (heap_size == 1)
return (1);
else
{
max=heap[0];
heap[0]=heap[--heap_size];
heap[heap_size]=0;
combine(0, heap);
heap[heap_size]=max;
}

return(0);

};


int main(int argc, char *argv[])
{
/*σου γράφω και πάλι σήμερα με περιφάνεια, από αυτή που αισθάνεται κανείς
όταν έχει αντιμετωπίσει όσα εμπόδια βρέθηκαν μπροστά του και νικητής έχει εκπληρώσει το καθήκον του.

Αυτή είναι μια υλοποίηση της heapsort. Ένα προγραμματιστικό τίποτα. Ένα τίποτα που όμως έφερα εις πέρας με ανδρεία, τόλμη, αυταπάρνηση και ενθουσιασμό. */

int n; // the size of the array
int i;

if (argc != 2)
{
fprintf(stderr, "Usage: %s filename!\n", argv[0]);
exit(1);
}


int *heap = readArray(argv[1], &n);

/*Στη σχολή, μας έχουνε πει οτι στα προγράμματά μας είναι καλό να βάζουμε σχόλια στον κώδικα. Έχουν δίκιο γιατί κάποιος άλλος κακόμοιρος θα πρέπει να βγάλει άκρη από τον τραχανά που έχεις απλώσει εσύ. Σκεφτόμουν όμως οτι τα συνιθισμένα σχόλια δεν ικανοποιούν τις ανάγκες ενός προγραμματιστή */

"reads this from there does that and returns it."

Αυτό απλά δεν είναι αρκετό.*/

for (i=0; i<=n-1; i++)
printf(" %d ",heap[i]);

constructheap(n,heap);

/*Απεθύνεσαι σε άνθρωπο που αναρωτιέται γιατί του σπας τα νεύρα. Εξήγησέ του.*/

printf("\n");
for (i=0; i<=n-1; i++)
printf(" %d ",heap[i]);

for(i=0; i<=n-1; i++)
/* Ποιό είναι το προβλημα; Το πρόβλημα είναι οτι ο κόσμος τελειώνει και κανείς, μα κανείς δεν δίνει δεκάρα τσακιστή. Οι γιατροί γιατρεύουν, οι δάσκαλοι δασκαλεύουν, οι κλέφτες κλέβουν και όλοι κάνουν την δουλειά τους με τον ένα και μοναδικό τρόπο που ξέρουν. Αυτά να τα ξεχάσετε, Ο ΚΟΣΜΟΣ ΕΠΙΤΕΛΟΥΣ ΘΑ ΦΑΝΕΙ ΓΕΝΝΑΙΟΔΩΡΟΣ ΚΑΙ ΘΑ ΤΕΛΕΙΩΣΕΙ.
deletemax_sort(heap);

printf("\n");
for (i=0; i<=n-1; i++)
printf(" %d ",heap[i]);

printf("\n");
return 0;
}