Sorting in place - Less possible swaps

Ο τομέας μας. ;)
Απάντηση
Giannisl9
Δημοσιεύσεις: 5
Εγγραφή: Σάβ Νοέμ 26, 2011 12:59 am

Sorting in place - Less possible swaps

Δημοσίευση από Giannisl9 »

Καλησπέρα,

θέλω να γράψω ένα πρόγραμμα το οποίο να βρίσκει τις ελάχιστες δυνατές εναλλαγές για να ταξινομηθεί ένας πίνακας... Όποιος έχει καμιά ιδέα ας μου προτείνει κάτι...

Ευχαριστώ,
Τα λέμε,
Giannisl9
Άβαταρ μέλους
zaxeilasfc
Δημοσιεύσεις: 118
Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
Τοποθεσία: Macintosh HD

Re: Sorting in place - Less possible swaps

Δημοσίευση από zaxeilasfc »

Giannisl9 έγραψε:Καλησπέρα,

θέλω να γράψω ένα πρόγραμμα το οποίο να βρίσκει τις ελάχιστες δυνατές εναλλαγές για να ταξινομηθεί ένας πίνακας... Όποιος έχει καμιά ιδέα ας μου προτείνει κάτι...

Ευχαριστώ,
Τα λέμε,
Giannisl9
Μια εύκολη υλοποίηση , και μάλλον η ταχύτερη, είναι να ελέγχεις σε κάθε επανάληψη αν έγινε ΕΣΤΩ ΚΑΙ ΜΙΑ ανταλλαγή των στοιχείων του πίνακα. Απο την στιγμή που σε κάποια επανάληψη η μεταβλητή που θα το ελέγχει (λογική, μάλλον) παραμείνει False τότε σημαίνει οτι δεν ανταλλάχθηκε κάποιο στοιχείο.

( Υ.Γ.: Μιλάμε για bubblesort πάντα... έτσι;; γιατί αν εννοείς το πρόβλημα του hellenico, δεν έχει να κάνει καμία σχέση!)
Giannisl9
Δημοσιεύσεις: 5
Εγγραφή: Σάβ Νοέμ 26, 2011 12:59 am

Re: Sorting in place - Less possible swaps

Δημοσίευση από Giannisl9 »

zaxeilasfc έγραψε:
Giannisl9 έγραψε: ( Υ.Γ.: Μιλάμε για bubblesort πάντα... έτσι;; γιατί αν εννοείς το πρόβλημα του hellenico, δεν έχει να κάνει καμία σχέση!)
Εμ δε νομίζω ότι έχει σχέση αν είναι του hellenico ή όχι... Η bubble sort κάνει από μόνη της περιττά swaps οπότε το να βάλω ένα μετρητή για να υπολογίζει τα swaps αυτά δεν νομίζω να είναι η καλύτερη ιδέα...

Τα λέμε,
Giannisl9

(ΥΣ: Ξαναδές τι ρωτάω...)
Άβαταρ μέλους
zaxeilasfc
Δημοσιεύσεις: 118
Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
Τοποθεσία: Macintosh HD

Re: Sorting in place - Less possible swaps

Δημοσίευση από zaxeilasfc »

Σε έναν πίνακα με στοιχεία " 2, 1, 3 , 6 , 9 ,10" νομίζω οτι οι επαναλήψεις που θα γίνουν είναι ΜΙΑ. Διότι, στον παρακάτω κώδικα, με το που δει οτι δεν έγινε ανταλλαγή, θα σταματήσει.

Κώδικας: Επιλογή όλων

#include <iostream>
#define n  6

using namespace std;

