Ταξινόμηση πίνακα

[zafgr]

Καλησπέρα , θα ήθελα να κάνω  στη c , ένα πίνακα ο οποίος να διατηρεί ταξινομημένα τα στοιχεία του όταν λαμβάνει τιμές για αυτά από τη rand() , δηλαδή να μη "γεμίζω" πρώτα τον πίνακα και μετά να κάνω ταξινόμηση.

Καλοδεχούμενη όποια άποψη 

Σας ευχαριστώ εκ των προτέρων 

 

[παπι]

Sorted list θες

[zafgr]

Sorted list θες

αναφέρεσαι σε bubble sort? insertion sort ή selection sort?

αν ναι μπορείς να μου δώσεις ένα παράδειγμα?

[anon667]

Για αρχή θα έλεγα να μας περιγράψεις πως ακριβώς θες να χειρίζεσαι τον πίνακα. Π.χ. τι functions θα χρησιμοποιείς; Πως θα τον δηλώνεις τον πίνακα;

[zafgr]

Για αρχή θα έλεγα να μας περιγράψεις πως ακριβώς θες να χειρίζεσαι τον πίνακα. Π.χ. τι functions θα χρησιμοποιείς; Πως θα τον δηλώνεις τον πίνακα;

το παράδειγμα που προσπαθώ να κάνω είναι ακριβώς το παρακάτω

 

Γράψτε ένα πρόγραμμα C το οποίο:

1. Θα δημιουργεί με κλήση της συνάρτησης rand() δύο (2) ταξινομημένους κατ’ αύξουσα σειρά μονοδιάστατους πίνακες Μ και Ν στοιχείων αντίστοιχα, τους οποίους και θα τους εμφανίζει στη οθόνη. Το εύρος τιμών των στοιχείων του πίνακα είναι: [100-999].

Προσέξτε, το πρόγραμμα θα φροντίζει ο κάθε πίνακας να διατηρεί ταξινομημένα τα στοιχεία του όταν λαμβάνει τιμές για αυτά από τη συνάρτηση rand() – Δηλαδή δεν θα «γεμίζουμε» πρώτα τον πίνακα και μετά θα κάνουμε ταξινόμηση των στοιχείων του.

2. Το πρόγραμμα σας στη συνέχεια θα δημιουργεί ένα τρίτο πίνακα ο οποίος θα περιέχει ταξινομημένα τα στοιχεία των 2 αρχικών (ταξινομημένων) πινάκων. Αυτός ο τρίτος πίνακας θα πρέπει προφανώς να έχει αριθμό στοιχείων ικανό να χωρέσει και τους 2 αρχικούς πίνακες (>=Μ+Ν). Το πρόγραμμα σας θα εμφανίζει στο τέλος το νέο πίνακα αντίστροφα (φθίνουσα σειρά).

Προσοχή ξανά: δεν θα δημιουργείται ο νέος πίνακας απλά ενώνοντας τους δύο αρχικούς και μετά να γίνεται ταξινόμηση των στοιχείων του. Θα φροντίζετε ο νέος πίνακας να διατηρείται ταξινομημένος καθώς καταχωρούνται σε αυτό τα στοιχεία των 2 αρχικών πινάκων.

 

και δε μπορώ να καταλάβω πώς θα αρχικοποιήσω έναν πίνακα χωρίς να τού δώσω καν τιμές

 

ο κώδικας που έγραψα είναι ο παρακάτω

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define size 100


main()
{
int i,j,temp;
int a[size],b[size];
int swapped,pos,N=0; 

printf("dwste N:\n");
scanf("%d",&N);

/*Arxikopoihsh tou protou pinaka*/ 
srand(time(NULL));

for(i=0;i<N;i++)
    a[i]=100+rand()%900;
    
   while(1){
     
swapped=0;

for(i=0;i<N-1;i++){
if(a[i]>a[i+1]){
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
swapped=1;
}
}

if(swapped==0){
break;
}

       }
    /* Ektyposh pinaka*/
printf("[");
for(i=1;i<N;i++) 
printf("%d, ",a[i]); 
printf("%d]",a[i-1]);

   

}

 

[solarpower]

Εγώ θα χρησιμοποιούσα έναν βοηθητικό πίνακα 900 στοιχείων όπου θα έγραφα μέσα το πόσες φορές κάθε νούμερο θα εμφανίζεται στο Μ, θα έφτιαχνα τον Μ και μετά θα τον άδειαζα και θα έγραφα μέσα πόσες φορές κάθε νούμερο θα εμφανίζεται στον Ν.

 

