Ο αλγόριθμος της σειριακή αναζήτησης μπορεί να χρησιμοποιηθεί μόνο σε ταξινομημένες λίστες

Η αντιμετάθεση (αμοιβαία αλλαγή τιμών των μεταβλητών α, β) γίνεται στην Pyhton με την απλή εντολή:

a, b = b, a

Πως μπορεί να γίνει με επιπλέον μεταβλητή;

Ο παρακάτω αλγόριθμος δυαδικής αναζήτησης χρησιμοποιείται σε λίστες με φθίνουσα ταξινόμηση:

def binarySearch(lista, key):

        first = 0

        last = len(lista) - 1

        found = False

        while not found and first <= last:

                mid = (first + last) / 2

                if lista[mid] == key:

                      found = True

                elif lista[mid] > key:

                      first = mid + 1

                else:

                     last = mid - 1

        return found

Πόσα περάσματα θα γίνουν για την αύξηση ταξινόμηση της λίστας:

[28, 28, 28, 28, 28, 28, 28, 30, 30, 30, 30]

Τι θα εμφανίσει το παρακάτω πρόγραμμα;

 def check_D(mylist):

        d = True

        i = 0

        N = len(mylist)

        while d and i < N-1:

                if myList[i] < myList[i + 1]:

                        d = False

                i = i + 1

        return d

L = [20, 12, 4, 2]

print check_D(L)

Στην παρακάτω αύξουσα ταξινομημένη λίστα  L ψάχνουμε το 45.

η πρώτη σύγκριση για τον αριθμό 45 θα είναι με το στοιχείο στο δείκτη: (0+13)/2 =6 άρα με τον L[6] άρα με το 35.

Ποιος είναι ο επόμενος αριθμός που θα συγκριθεί το 45;

Ο παρακάτω αλγόριθμος επιλέγει έναν αριθμό από το 1 έως και το 1000 και ο χρήστης προσπαθεί να τον μαντέψει με τη βοήθεια μηνυμάτων από το Η/Υ (αν ο αριθμός που έδωσε ο χρήστης είναι μικρότερος ή μεγαλύτερος). Βελτιώστε τον αλγόριθμο στην  while ώστε ο χρήστης να σκεφτεί με καλύτερη στρατηγική και να μειώσει τις προσπάθειές του για να βρει τον κρυφό αριθμό. Οι προσπάθειες που θα μπορεί να δώσει είναι 10

import random

secret_number = random.randint(1, 1000)  # ο αριθμός που επιλέγει τυχαίο ο Η/Υ

guesses = 0   #προσπάθειες

found = False

while not found:

        guess = input(' Μάντεψε τον αριθμό')  # Ο αριθμός που δίνει ο χρήστης

        guesses + = 1

        if guess == secret_number:

                print 'Μπράβο το βρήκες με', guesses, 'προσπάθειες'

                found = True

        else:

                if guess < secrtet_number:

                        print ' Ο αριθμός σου είναι μικρότερος από τον ζητούμενο'

                else:

                        print ' Ο αριθμός σου είναι μεγαλύτερος από τον ζητούμενο'  

#Τέλος της while

if  found :  # αφού αν είναι True αρκεί (μπορούμε και found == True:)

        print 'Μπράβο το βρήκες με ', guesses, ' προσπάθειες'

else:

        print 'Δυστυχώς δεν το βρήκες'

Η δυαδική αναζήτηση μπορεί να γίνει σε στοιχεία που βρίσκονται σε κάποια λογική διάταξη, είτε αυτά είναι αριθμοί είτε αλφαριθμητικά

Τι θα εμφανίσει το παρακάτω πρόγραμμα;

 def isAscending(mylist):

        ascending = True

        i = 0

        N = len(mylist)

        while ascending and i < N-1:

                if myList[i] > myList[i + 1]:

                        ascending = False

                i = i + 1

        return ascending

L = [12, 40, 58, 80, 79]

print isAscending(L)

Η δυαδική αναζήτηση μπορεί να γίνει μόνο σε ταξινομημένες λίστες με αριθμούς, όχι σε λίστες με συμβολοσειρές

Επιλέξτε έναν πιο συνοπτικό τρόπο εκτέλεσης των παρακάτω εντολών, που δηλώνουν το πρώτο πέρασμα της αύξουσας ταξινόμησης σε μια λίστα 5 στοιχείων:

if students[4] < students[3]:

        students[4], students[3] = students[3], students[4]

if students[3] < students[2]:

        students[3], students[2] = students[2], students[3]

if students[2] < students[1]:

        students[2], students[1] = students[1], students[2]

if students[1] < students[0]:

        students[1], students[0] = students[0], students[1]

Σε μια ταξινομημένη λίστα 1000 στοιχείων, πόσες είναι οι περισσότερες συγκρίσεις που θα χρειαζόταν για να βρεθεί οποιοδήποτε στοιχείο χρησιμοποιοώντας τη δυαδική αναζήτηση;

Στην παρακάτω αύξουσα ταξινομημένη λίστα  L ψάχνουμε το 45.

η πρώτη σύγκριση για τον αριθμό 45 θα είναι με το στοιχείο στο δείκτη: (0+13)/2 =6 άρα με τον L[6] άρα με το 35.

επειδή 45>35 θα ελέγξει από το δείκτη 6+1 = 7 έως το τέλος της λίστας.

Άρα ο επόμενος έλεγχος θα είναι με το στοιχείο στο δείκτη: (7 + 13) / 2 = 10, άρα με το 60

Με ποιο στοιχείο θα ελεγχθεί μετά;

Δίνεται η λίστα με τους αριθμούς [60, 38, 98, 54, 32, 90, 20] . Πως θα γίνει η λίστα μετά από 3 περάσματα μιας αύξουσας ταξινόμησης;

Σε μια ταξινομημένη λίστα 16 στοιχείων, πόσες είναι οι περισσότερες συγκρίσεις που θα χρειαζόταν για να βρεθεί οποιοδήποτε στοιχείο χρησιμοποιοώντας τη δυαδική αναζήτηση;

Ο αλγόριθμος της Σειριακή αναζήτησης θα ελέγξει όλα τα στοιχεία σε μια λίστα ακόμα και αν είναι ταξινομημένη

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

Πόσα περάσματα θα γίνουν για την αύξηση ταξινόμηση της λίστας:

[28, 28, 28, 6, 6, 6, 6, 6, 6, 6, 6]

Δίνεται το πρόβλημα: Να βρεθούν οι τρεις μεγαλύτεροι αριθμοί σε μια λίστα

Τι λύση θα επιλέγατε;

Ο αλγόριθμος ταξινόμησης ευθείας ανταλλαγής είναι γνωστός και ως αλγόριθμος ταξινόμησης φυσαλίδας γιατί σε κάθε πέρασμα το μικρότερο στοιχείο ανεβαίνει, όπως συμβαίνει και σε και μια φυσαλίδα, στην επιφάνεια του νερού