Μάθημα : Προγραμματισμός Υπολογιστών Γ' ετος 2025-2026

Ο αλγόρισθμος της δυαδικής αναζήτησης

Δυαδική αναζήτηση με επιστροφή θέσης 

Η λύση του βιβλίου με τροποποίηση ώστε να επιστρέφει την θέση του αναζητούμενου

def binarySearch( array, key ) :#array: η λίστα και key: το αναζητούμενο
    first = 0
    last = len(array) - 1
    while first <= last:
       mid = ( first + last ) / 2
       if array[ mid ] == key :
          return mid #Επιστρέφει την θέση του αναζητούμενου στην λίστα
       elif array[ mid ] < key :
          first = mid + 1
       else :
          last = mid - 1
    return -1 #Επιστρέφει -1 όταν δεν υπάρχει το αναζητούμενο στην λίστα

def anazitisi(A,key):#Με αλλον τρόπο  
N=len(A)
pos=-1
first=0
last=N-1
while first<=last and pos==-1:
      mid=(first+last)/2
      if A[mid]==key:
           pos=mid
     elif A[mid]<key:
           first=mid+1
     else:
           last=mid-1
return pos

Αλγόριθμος της ταξινόμησης ανταλλαγής (Φυσαλίδα)

Ο αλγόριθμος του βιβλίου αλλιώς

Στο βιβλίο δίνεται η παρακάτω λύση που τοποθετεί τον μικρότερο αριθμό στην αρχή και επαναλαμβάνει την διαδικασία για το υπόλοιπο τμήμα της λίστας:

N = len(A)
for i in range( N-1 ): # range(0, N–1, 1)
    for j in range( N-1 , i , -1 ): # μέχρι και i–1
        if A[ j ] < A[ j-1 ] :
             A[ j ] , A[ j-1 ] = A[ j-1 ] , A[ j ]

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

N = len(A)
for i in range( N-1,0,-1 ): 
    for j in range( 0 , i): 
        if A[ j ] > A[ j+1 ] :
              A[ j ] , A[ j+1 ] = A[ j+1 ] , A[ j ]

Ο αλγόριθμος του βιβλίου ως συνάρτηση

def bubbleSort(A):
    N = len(A)
    for i in range( N-1 ): # range(0, N–1, 1)
         for j in range( N-1 , i , -1 ): # μέχρι και i–1
             if A[ j ] < A[ j-1 ] :
                  A[ j ] , A[ j-1 ] = A[ j-1 ] , A[ j ]

   return

Βελτιωμένος αλγόριθμος 

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

def bubbleSort(A):
    N = len(A)
    for i in range( N-1 ): # range(0, N–1, 1)
        sorted=True
        for j in range( N-1 , i , -1 ): # μέχρι και i–1
             if A[ j ] < A[ j-1 ] :
                  A[ j ] , A[ j-1 ] = A[ j-1 ] , A[ j ]
                  sorted=False
        if sorted:
            return
    return

Οι 4 εκδοχές της ταξινόμησης ανταλλαγής

Εκδοχή που υπάρχει στο βιβλίο, τοποθετεί αριστερά τους μικρότερους (αύξουσα ταξινόμιση)

Όλες οι εδοχές μετατρέπονται σε φθίνουσες ταξινομίσεις με αντιστροφή της ανισότητας στο IF

def bubleSort1(A):
    N=len(A)
    for i in range(N-1):
        for j in range(N-1,i,-1):
            if A[j]<A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]
        print i+1,'Per:',A #Εμφανίζει τα διαδοχική περάσματα, δεν είναι απαραίτητη
    return

Το ίδιο με το παραπάνω αλλά ξεκινάει το i από 1 και για αυτό σταματάει όταν το j γίνει i-1

def bubleSort2(A):
    N=len(A)
    for i in range(1,N):
        for j in range(N-1,i-1,-1):
            if A[j]<A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]
        print i,'Per:',A #Εμφανίζει τα διαδοχική περάσματα, δεν είναι απαραίτητη
    return

Εκδοχή που τοποθετεί τα μεγαλύτερα δεξιά (αύξουσα ταξινόμιση)

def bubleSort3(A):
    N=len(A)
    for i in range(N-1,0,-1):
        for j in range(0,i):
            if A[j]>A[j+1]:
                A[j],A[j+1] = A[j+1],A[j]
        print N-i,'Per:',A #Εμφανίζει τα διαδοχική περάσματα, δεν είναι απαραίτητη
    return

Το ίδιο με το παραπάνω αλλά ξεκινάει το i από Ν και για αυτό σταματάει όταν το j γίνει i-1

def bubleSort4(A):
    N=len(A)
    for i in range(N,1,-1):
        for j in range(0,i-1):
            if A[j]>A[j+1]:
                A[j],A[j+1] = A[j+1],A[j]
        print N-i+1,'Per:',A #Εμφανίζει τα διαδοχική περάσματα, δεν είναι απαραίτητη
    return