int main(void)
{
    int counter=0;
    int array[n];
    bool swap=true;
    bool changedone = false;
    int i,j,temp;
    array[0] = 2;
    array[1] = 1;
    array[2] = 3;
    array[3] = 6;
    array[4] = 9;
    array[5] = 10;
    i=1;
    temp=0;
    while (swap == true && i<n) {
        swap = false ;    
        for (j=n-1; j>=i; j--) {
                if (array[j-1]>array[j]) {
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                    swap = true;
                }
                else
                {
                    swap = false;
                }
                if (swap == true) {
                    changedone = true;
                }
            }
            if (changedone == true) {
                counter++;
            }
        i++;
        changedone = false;
    }
    cout<<counter<<endl;

}
Ελπίζω ο κώδικάς μου να είναι κατανοητός. Αν έχεις απορίες ρώτα με.
Giannisl9
Δημοσιεύσεις: 5
Εγγραφή: Σάβ Νοέμ 26, 2011 12:59 am

Re: Sorting in place - Less possible swaps

Δημοσίευση από Giannisl9 »

Ας πούμε ότι παίρνουμε τον πίνακα χ[] ο οποίος έχει 3 στοιχεία (χ[3]={3,2,1})
Αλγόριθμός σου θα έκανε τα εξής:
1. Είναι το χ[1] > του χ[2]; --> Ναι, οπότε swap=true(χ[3]={3,1,2})
2. Είναι το χ[0] > του χ[1]; --> Ναι, οπότε swap=true(x[3]={1,3,2})
3. changedone=true οπότε counter++; (counter=1)
4. Είναι το χ[1] > του χ[2]; --> Ναι, οπότε swap=true(x[3]={1,2,3})
5. changedone=true οπότε counter++; (counter=2)

Ο αριθμός που βρίσκει λοιπόν δεν αντιπροσωπεύει τις ελάχιστες δυνατές κινήσεις εφόσον στο παράδειγμα αυτές είναι ΜΙΑ αφού 3,2,1 ---> 1,2,3 αν 3<-->1 ...

Τα λέμε,
Giannisl9
Άβαταρ μέλους
zaxeilasfc
Δημοσιεύσεις: 118
Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
Τοποθεσία: Macintosh HD

Re: Sorting in place - Less possible swaps

Δημοσίευση από zaxeilasfc »

Giannisl9 έγραψε:Ας πούμε ότι παίρνουμε τον πίνακα χ[] ο οποίος έχει 3 στοιχεία (χ[3]={3,2,1})
Αλγόριθμός σου θα έκανε τα εξής:
1. Είναι το χ[1] > του χ[2]; --> Ναι, οπότε swap=true(χ[3]={3,1,2})
2. Είναι το χ[0] > του χ[1]; --> Ναι, οπότε swap=true(x[3]={1,3,2})
3. changedone=true οπότε counter++; (counter=1)
4. Είναι το χ[1] > του χ[2]; --> Ναι, οπότε swap=true(x[3]={1,2,3})
5. changedone=true οπότε counter++; (counter=2)

Ο αριθμός που βρίσκει λοιπόν δεν αντιπροσωπεύει τις ελάχιστες δυνατές κινήσεις εφόσον στο παράδειγμα αυτές είναι ΜΙΑ αφού 3,2,1 ---> 1,2,3 αν 3<-->1 ...

