Jump to content



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


ChrisXP

Recommended Posts

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

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

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

#include <iostream>

#include <stdlib.h>

#include <stdio.h>

using namespace std;

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

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";

}

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

Ευχαριστώ

Link to comment
Share on other sites

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

δηλαδή: 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

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

Link to comment
Share on other sites

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

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

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

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

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

βάλε στο google qsort

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

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

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

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

Link to comment
Share on other sites

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;

}

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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)

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

Link to comment
Share on other sites

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ος του καθε στοιχειου τοτε μπορεις να βρεις και την θεση. με πιανεις? ;)

Link to comment
Share on other sites

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

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.