Τ.Ε.Μ. Κεφ5 Δρ4 Βελτιστοποιημένη ταξινόμηση

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

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] χρησιμοποιώντας τη βελτιστοποιημένη ταξινόμηση και πόσα άσκοπα θα γινόταν με τον απλό αλγόριθμο ταξινόμησης;

  • 4 περάσματα με το βελτιστοποιημένο αλγόριθμο ταξινόμησης
  • και Ν-1 = 7 - 1 = 6 συνολικά περάσματα ή 6 - 4 = 2 άσκοπα περάσματα με τον απλό αλγόριθμο
  • 3 περάσματα με το βελτιστοποιημένο αλγόριθμο ταξινόμησης
  • και Ν-1 = 7 - 1 = 6 συνολικά περάσματα ή 6 - 3 = 3 άσκοπα περάσματα με τον απλό αλγόριθμο
  • 2 περάσματα με το βελτιστοποιημένο αλγόριθμο ταξινόμησης
  • και Ν-1 = 7 - 1 = 6 συνολικά περάσματα ή 6 - 2 = 4 άσκοπα περάσματα με τον απλό αλγόριθμο