Πρόγραμμα στη C++ crashάρει

[Επισκέπτης]

Καλησπέρα, έχω μία εργασία για τη σχολή η οποία ζητείται σε C++. Την έχω ψιλοξεχάσει αλλά googlάροντας προχωράω. Έχω εδώ ένα πρόβλημα και προσπαθώ να καταλάβω γιατί κρασάρει στη while που έχω μέσα στη μέθοδο για την quicksort (την πήρα έτοιμη, δεν είνα η υλοποίηση του αλγορίθμου ο σκοπός). Όπως βλέπετε στη main φτιάχνω ένα array μεγέθους n στο range [1,10^10]. Μετά πρέπει να υλοποιήσω τρεις αλγορίθμους ταξινόμησης για να κάνω διάφορα πράγματα. Στη while όμως μου κρασάρει το πρόγραμμα για κάποιο λόγο. Οι τιμές είναι long long γιατί όπως βλέπετε στο εύρος τιμών οι τιμές φτάνουν πολύ υψηλές. Ορίστε και ο κώδικας:

#include <iostream>
#include <cmath>
#include <stdlib.h>

using namespace std;

void quicksort(long long arr[],long long left,long long right,int ch) {
      long long i = left;
      long long j = right;
      long long tmp;
      long long pivot = arr[(left+right)/2];
      /* partition */
      while (i<=j){ //Εδώ πρέπει να ΄ναι το πρόβλημα.
            while (arr[i]<pivot)
                  i++;
            while (arr[j]>pivot)
                  j--;
            if (i<=j){
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      }
      /* recursion */
      if (left < j)
            quicksort(arr,left,j,ch);
      if (i < right)
            quicksort(arr,i,right,ch);
      cout << arr[ch-1];
}

void randomized(long long arr[],int ch){

}

void worstCase(long long arr[],int ch){

}

int main()
{
    cout << "- - - - - - - - - - - - - - - - - - - - - " << endl;
    cout << "Which method would you like to implement?" << endl;
    cout << "" << endl;
    cout << "1. Quicksort method" << endl;
    cout << "2. Randomized method" << endl;
    cout << "3. Worst-case method" << endl;
    cout << "" << endl;
    cout << "Give an option(1-3): " << endl;
    int choice;
    cin >> choice;
    cout << "" << endl;
    cout << "Give an array input(size): " << endl;
    int input;
    cin >> input;
    long long arr[input];
    for (int i=0;i<input;i++){
        arr[i] = rand() % (10000000000 + 1 - 1) + 1;
    }
    long int ch;
    if (choice==1){
        cout << "" << endl;
        cout << "You have chosen Quicksort method. Give which (smallest) element you 'd like to get: ";
        cout << "" << endl;
        cin >> ch;
        quicksort(arr,arr[0],arr[input-1],ch);
    }
    else if (choice==2){
        cout << "" << endl;
        cout << "You have chosen Randomized method. Give which (smallest) element you 'd like to get: ";
        cout << "" << endl;
        cin >> ch;
        randomized(arr,ch);
    }
    else if (choice==3){
        cout << "" << endl;
        cout << "You have chosen Worst-case method. Give which (smallest) element you 'd like to get: ";
        cout << "" << endl;
        cin >> ch;
        worstCase(arr,ch);
    }
    return 0;
}

 

Επεξ/σία 4 Απριλίου 2018 από Επισκέπτης

[stial]

Δοκίμασε να βάλεις να σου τυπώνει κάθε φορά μέσα στα while τους μετρητές σου , η κότσαρε κανα break me συνθήκη ωστέ να καταλάβεις που ακριβώς γίνεται η μανούρα. Μου έχει τύχει να μην μπαίνει καν στο loop για άκυρο λόγο και να νομίζω ότι φταίει το loop ενώ το πρόβλημα ήταν ας πούμε στην δήλωση τον μεταβλητών. Επίσης βλέπω την ίδια συνθήκη και στο while σου αλλά και μέσα στο άλλο while με if.. θα το προσέγγιζα αλλιώς γιατί μπορεί να παίζεται overlap εκεί.

[Επισκέπτης]

Έβαλα cout σε διάφορα σημεία για να δω που προκύπτει το crash και έτσι συμπέρανα ότι γίνεται στη while. Ο αλγόριθμος για τον quicksort είναι έτοιμος και δε νομίζω να είναι λάθος. Σκέφτομαι μήπως γίνεται κανένα μπέρδεμα με τις μεταβλητές που είναι long long...

[albNik]

13 λεπτά πριν, kaifman είπε

φτιάχνω ένα array μεγέθους n στο range [1,10^10].

Δε νομίζω να δέχεται τέτοιο μέγεθος.
Επίσης το μέγεθος του πίνακα (input) πρέπει να είναι γνωστό από πριν, όχι να το δίνει ο χρήστης.  

[Επισκέπτης]

Η εκφώνηση του προβλήματος γράφει:

Αναφορά σε κείμενο

Προγραμματισμός μιας διαδικασίας που θα κατασκευάζει έναν πίνακα μεγέθους n (παράμετρος) με τυχαία στοιχεία στο διάστημα [1...10^10]

Ζητήθηκε σε C ή C++. Αυτό που λες για γνωστό μέγεθος ισχύει στη C σίγουρα, στη C++ νομίζω επιτρέπεται.

Edit: Οκ βρήκα τι πρέπει να φταίει. Τα ορίσματα left και right αναφέρονται σε θέσεις του πίνακα, όχι τιμές!

Επεξ/σία 4 Απριλίου 2018 από Επισκέπτης

[Kercyn]

Γιατί ταλαιπωρείσαι με arrays ενώ υπάρχει το vector;

[Επισκέπτης]

1 λεπτό πριν, Kercyn είπε

Γιατί ταλαιπωρείσαι με arrays ενώ υπάρχει το vector;

Γιατί δε γνωρίζω vectors φίλε Kercyn. Χώρια που η εκφώνηση ζητάει Array. Θέλει να κάνω μετά συγκρίσεις, είναι σαν πειραματική εργασία.

[Kercyn]

6 λεπτά πριν, kaifman είπε

Γιατί δε γνωρίζω vectors φίλε Kercyn. Χώρια που η εκφώνηση ζητάει Array. Θέλει να κάνω μετά συγκρίσεις, είναι σαν πειραματική εργασία.

Είναι πάρα πολύ απλό και θα σου διευκολύνει τη ζωή

Πάντως αφού αυτός που έγραψε την άσκηση είναι κακός και ζητάει arrays, μπορείς να χρησιμοποιήσεις την έτοιμη quicksort και να μην παιδεύεσαι με random υλοποιήσεις από το Ιντερνέτ, για να έχεις κι εσύ το κεφάλι σου ήσυχο.

[Επισκέπτης]

Πάντως τις έχω αφήσει τις C/C++ από το 1ο έτος.

Έβγαλα άκρη με την quicksort με τη διόρθωση που ανέφερα παραπάνω.

[imitheos]

1 ώρα πριν, kaifman είπε

Καλησπέρα, έχω μία εργασία για τη σχολή η οποία ζητείται σε C++. Την έχω ψιλοξεχάσει αλλά googlάροντας προχωράω. Έχω εδώ ένα πρόβλημα και προσπαθώ να καταλάβω γιατί κρασάρει στη while που έχω μέσα στη μέθοδο για την quicksort (την πήρα έτοιμη, δεν είνα η υλοποίηση του αλγορίθμου ο σκοπός). Όπως βλέπετε στη main φτιάχνω ένα array μεγέθους n στο range [1,10^10]. Μετά πρέπει να υλοποιήσω τρεις αλγορίθμους ταξινόμησης για να κάνω διάφορα πράγματα. Στη while όμως μου κρασάρει το πρόγραμμα για κάποιο λόγο. Οι τιμές είναι long long γιατί όπως βλέπετε στο εύρος τιμών οι τιμές φτάνουν πολύ υψηλές. Ορίστε και ο κώδικας:

void quicksort(long long arr[],long long left,long long right,int ch) {
      long long i = left;
      long long j = right;
      long long tmp;
      long long pivot = arr[(left+right)/2];
      /* partition */
      while (i<=j){ //Εδώ πρέπει να ΄ναι το πρόβλημα.
            while (arr[i]<pivot)
                  i++;
            while (arr[j]>pivot)
                  j--;
      }
}

int main()
{
    long long arr[input];

        quicksort(arr,arr[0],arr[input-1],ch);  
}

 

Άσχετο αλλά υποστηρίζει VLAs η C++ ?

Όπως βλέπεις και από τον κώδικα της συνάρτησής σου, τα left (i), right (j) αναφέρονται στο range των θέσεων του πίνακα που θα δουλέψεις. Εσύ όμως μέσα στην main καλείς την συνάρτηση δίνοντας σαν όρισμα τις τιμές της θέσης 0 και input-1 οι οποίες έχουν τυχαία τιμή. Έτσι λοιπόν μέσα στο while με τις εκφράσεις arr, arr[j] προσπελαύνεις θέσεις πολύ έξω από τον πίνακα και για αυτό παίρνεις segmentation fault.

Αν αλλάξεις το κάλεσμα της συνάρτησης ώστε να τρέχει με 0, input-1 τότε θα παίξει όπως θέλεις.

[k33theod]

Kaifman

Εντάξει λες ότι η υλοποίηση της quicksort  δεν είναι ο σκοπός της άσκησης

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

Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
Introduction to Algorithms
Third Edition
δεν το βγάζει όμως σωστά στην επικόλληση

Η quicksort δεν έχει πχ κανένα while η partition είναι ξεχωριστή συνάρτηση με επιστρεφόμενη τιμή, έχει 3 παραμέτρους και όχι 4, τέλως πάντων προσπάθησα να γράψω σε c/ c++ την υλοποίηση του βιβλίου και  νομίζω ότι είναι αρκετά κοντά, και σε μερικά παραδείγματα που έκανα φαίνεται να δουλεύει κανονικά

void quicksort(long long A[], int p, int r) {
    if (p < r) {
        int q = partition (A, p, r);
        quicksort(A, p, q-1);
        quicksort(A, q, r);
    }

int partition(long long A[], int p, int r) {
    long long x = A[r];
    int i = p-1;
    long long temp {0};
    for (int j = p; j <= r-1; j++) {
        if (A[j] <= x) {
            i = i+1;
            temp = A[j];
            A[j]=A[i];
            A[i]=temp;
        }
    }
    temp = A[i+1];
    A[i+1] = A[r];
    A[r] = temp;
    return i+1;
}

 

Επεξ/σία 5 Απριλίου 2018 από k33theod