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

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

[55, 46, 44, 34, 28, 18, 14, 12, 10, 8, 4]

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

a, b = b, a

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

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

 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)

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

Ο παρακάτω αλγόριθμος επιλέγει έναν αριθμό από το 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 'Δυστυχώς δεν το βρήκες'

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

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

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

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

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

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

Επιλέξτε έναν πιο συνοπτικό τρόπο εκτέλεσης των παρακάτω εντολών, που δηλώνουν το πρώτο πέρασμα της αύξουσας ταξινόμησης σε μια λίστα 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]

Ο παρακάτω αλγόριθμος βελτιστοποιεί την ταξινόμηση, ώστε όταν η λίστα ταξινομηθεί να μην κάνει άσκοπα περάσματα

def optimizedBubbleSort(A):

        N = len(A)

        isSorted = False

        i = 0

       while i < N-1  and not isSorted:

                isSorted = True

                for j in range(N-1, i, -1):

                        if A[j] < A[j-1]:

                               A[j], A[j-1] = A[j-1], A[j]

                               isSorted = False

                i + = 1

πόσα περάσματα θα γίνουν για τη λίστα [7, 8, 9, 12, 4, 5, 11] χρησιμοποιώντας τη βελτιστοποιημένη ταξινόμηση και πόσα άσκοπα θα γινόταν με τον απλό αλγόριθμο ταξινόμησης;

Η δυαδική αναζήτηση ισχύει για όλους τους τύπους δεδομένων για τους οποίους έχουμε ορίσει του συγκριτικούς τελεστές. Αυτό το χαρακτηριστικό ονομάζεται πολυμορφισμός και είναι από το βασικά πλεονεκτήματα της Python

Η δυαδική αναζήτηση βρίσκει το ζητούμενο πολύ πιο αργά από ότι η σειριακή αναζήτηση

Τι θα εμφανιστεί όταν θα γίνει η κλήση της συνάρτησης binarySearch για τη λίστα: L [7, 9, 15, 67, 77, 85];

def binarySearch(array, key):

        first = 0

       last = len(array) - 1

        pos = 'Δεν υπάρχει'

        while first <= last and pos == -1:

                mid = (first + last) / 2

                if array[mid] == key:

                        pos = mid

                elif array[mid] < key:

                        first = mid + 1

               else:

                       last = mid - 1

        return pos

print binarySearch(L, 5):

 

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

Επιλέξτε το σωστό πρόγραμμα που θα εμφανίζει σε φθίνουσα σειρά ως προς τους βαθμούς, τα ονόματα των μαθητών της τάξης

Θεωρήστε ότι η λίστα nameL με τα ονόματα και η λίστα gradeL με τους βαθμούς είναι γεμάτες

Για την παρακάρω λίστα με 7 αριθμούς ποια θα είναι η τιμή της λίστας μετά από τρία περάσματα, αν χρησιμοποιήσουμε τον αλγόριθμο της αύξουσας ταξινόμησης (φυσαλίδα);

[55, 34, 5, 3, 2, 1, 1]

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

[55, 34, 5, 3, 2, 1, 1]

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