Έστω ο πίνακας αυτός είναι ο Β[], και έστω ότι είναι γεμάτος με νούμερα. Για να γραφτεί ο Μ[] ξεκινάμε από το πρώτο Β[ι]>0 και το γράφουμε με j=0 στο Μ[j]=i, και μειώνουμε το Β[ι] ή μια βοηθητική μεταβλητή. Το ίδιο κάνουμε για τον Ν[]

 

Το 2ο ερώτημα είναι πιο εύκολο γιατί τώρα μπορούμε να φτιάξουμε το πίνακα F με Μ+Ν στοιχεία, να θέσουμε τρεις "δρομείς", το i και j και k, ώστε όταν Μ[ι]<Ν[j] θα πηγαίνει στο F[k]=M και i++ και k++ αλλιώς F[k]=M[j] και j++ και k++

 

Άρα το ζήτημα είναι πώς θα φτιάχνεται ο βοηθητικός πίνακας Β(). Εδώ είναι η ευκολία: Κάνουμε ένα loop όσο το μέγεθος του Μ και χρησιμοποιούμε την rand() να μας πει σε ποιο στοιχείο του βοηθητικού πίνακα θα αυξήσουμε κατά ένα. Στο τέλος ο βοηθητικός πίνακας θα έχει τόσες τιμές όσο το μέγεθος του Μ, αλλά θα είναι σε τυχαία στοιχεία, και σε κάθε στοιχείο θα έχει τυχαία έναν αριθμό.

[zafgr]

Εγώ θα χρησιμοποιούσα έναν βοηθητικό πίνακα 900 στοιχείων όπου θα έγραφα μέσα το πόσες φορές κάθε νούμερο θα εμφανίζεται στο Μ, θα έφτιαχνα τον Μ και μετά θα τον άδειαζα και θα έγραφα μέσα πόσες φορές κάθε νούμερο θα εμφανίζεται στον Ν.

 

Έστω ο πίνακας αυτός είναι ο Β[], και έστω ότι είναι γεμάτος με νούμερα. Για να γραφτεί ο Μ[] ξεκινάμε από το πρώτο Β[ι]>0 και το γράφουμε με j=0 στο Μ[j]=i, και μειώνουμε το Β[ι] ή μια βοηθητική μεταβλητή. Το ίδιο κάνουμε για τον Ν[]

 

Το 2ο ερώτημα είναι πιο εύκολο γιατί τώρα μπορούμε να φτιάξουμε το πίνακα F με Μ+Ν στοιχεία, να θέσουμε τρεις "δρομείς", το i και j και k, ώστε όταν Μ[ι]<Ν[j] θα πηγαίνει στο F[k]=M και i++ και k++ αλλιώς F[k]=M[j] και j++ και k++

 

Άρα το ζήτημα είναι πώς θα φτιάχνεται ο βοηθητικός πίνακας Β(). Εδώ είναι η ευκολία: Κάνουμε ένα loop όσο το μέγεθος του Μ και χρησιμοποιούμε την rand() να μας πει σε ποιο στοιχείο του βοηθητικού πίνακα θα αυξήσουμε κατά ένα. Στο τέλος ο βοηθητικός πίνακας θα έχει τόσες τιμές όσο το μέγεθος του Μ, αλλά θα είναι σε τυχαία στοιχεία, και σε κάθε στοιχείο θα έχει τυχαία έναν αριθμό.

solarpower σε ευχαριστώ για την απάντησή σου η απορία μου όμως παραμένει όσον αφορά ότι κάθε στοιχείο που μπαίνει απο τη rand() πρέπει να μπαίνει ταξινομημένο . 

Μήπως θα μπορούσα να χρησιμοποιώ την rand() να προσθέτει ενα στοιχείο τη φορά και να ταξινομούνται όλα σαν insertion sort?

Αναφορικά είμαι αρχάριος στο προγραμματισμό, τώρα μαθαίνω ...

[solarpower]

zafgr,

το να είσαι νέος δεν πειράζει. Όμως και νέος να είσαι το βασικό ατού είναι να καταλαβαίνεις το λάθος! Στο κώδικά σου ξεκινάς με πίνακες μεγέθους size=100 και μετά ζητάς το Ν για αρχικοποίηση του πίνακα. Αν δώσω Ν=1000 τι νομίζεις ότι θα κάνει το πρόγραμμα; Παίζει το a[500] ας πούμε;

Προφανώς το ζήτημα δεν θα λυθεί με δυναμικούς πίνακες. Δηλαδή θα ξεκινάει το πρόγραμμα με γνωστά τα Ν και Μ.

[zafgr]

zafgr,

