/* Ε.Α.Π. Πληροφορική
   Αθανασίου Κωνσταντίνος
   Α.Μ. 170612
   ΗΛΕ-42
   2η Γραπτή Εργασία - ΠΛΗ10
   Υποεργασία 2.B.: Ταξινόμηση  Bead Sort ή Gravity Sort */
#include <stdio.h> /* Συμπερίληψη της βιβλιοθήκης για λειτουργίες εισόδου/εξόδου (printf, scanf)*/

#define N 10 /* Σταθερά: Πλήθος στοιχείων του πίνακα Α (είσοδος) και Β (έξοδος)*/
#define M 50 /* Σταθερά: Μέγιστη τιμή κονταριών (ύψος) που επιτρέπεται, max(A[i])*/

int main()
{
    /* Βήμα 1: Ανάγνωση των στοιχείων του πίνακα A */
    int A[N];
    /* Επανάληψη για την εισαγωγή των Ν στοιχείων του πίνακα Α*/
    for(int i=0; i<N; i++) 
    { 
        printf("Εισάγετε το στοιχείο %d (επιτρεπόμενες τιμές από 0 έως και %d): ", i+1, M);
        scanf("%d", &A[i]);
        
    /* Αμυντικός Προγραμματισμός: Έλεγχος εγκυρότητας τιμής εισόδου*/
        while(A[i] < 0 || A[i] > M) 
        { 
    /* Ενημέρωση χρήστη και επανεισαγωγή τιμής αν δεν είναι εντός του ορίου [0, M]*/
            printf("Η τιμή που εισάγετε πρέπει να είναι μεταξύ 0 και %d. Επαναλάβετε την είσοδο.\n", M);
            printf("Εισάγετε το στοιχείο %d (επιτρεπόμενες τιμές από 0 έως και %d): ", i+1, M);
            scanf("%d", &A[i]);
        }
    }
    
    /* Βήμα 2: Υπολογισμός του πίνακα counts*/
    /* Δήλωση του πίνακα counts (κοντάρια) με μέγεθος M.*/ 
    /* Οι δείκτες 0 έως M-1 αντιπροσωπεύουν τις τιμές 1 έως M.*/
    int counts[M] = {0}; 
    
    /* Τοποθέτηση "χαντρών" στα αντίστοιχα κοντάρια.*/
    for(int i=0; i<N; i++) 
    { 
        int v = A[i]; // v είναι η τιμή του τρέχοντος στοιχείου (π.χ. v=3)
    
        /* Για κάθε τιμή v, τοποθετείται μια χάντρα στα κοντάρια με δείκτες j=0 έως v-1.*/
        /* Δηλαδή, ένα στοιχείο v=3 αυξάνει τα counts[0], counts[1], counts[2]*/
        for(int j=0; j<v; j++) 
        {
           counts[j]++; /* Αύξηση του πλήθους χαντρών στο κοντάρι j*/
        } 
    }


    /* Βήμα 3: Υπολογισμός των στοιχείων του πίνακα B */
    int B[N]; /* Ο πίνακας εξόδου για τα N ταξινομημένα στοιχεία*/
    
    /* Δημιουργία του ταξινομημένου πίνακα B (από k=0 έως N-1)*/
    /* Αυτό το βήμα εξάγει τις τιμές σε αύξουσα σειρά*/
    for(int k=0; k<N; k++)
    {
       /* Υπολογισμός του ορίου (threshold): Πλήθος χαντρών που πρέπει να έχει ένα κοντάρι*/
        /* Θέτουμε το threshold να φθίνει (από N προς 1)*/
        int threshold = N-k;
        int counter = 0; /* Μετρητής για την τιμή του B[k]*/

        /* Διατρέχουμε όλα τα κοντάρια (δείκτες j=0 έως M-1)*/
        for(int j=0; j<M; j++) 
        {
            /* Ελέγχουμε αν το κοντάρι j έχει πλήθος χαντρών (counts[j])*/ 
            /* ίσο ή μεγαλύτερο από το τρέχον όριο (threshold).*/
            if(counts[j] >= threshold) 
            {
                /* Κάθε κοντάρι που ικανοποιεί τη συνθήκη αντιπροσωπεύει μία μονάδα */
                /* στην ταξινομημένη τιμή B[k]*/
                counter++; 
            }
        }        
        /* Το k-οστό στοιχείο του ταξινομημένου πίνακα B ισούται με τον τελικό μετρητή*/
        /* Το B[0] (k=0) παίρνει τη μικρότερη τιμή*/
        B[k] = counter;
    }
    
    /* Βήμα 4: Εμφάνιση των στοιχείων του πίνακα B */
    for(int i=0; i<N; i++) 
    {
        printf("Το στοιχείο %d είναι ίσο με %d \n", i+1, B[i]);
    }
    printf("\n\n");
    printf("------------------------------\n");
    
    return 0; /* Τερματισμός του προγράμματος με επιτυχία*/
}