Τα λέμε,
Giannisl9
Τότε προφανώς αναφέρεσε στην άσκηση του Hellenico η οποία δεν λύνεται έτσι. Αυτό που σου δίνω εγώ ειναι η βέλτιστη ταξινόμηση φυσαλίδας που μπορεί να γίνει.
Με ποιά μαγική μέθοδο αποφάσησες οτι το 3 θα ανταλλαχθεί με το 1;;
Αυτό που κάνει την άσκηση του Hellenico να διαφέρει είναι οτι έχεις keys. Αν εξακολουθείς να υποστηρίζεις οτι δεν αναφέρεσε σε αυτήν, και σε ενδιαφέρει η ταξινόμηση με τα λιγότερα swaps για δοκίμασε σε παρακαλώ αυτό που μου είπες στο ποστ σου σε έναν πίνακα {1,8,0,9,3,4,5,6,2,7}. . .
Ποια θα ήταν η απάντηση;; σε πόσα βήματα γίνεται;; ξέρεις κάποια ταξινόμηση να απευθύνεται σε αμοιβαίες ανταλλαγές;; Αν ναι τότε νομίζω πως τσάμπα παλεύουμε τόσα χρόνια να βρουμε την βέλτιστη καθώς η μέθοδός σου έχει πολυπλοκότητα O(n/2)!! (Αμοιβαίες ανταλλαγές των n/2 στοιχείων με τα υπόλοιπα n/2.

Φιλικά, Ιωάννης
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Sorting in place - Less possible swaps

Δημοσίευση από userresu »

Αν τα στοιχεία του πίνακα είναι όλα διαφορετικά μεταξύ τους, μπορεί να γίνει σε O(NlogN). Αρχικά τα ταξινομείς σε έναν καινούριο πίνακα, ώστε να ξέρεις την θέση που θα έπρεπε να βρίσκεται το κάθε στοιχείο (*). Ο αλγόριθμος με τα ελάχιστα swaps είναι πολύ απλός: Όσο υπάρχει ένα στοιχείο που δεν βρίσκεται στη θέση του, βάλτο στη θέση που θα έπρεπε να είναι. Το γιατί αυτό είναι σωστό δεν είναι το ίδιο εύκολο: Έστω Α(i) (1<=i<=N) η θέση που θα έπρεπε να βρίσκεται το στοιχείο που βρίσκεται τώρα στην i-οστή θέση. Σε έναν γράφο με Ν κόμβους αριθμημένους από 1 μέχρι Ν, βάλε ένα κατευθυνόμενο βελάκι από το i στο A(i) για κάθε i. Εύκολα μπορείς να δείς ότι σχηματίζονται κάποιοι κύκλοι χωρίς κοινά στοιχεία μεταξύ τους. Αν υπάρχουν Ν κύκλοι τότε Α(i)=i για κάθε i άρα ο πίνακας είναι ταξινομημένος. Διαφορετικά, ένα swap είναι στην ουσια μία ανταλλαγή των κατευθύνσεων από 2 βελάκια. Δηλαδή πχ τα βελάκια (1->2) και (4->5) να γίνουν (1->5) και (4->2). Αν τα 2 βελάκια βρίσκονται σε διαφορετικούς κύκλους, τότε οι 2 κύκλοι ενώνονται άρα έχουμε έναν κύκλο λιγότερο. Αν βρίσκονται στον ίδιο κύκλο, τότε ο κύκλος χωρίζεται σε 2 νέους κύκλους, άρα έχουμε έναν κύκλο περισσότερο. Προφανώς μας βολεύει πάντα να κάνουμε τη 2η κίνηση, αφού θέλουμε τελικά Ν κύκλους και έχουμε λιγότερους. Συνεπώς η απάντηση είναι N-Κ, όπου Κ το πλήθος των κύκλων στον αρχικό γράφο.

(*): Εδώ "χαλάει" το πράγμα όταν υπάρχουν ίδια στοιχεία, γιατί υπάρχουν περισσότερες από μία πιθανές θέσεις για το καθένα στην τελική διάταξη. Αν πάρεις όλες τις δυνατές περιπτώσεις για τις τελικές θέσεις των στοιχείων, ο αλγόριθμος θα είναι μεν σωστός, αλλά αργός (το πόσο αργός εξαρτάται από το πλήθος των ίδιων στοιχείων). Δεν ξέρω αν υπάρχει αποδοτικός αλγόριθμος σε αυτή την περίπτωση και μου φαίνεται αρκετά δύσκολο πρόβλημα (Ίσως και NP-complete).
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Sorting in place - Less possible swaps

Δημοσίευση από userresu »

Στο παράδειγμα θα δουλέψει ως εξής:
{1,8,0,9,3,4,5,6,2,7}
{8,1,0,9,3,4,5,6,2,7}
{2,1,0,9,3,4,5,6,8,7}
{0,1,2,9,3,4,5,6,8,7}
{0,1,2,7,3,4,5,6,8,9}
{0,1,2,6,3,4,5,7,8,9}
{0,1,2,5,3,4,6,7,8,9}
{0,1,2,4,3,5,6,7,8,9}
{0,1,2,3,4,5,6,7,8,9}
Απάντηση