το να είσαι νέος δεν πειράζει. Όμως και νέος να είσαι το βασικό ατού είναι να καταλαβαίνεις το λάθος! Στο κώδικά σου ξεκινάς με πίνακες μεγέθους size=100 και μετά ζητάς το Ν για αρχικοποίηση του πίνακα. Αν δώσω Ν=1000 τι νομίζεις ότι θα κάνει το πρόγραμμα; Παίζει το a[500] ας πούμε;

Προφανώς το ζήτημα δεν θα λυθεί με δυναμικούς πίνακες. Δηλαδή θα ξεκινάει το πρόγραμμα με γνωστά τα Ν και Μ.

solarpower δεν είναι το πρόβλημά μου το μέγεθος του πίνακα άλλωστε δε το διευκρινίζει η άσκηση  και αλλάζει εύκολα σχετικά. Ας υποθέσουμε αρχικά ότι μας λέει να έχουμε πινακες με  size=100 , πώς θα μπούνε οι τιμές απο τη rand  ταξινομημένες δε καταλαβαίνω...

ευχαριστώ

[παπι]

Καθηγητής από τα λιντλ.

 

Προσοχή ξανά: δεν θα δημιουργείται ο νέος πίνακας απλά ενώνοντας τους δύο αρχικούς

 

Κλαίω, merge δύο πινάκων...

 

Λοιπόν τιες. Πας διαβάζεις για sorted linked list. Από την εκφώνηση θα αντικαταστήσεις την λέξη 'πινακα' με την λέξη 'λιστα' και θα γράψεις την άσκηση. Είναι απλή άσκηση, αλλά όχι με πίνακες.

[solarpower]

Καλά άμα το κάνει με λίστα στη C την έχασε την άσκηση!

 

(να συμπληρώσω, ασφαλώς για να ρωτάει ακόμα πως θα χρησιμοποιήσει την rand() και δεν θα ταξινομήσει τον πίνακα και αυτός θα βγει ταξινομημένος στο γέμισμα σημαίνει ότι δεν κατάλαβε την λύση που έδωσα)

 

άντε να το γράψω: η λύση είναι ένα lookup table.

[paparovic]

Εγώ θα χρησιμοποιούσα έναν βοηθητικό πίνακα 900 στοιχείων όπου θα έγραφα μέσα το πόσες φορές κάθε νούμερο θα εμφανίζεται στο Μ, θα έφτιαχνα τον Μ και μετά θα τον άδειαζα και θα έγραφα μέσα πόσες φορές κάθε νούμερο θα εμφανίζεται στον Ν.

 

Το τεχνικό όνομα της υλοποίησης λέγεται MoronSort.

solarpower δεν είναι το πρόβλημά μου το μέγεθος του πίνακα άλλωστε δε το διευκρινίζει η άσκηση  και αλλάζει εύκολα σχετικά. Ας υποθέσουμε αρχικά ότι μας λέει να έχουμε πινακες με  size=100 , πώς θα μπούνε οι τιμές απο τη rand  ταξινομημένες δε καταλαβαίνω...

ευχαριστώ

 

Με τα ελάχιστα που θυμάμαι από C, καταρχάς ορίζεις το array, πχ paparies[100]. Αυτό δημιουργεί ένα array με unitialized τιμές ("άδειο").

 

Αυτό που θέλει να κάνεις στο 1, είναι το εξής:

 

Παράγω μια τυχαία τιμή.

Την χώνω στο array.

Κάνω sort το array.

Επαναλαμβάνω μέχρι να γεμίσω το array.

[solarpower]

 

Προσέξτε, το πρόγραμμα θα φροντίζει ο κάθε πίνακας να διατηρεί ταξινομημένα τα στοιχεία του όταν λαμβάνει τιμές για αυτά από τη συνάρτηση rand() – Δηλαδή δεν θα «γεμίζουμε» πρώτα τον πίνακα και μετά θα κάνουμε ταξινόμηση των στοιχείων του

Αυτό αναφέρει η άσκηση paparovic, άρα δεν γίνεται να κάνεις sort μετά την εισαγωγή τιμής!

Το MoronSort δεν το γνωρίζω!

[paparovic]

Αυτό αναφέρει η άσκηση paparovic, άρα δεν γίνεται να κάνεις sort μετά την εισαγωγή τιμής!

 

Εγώ καταλαβαίνω από την εκφώνηση ότι απαγορεύεται να γεμίσω όλο τον πίνακα και μετά να κάνω sort.

[solarpower]

Και τι στόχο θα είχε να κάνει sort σε κάθε γέμισμα τιμής; Αφού δεν υπάρχει κάποιο ζητούμενο από τη άσκηση κατά την εισαγωγή τιμής!