Επεξήγηση ταξινόμησης φυσαλίδων

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

Με τη χειρότερη περίπτωση πολυπλοκότητας του O (n ^ 2), η ταξινόμηση φυσαλίδων είναι πολύ αργή σε σύγκριση με άλλους αλγορίθμους ταξινόμησης όπως η γρήγορη ταξινόμηση. Το αρνητικό είναι ότι είναι ένας από τους ευκολότερους αλγόριθμους ταξινόμησης για να κατανοήσετε και να κωδικοποιήσετε από την αρχή.

Παράδειγμα:

let arr = [4, 2, 6, 3, 9]; let sorted = false while(!sorted) { sorted = true for(var i = 0; i < arr.length; i++) { if(arr[i] < arr[i - 1]) { let temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; sorted = false; } } }

Πρώτα περάστε από τη λίστα:

  • Ξεκινώντας με [4, 2, 6, 3, 9], ο αλγόριθμος συγκρίνει τα δύο πρώτα στοιχεία του πίνακα, 4 και 2. Τα ανταλλάσσει επειδή 2 <4:[2, 4, 6, 3, 9]
  • Συγκρίνει τις επόμενες δύο τιμές, 4 και 6. Όπως 4 <6, αυτές είναι ήδη σε σειρά και ο αλγόριθμος κινείται: [2, 4, 6, 3, 9]
  • Οι επόμενες δύο τιμές ανταλλάσσονται επίσης επειδή 3 <6: [2, 4, 3, 6, 9]
  • Οι δύο τελευταίες τιμές, 6 και 9, είναι ήδη σε σειρά, οπότε ο αλγόριθμος δεν τις ανταλλάσσει.

Δεύτερη διέλευση από τη λίστα:

  • 2 <4, οπότε δεν χρειάζεται να ανταλλάξετε θέσεις: [2, 4, 3, 6, 9]
  • Ο αλγόριθμος ανταλλάσσει τις επόμενες δύο τιμές επειδή 3 <4: [2, 3, 4, 6, 9]
  • Χωρίς ανταλλαγή ως 4 <6: [2, 3, 4, 6, 9]
  • Και πάλι, 6 <9, οπότε δεν υπάρχει ανταλλαγή: [2, 3, 4, 6, 9]

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

Τρίτη διέλευση από τη λίστα:

  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]

Η σαφής ταξινόμηση φυσαλίδων απέχει πολύ από τον πιο αποτελεσματικό αλγόριθμο ταξινόμησης. Ωστόσο, είναι απλό να τυλίξετε το κεφάλι σας και να εφαρμόσετε τον εαυτό σας.

Τώρα πηγαίνετε να ρίξετε στον εαυτό σας ένα κρύο, αφρώδες ποτό - το αξίζετε.