ΘΕΜΑ: Bubble Sort Κώδικας

Την καλησπέρα μου στο forum. Νέος στην python και προσπαθώ μέσω ενός online μαθήματος να μάθω τα βασικά. Αυτή τη στιγμή βρίσκομαι στην ενότητα των λιστών. Δεν θα πω ψέματα νιώθω πως έκαψα τον εγκέφαλο μου αλλά τελικά κάτι κατάφερα. Στο θέμα. Έχω 2 ασκήσεις να παραδώσω και λόγω διάφορων αναποδιών έχασα μέρες και έχω διορία μέχρι αύριο το βράδυ, οπότε κάθε βοήθεια δεκτή.

Η μια εργασία στην οποία έχω κάνει πρόοδο είναι η ακόλουθη.

Γράψτε πρόγραμμα το οποίο να:

Δίνει ακέραιο N από πληκτρολόγιο
Δημιουργεί λίστα L, N θέσεων με ψευδοτυχαίους στο διάστημα [1, 100]
Εφαρμόζει τον αλγόριθμο ταξινόμησης φυσαλίδας για να ταξινομήσει τη λίστα κατ’ αύξουσα σειρά
Εμφανίζει την ταξινομημένη λίστα στην οθόνη
Υπόδειξη:

Χρησιμοποιήστε τη μέθοδο περιγραφής λίστας (list comprehension)

Για λίστα L με Ν θέσεις (zero-indexed άρα ο δείκτης του τελευταίου στοιχείου είναι Ν-1) υλοποιήστε τον αλγόριθμο φυσαλίδας με βάση τον ψευδοκώδικα που δίνεται παρακάτω:

Για i από 0 μέχρι και Ν-2
Για j από 0 μέχρι και Ν-2-i
αν L[j+1] < L[j] :
αντιμετάθεσε L[j] με L[j+1]

και η λύση αυτής είναι η παρακάτω ή τέλος πάντων αυτή που πιστεύω πως είναι η λύση μέχρι ενός σημείου.

import random as rn
N = int(input('Δώσε έναν ακέραιο : '))
L = [rn.randint(1,100) for k in range(N)]
for i in range(0,N-2):
for j in range(0,N-2-i):
if L[j+1] < L[j]:
L[j+1],L[j] = L[j],L[j+1]
print(L)

Τι δεν έχω κάνει σωστά και δεν λαμβάνω sorted τις λίστες μου? Ευχαριστώ πολύ για τον χρόνο σας

Αντί Ν-2 Ν-1

Αν δεις είναι σαν σταθερά το Ν-2 στην άσκηση οπότε πρέπει σε άλλη σειρά να προσθέσω κάτι για να βγει τελικά το αποτέλεσμα

Ο Theo σου έδωσε τη λύση. Το Ν-2 στον κώδικα που παραθέτεις έχει σαν αποτέλεσμα την παράληψη του τελευταίου στοιχείου της λίστας.

Σκέψου τη λίστα στο οριζόντιο επίπεδο.

Για κάθε μία από τις τιμές του j, θα πραγματοποιείται η σύγκριση του j-οστού με το j+1-οστό στοιχείο της λίστας και όταν το πιο "δεξιά" στοιχείο (L[j+1]) είναι μικρότερο από το πιο "αριστερά" (L[j]) τότε μεταθέτεις τις τιμές τους. Με αυτό τον τρόπο, οι μεγαλύτερες τιμές μετατοπίζονται προς τα δεξιά.

Για να καταλάβεις τι εννοώ, ας "τρέξουμε" το πρόγραμμα με το χέρι:

Παράδειγμα:

Έστω λοιπόν ότι Ν = 5 και L = [45, 10, 25, 14, 88]

Όταν το i=0, το j θα πάρει τιμές


Μην ξεχνάς ότι στο range το πάνω όριο είναι ανοιχτό!

Οι συγκρίσεις θα είναι για τα στοιχεία (με κόκκινο φόντο τα στοιχεία που αλλάζουν θέση σε κάθε επανάληψη):

(j=0) L[1] < L[0] --> 10 < 45 (ισχύει η συνθήκη, οπότε μεταθέτουμε τις τιμές)

Νέα μορφή της λίστας: L = [10, 45, 25, 14, 88]

(j=1) L[2] < L[1] --> 25 < 45 (ισχύει η συνθήκη, οπότε μεταθέτουμε τις τιμές)

Νέα μορφή της λίστας: L = [10, 25, 45, 14, 88]

(j=2) L[3] < L[2] --> 14 < 45 (ισχύει η συνθήκη, οπότε μεταθέτουμε τις τιμές)

Νέα μορφή της λίστας: L = [10, 25, 14, 45, 88]

Μπορείς να συνεχίσεις στον ίδιο στυλ, για τις υπόλοιπες τιμές του i και το αποτέλεσμα θα είναι το αναμενόμενο.

Είναι όμως ο αλγόριθμος σωστός;

Αν πρόσεξες, στο παράδειγμα τελείωσε η πρώτη επανάληψη για το j (όσο το i=0) και δεν έγινε η σύγκριση για το τελευταίο στοιχείο της λίστας! Αυτό δεν θα συνέβαινε αν είχες δώσει N-1. Στην συγκεκριμένη βέβαια περίπτωση ήμασταν τυχεροί γιατί το μεγαλύτερο στοιχείο της λίστας ήταν ήδη στη σωστή θέση (κατά τύχη).

Αν θέλεις να επαναλάβεις την παραπάνω άσκηση για τον πίνακα L = [88, 10, 25, 14, 45], όπου το μεγαλύτερο στοιχείο δεν βρίσκεται στην τελική του θέση, τότε θα δεις ότι το αποτέλεσμα του αλγορίθμου θα είναι λάθος (L = [10, 14, 25, 88, 45]) γιατί το 45 δεν ελέγχεται ποτέ.

Οπότε, η εσωτερική επανάληψη πρέπει να είναι


Η εξωτερική επανάληψη όμως μπορεί να παραμείνει ως έχει (σου το αφήνω να το σκεφτείς αυτό).

Θα σου πρότεινα να εισάγεις κάποια print μέσα στον κώδικά σου για να βλέπεις τι ακριβώς συμβαίνει σε κάθε βήμα

Επίσης, ακόμα πιο χρήσιμο είναι να κάνεις αποσφαλμάτωση είτε χρησιμοποιώντας απευθείας τον debugger της Python pdb, ή να το κάνεις μέσω κάποιου IDE (όπως PyCharm).