qsort και δυσδιάστατοι πίνακες C++

[ChrisXP]

Καλησπέρα σε όλους

θέλω να κάνω quick sort σε δυσδιάστατο πίνακα και αντιμετωπίζω πρόβλημα στην σύνταξη της qsort.

ο κώδικας για qsort μονοδιάστατου πίνακα:

#include <iostream>

#include <stdlib.h>

#include <stdio.h>

using namespace std;

int compare (const void * a, const void * {

return ( *(int*)a - *(int*)b );

}

int main()

{

int d[100];

for (int q=0;q<101;q++)

{

d[q]=q;

}

d[30]=2;

qsort (d, 100, sizeof(int), compare);

for (int q=0;q<101;q++)

{

f2 << d[q] << "\n";

}

system("PAUSE");

return 0;

}

και αυτό που φτιάχνω για δυσδιάστατο:

int x[20][2];

for(int q=0;q<20;q++)

{

x[q][1] = q+1;

}

x[10][1]=5;

for(int q=0;q<20;q++)

{

f2 << x[q][1] << "\n";

}

qsort (x, 20, sizeof(int), compare);

for(int q=0;q<20;q++)

{

f2 << x[q][1] << "\n";

}

όποιος ξέρει ας απάντησει λίγο γρήγορα γιάτι πρέπει να τελειώσω

Ευχαριστώ

[DarkSaga]

τι θέλεις να κάνει η qsort ακριβώς στον δισδιάστατο?

να ταξινομεί κάθε γραμμή χωριστά η γενικά όλο τον πίνακα ως ένα πεδίο?

[ChrisXP]

θέλω να ταξινομεί την όλες της γραμμές της πρώτης στήλης

δηλαδή: x[20][2] θέλω να ταξινομήσω της τιμές από 0-20 στό 1 ([20][1])

και οι τιμές της 2 στήλης να αλλάξουν σύμφωνα με τα περιεχόμενα της πρώτης.

επειδή μάλλον σε μπέρδεψα περισσότερο

0 1

-1 2

5 3

8 4

-5 5

-9 6

9 7

αυτές θα είναι οι τιμές εγώ θέλω να ταξινομήσω την πρώτη στήλη και να γίνει

-9 6

-5 5

-1 2

0 1

5 3

8 4

9 7

ελπίζω να καταλάβατε τι εννοώ.

[DarkSaga]

ταξινομείς την πρώτη στήλη και

μαζί με κάθε στοιχείο θες να κουβαλας δίπλα και το σωστό του καλα κατάλαβα?

κάνεις sort ως προς τη στήλη

και στο swap που κάνει η συνάρτηση σου βάλε να εναλλάσει και τα 2 στοιχεια της γραμμής όχι μόνο αυτό με το οποίο συγκρίνεις.

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

βάλε στο google qsort

και πάρε την έτοιμη απο κάποιον

για να βλέπεις πως δουλεύει

η qsort του συστήματος δεν σου κάνει εδώ

είναι αδιάφανη.

[ChrisXP]

Φίλε μου επειδή δεν βρήκα κάτι σχετικά με αυτό που ζητάω μήπως μπορείς να μου δώσεις ένα παράδειγμα

[ChrisXP]

τίποτα νεότερο

[unreal]

void quick_sort(double a[], int n)

{

int i, j;

double middle;

do{

i=0;

j=n-1;

middle=a[j/2];

do{

while(a<middle)i++;

while(a[j]>middle)j--;

if(i<j) swap(&a, &a[j]); else if(i>j)break;

i++;

j++;

}while(i<=j);

if((j+1)<(n-1))

{

if(j>0) quick_sort(a,j+1);

a+=i;

n-=i;

}

else

{

if(i<n-1) quick_sort(a+i, n-i);

n=j+1;

}

}while(n>1);

return;

}

[ChrisXP]

thanks παιδιά μήπως ξέρει κανείς ποιά ειναι η καλύτερη εντολή αναζήτησης εγώ ψάχνω για το bsearch και επίσης μήπως ξέρετε πώς την χρησιμοποιώ για δυσδιάστατο πίνακα

[ChrisXP]

int compare_i( const void *f1, const void *f2 )

{

int *farr1 = (int *)f1;

int *farr2 = (int *)f2;

return farr1[0] - farr2[0]; // or use farr1[1] for other element...

}

int X[2000000][3]

bsearch (&key, X, N, sizeof(int)*4, compare_i)

μήπως ξέρει κανείς πώς μπορώ να του πω να μου πει σε ποιά γραμμή του πίνακα βρήκε το αποτέλεσμα

[unreal]

int binary_search(double key, double array[], int n)

{

int index, lower,upper;

lower=0;

upper=n-1;

if((key<array[lower]) || (key>array[upper])) return (EOF);

while(lower<=upper)

{

index=(lower+upper)/2;

if(key==array[index]) return index;

if(key<array[index]) { upper = index-1;}

else{lower = index+1;}

}

return (EOF);

}

Η παραπανω επιστρεφει αυτο που θες. Γινεται ομως και ετσι οπως το κανεις εσυ.

η συναρτηση bsearch() επιστρεφει την διευθυνση μνημης που βρισκεται το στοιχειο που ψαχνεις.

Αρα αφου ξερεις την διευθυνση μνημης της αρχης του πινακα και με την sizeof βρεις και το μεγε8ος του καθε στοιχειου τοτε μπορεις να βρεις και την θεση. με πιανεις?

[ChrisXP]

ok το έκανα αυτό που ήθελα ευχαριστώ για την βοήθεια.

[Skeftomilos]

Ο Unreal έδωσε την πιο αποδοτική λύση για το συγκεκριμένο πρόβλημα. Τι θα συνέβαινε όμως άν ο πίνακας είχε περισσότερες στήλες? Θα κάναμε swap τα data σε όλες τις στήλες για κάθε swap στην πρώτη στήλη? Υπάρχει ένα όριο στον αριθμό των στηλών, μετά το οποίο η μέθοδος αυτή γίνεται ασύμφορη και πρέπει να προτιμηθεί χρήση δεικτών.