python bubblesort και διαδικη αναζητηση

[mr.angelos]

καλησπερα,
δινω πανελλαδικες σε λιγες μερες και θελω να μαθω καλα την bubblesort και την διαδικη αναζητηση.
το ξερω ειναι στο βιβλιο του σχολειου και την εχω διαβασει αρκετες φορες και εχω καταλαβει περιπου τι κανει.
Θα ηθελα αν καποιος μπορει να μου πει ενα κολπο ωστε να την μαθω οχι παπαγαλλια που θελλουν στις εξετασεις αλλα να την μαθω καλα και να μου μεινει. 

[kaliakman]

34 λεπτά πριν, mr.angelos είπε

καλησπερα,
δινω πανελλαδικες σε λιγες μερες και θελω να μαθω καλα την bubblesort και την διαδικη αναζητηση.
το ξερω ειναι στο βιβλιο του σχολειου και την εχω διαβασει αρκετες φορες και εχω καταλαβει περιπου τι κανει.
Θα ηθελα αν καποιος μπορει να μου πει ενα κολπο ωστε να την μαθω οχι παπαγαλλια που θελλουν στις εξετασεις αλλα να την μαθω καλα και να μου μεινει. 

Η δυαδική είναι πολύ εύκολο να την καταλάβεις.

Σκέψου ότι έχεις έναν τηλεφωνικό κατάλογο και θες να βρεις ένα όνομα πχ Παπαδόπουλος:

Επειδή δεν ξέρεις που ακριβώς είναι ανοίγεις τυχαία τον κατάλογο σε ένα σημείο (στον αλγόριθμο μας τον ανοίγεις ακριβώς στην μέση)
Βρίσκεις ας πούμε το όνομα Κωνσταντίνου. 
Ξέρεις ότι το Παπαδόπουλος είναι μετά το Κωνσταντίνου οπότε σίγουρα βρίσκεται δεξιά από το τυχαίο σημείο που τον άνοιξες (σε εμάς η μέση) αν ίσχυε το ανάποδο πχ έψαχνες το όνομα Βασιλείου ξέρεις ότι είναι αριστερά από το Κωνσταντίνου.
Τώρα σκέψου οτι κόβεις τον κατάλογο αριστερά από το τυχαίο σημείο αφού ξέρεις ότι δεν είναι εκεί.
Ξανακάνεις την ίδια διαδικασία στον "καινούριο" κατάλογο μέχρι να βρεις αυτό που θέλεις.
 

 

Για bubble sort εδώ είσαι

 

Επεξ/σία 9 Ιουνίου 2020 από kaliakman

[Lanike71]

Like για το folk dance.

Σημειωτέον, έχει και για άλλους αλγορίθμους παρόμοια βίντεο.

[k33theod]

Προσπαθώ να το εξηγήσω και εγώ γιατί αυτό με το τυχαίο ίσως τον μπερδέψει.

Κατ αρχήν για να κάνεις binary search πρέπει οι αριθμοί(στοιχεία) σου να είναι ταξινομημένοι, αυξάνονται  ή μειώνονται όταν έχεις δηλαδή μέσα  4,3,5 δεν γίνεται.

Έστω ότι είναι σε άυξουσα σειρά.  Έχεις 2 δείκτες από και εώς τον από τον ονομάζεις l=left  και τον εώς τον ονομάζεις r=right. Και κάνεις μια διαδικασία όσο το left είναι μικρότερο του right. Αυτό γίνεται γιατί τα left και right είναι μεταβλητά μέσα στη διαδικασία τα αλλάζεις.

Η διαδικασία είναι ώς εξης.

a. Ελέγχεις πάντα το στοιχείο στο κέντρο mid=l+(r-l) / 2  (δηλαδή το κέντρο είναι το αριστερό + το μισό της διαφοράς) σε σχέση με τον αριθμό σου χ ασ πούμε. Υπάρχουν μόνο 3 περιπτώσεις

1. Η τιμή του πίνακα στη θέση mid π[mid]=x οπότε λες το βρήκα είναι στη θέση mid.

2. π[mid]<χ οπότε λές το στοιχείο μου είναι ακόμα πιο δεξιά και ορίzεις νέο left το mid+1 δηλαδή l=mid+1 αφού τη θέση mid την έχεις ήδη ψάξει.

3.  π[mid]>x οπότε θες να ψάξεις αριστερά και λες r=mid-1.

def binarySearch(arr, l, r, x): 
  
    while l <= r: 
  
        mid = l + (r - l) // 2; 
          
        # Check if x is present at mid 
        if arr[mid] == x: 
            return mid 
  
        # If x is greater, ignore left half 
        elif arr[mid] < x: 
            l = mid + 1
  
        # If x is smaller, ignore right half 
        else: 
            r = mid - 1
      
    # If we reach here, then the element 
    # was not present 
    return -1

 

Επεξ/σία 10 Ιουνίου 2020 από k33theod

[mr.angelos]

Ευχαριστω παρα πολυ για τις απαντησεις σας.
ουσιαστικα πρεπει να μαθω την λειτουργεια του κωδικα καλα.
Απλα στις εξετασεις εχουν την απαιτηση να ξερουμε binary search,bubble sort κτλ απεξω ολο τον κωδικα.
Το ξερω χρειαζεται αλλα ειναι λιγο καπως ειδικα εκεινη την ωρα με το αγχος.

οποτε πρωτα πρεπει να γινει η bubble sort διοτι η δυαδικη αναζητηση δεν μπορει να γινει σε μη ταξινομημενη λιστα, σωστα;

[Lanike71]

5 λεπτά πριν, mr.angelos είπε

Απλα στις εξετασεις εχουν την απαιτηση να ξερουμε binary search,bubble sort κτλ απεξω ολο τον κωδικα

Μη μάθεις κώδικα απ' έξω.

Μάθε τι δουλειά κάνει και πώς την κάνει, το κάθε σορτάρισμα, αν έχουν 2-3 που πρέπει να ξέρετε.

Ο κώδικας βγαίνει μετά.

Επεξ/σία 10 Ιουνίου 2020 από Lanike71

[k33theod]

Αν αφαιρέσουμε τα σχόλια από τον παραπάνω κώδικα και αντικαταστήσουμε το mid με m γίνεται και το binarySearch με bS

def bS(a, l, r, x): 
    while l <= r: 
        m = l + (r - l) // 2
        if a[m] == x: 
            return m 
        elif a[m] < x: 
            l = m + 1
        else: 
            r = m - 1
    return -1

πιό κοντό δεν γίνεται

[mr.angelos]

11 ώρες πριν, k33theod είπε

Αν αφαιρέσουμε τα σχόλια από τον παραπάνω κώδικα και αντικαταστήσουμε το mid με m γίνεται και το binarySearch με bS

def bS(a, l, r, x): 
    while l <= r: 
        m = l + (r - l) // 2
        if a[m] == x: 
            return m 
        elif a[m] < x: 
            l = m + 1
        else: 
            r = m - 1
    return -1

πιό κοντό δεν γίνεται

Ευχαριστω πολυ για την απαντηση.
η συναρτηση ειναι σε python 3? 
ρωταω γιατι εμεις εξεταζομαστε σε python 2.7 και θυμαμαι λιγο διαφορετικο τον κωδικα.