Άσκηση 5 – Βελτιωμένη φυσαλίδα – Αλγόριθμος ταξινόμησης ευθείας ανταλλαγής

Εκφώνηση

Να αναπτύξετε συνάρτηση η οποία βελτιώνει τον αλγόριθμο ταξινόμησης ευθείας ανταλλαγής έτσι ώστε να αποφεύγονται οι περιττές συγκρίσεις. Μόλις διαπιστωθεί ότι η λίστα ταξινομήθηκε ο αλγόριθμος τερματίζεται.

Λύση

#Συνάρτηση bubble2 - Βελτιωμένος αλγόριθμος ταξινόμησης ευθείας ανταλλαγής
def bubble2(L):
   N = len(L)
   found = False
   i = 0
   s = 0
   print ' Ξεκινάει η ταξινόμηση για τη λίστα:',L
   while i<N-1 and found == False:
      s = s + 1
      found = True
      j = N-1
      while j > i:
           if L[j] < L[j-1]:
                L[j],L[j-1] = L[j-1],L[j]
                found = False
           j = j - 1
      i = i + 1
      print 'H λίστα μετά από τη',s,'σάρωση είναι:',L
    print 'Η λίστα ταξινομήθηκε μετά από:',s,'σαρώσεις'
    print L