Εισαγωγή στον αλγόριθμο Bubble Sort

Η ταξινόμηση είναι μια από τις πιο βασικές λειτουργίες που μπορείτε να εφαρμόσετε στα δεδομένα. Μπορείτε να ταξινομήσετε στοιχεία σε διαφορετικές γλώσσες προγραμματισμού χρησιμοποιώντας διάφορους αλγόριθμους ταξινόμησης όπως Quick Sort, Bubble Sort, Merge Sort, Insertion Sort κ.λπ. Το Bubble Sort είναι ο πιο απλός αλγόριθμος μεταξύ όλων αυτών.

Σε αυτό το άρθρο, θα μάθετε για τη λειτουργία του αλγορίθμου Bubble Sort, τον ψευδοκώδικα του Bubble Sort αλγόριθμος, την πολυπλοκότητα του χρόνου και του χώρου και την εφαρμογή του σε διάφορες γλώσσες προγραμματισμού όπως C ++, Python, C και JavaScript.

Πώς λειτουργεί ο αλγόριθμος Bubble Sort;

Το Bubble Sort είναι ο απλούστερος αλγόριθμος ταξινόμησης που επαναλαμβάνει επανειλημμένα τη λίστα, συγκρίνει παρακείμενα στοιχεία και τα ανταλλάσσει αν είναι σε λάθος σειρά. Αυτή η ιδέα μπορεί να εξηγηθεί πιο αποτελεσματικά με τη βοήθεια ενός παραδείγματος. Εξετάστε έναν μη ταξινομημένο πίνακα με τα ακόλουθα στοιχεία: {16, 12, 15, 13, 19}.

Παράδειγμα:

Εδώ συγκρίνονται τα παρακείμενα στοιχεία και αν δεν είναι σε αύξουσα σειρά, ανταλλάσσονται.

Ψευδοκώδικας του αλγόριθμου ταξινόμησης φυσαλίδων

Σε ψευδοκώδικα, ο αλγόριθμος Bubble Sort μπορεί να εκφραστεί ως:

bubbleSort (Arr [], μέγεθος)
// loop για πρόσβαση σε κάθε στοιχείο πίνακα
για i = 0 έως size-1 κάνουμε:
// loop για σύγκριση στοιχείων πίνακα
για j = 0 έως μέγεθος-i-1 κάντε:
// συγκρίνετε τα παρακείμενα στοιχεία
εάν Arr [j]> Arr [j + 1] τότε
// ανταλλαγή τους
ανταλλαγή (Arr [j], Arr [j + 1])
τέλος εαν
τέλος για
τέλος για
τέλος

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

Έτσι, ο ψευδοκώδικας του βελτιστοποιημένου αλγορίθμου Bubble Sort μπορεί να εκφραστεί ως:

bubbleSort (Arr [], μέγεθος)
// loop για πρόσβαση σε κάθε στοιχείο πίνακα
για i = 0 έως size-1 κάνουμε:
// ελέγξτε εάν υπάρχει ανταλλαγή
ανταλλαγή = ψευδές
// loop για σύγκριση στοιχείων πίνακα
για j = 0 έως μέγεθος-i-1 κάντε:
// συγκρίνετε τα παρακείμενα στοιχεία
εάν Arr [j]> Arr [j + 1] τότε
// ανταλλαγή τους
ανταλλαγή (Arr [j], Arr [j + 1])
ανταλλαγή = αλήθεια
τέλος εαν
τέλος για
// αν δεν έχουν αλλάξει στοιχεία που σημαίνει ότι ο πίνακας έχει ταξινομηθεί τώρα, τότε σπάστε το βρόχο.
εάν (όχι ανταλλαγή) τότε
Διακοπή
τέλος εαν
τέλος για
τέλος

Χρονική πολυπλοκότητα και βοηθητικός χώρος του αλγόριθμου Bubble Sort

Η χειρότερη περίπτωση πολυπλοκότητας του αλγόριθμου Bubble Sort είναι O (n ^ 2). Εμφανίζεται όταν ο πίνακας είναι σε φθίνουσα σειρά και θέλετε να τον ταξινομήσετε σε αύξουσα σειρά ή αντίστροφα.

Η πολυπλοκότητα του καλύτερου χρόνου του αλγόριθμου Bubble Sort είναι το O (n). Εμφανίζεται όταν ο πίνακας έχει ήδη ταξινομηθεί.

Σχετιζομαι με: Τι είναι η σημείωση Big-O;

Ο μέσος χρόνος περιπλοκότητας του αλγόριθμου Bubble Sort είναι O (n ^ 2). Εμφανίζεται όταν τα στοιχεία του πίνακα είναι σε ανάμικτη σειρά.

Ο βοηθητικός χώρος που απαιτείται για τον αλγόριθμο Bubble Sort είναι O (1).

C ++ Υλοποίηση του αλγορίθμου Bubble Sort

Ακολουθεί η εφαρμογή C ++ του αλγορίθμου Bubble Sort:

// C ++ εφαρμογή του
// βελτιστοποιημένος αλγόριθμος Bubble Sort
#περιλαμβάνω 
χρησιμοποιώντας το namespace std;
// Λειτουργία εκτέλεσης Bubble Sort
void bubbleSort (int arr [], int μέγεθος) {
// Βρόχος για πρόσβαση σε κάθε στοιχείο του πίνακα
για (int i = 0; i // Μεταβλητή για να ελέγξετε εάν υπάρχει ανταλλαγή
ανταλλαγή bool = false;
// loop για σύγκριση δύο παρακείμενων στοιχείων του πίνακα
για (int j = 0; j // Συγκρίνοντας δύο παρακείμενα στοιχεία πίνακα
αν (arr [j]> arr [j + 1]) {
// Ανταλλάξτε και τα δύο στοιχεία εάν είναι
// όχι σε σωστή σειρά
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
ανταλλαγή = true;
}
}
// Αν δεν άλλαξαν στοιχεία, αυτό σημαίνει ότι ο πίνακας έχει ταξινομηθεί τώρα,
// στη συνέχεια σπάστε το βρόχο.
αν (swapped == false) {
Διακοπή;
}
}
}
// Εκτυπώνει τα στοιχεία του πίνακα
void printArray (int arr [], int μέγεθος) {
για (int i = 0; << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Εύρεση του μήκους του πίνακα
int size = sizeof (arr) / sizeof (arr [0]);
// Εκτύπωση του δεδομένου μη ταξινομημένου πίνακα
cout << "Χωρίς ταξινόμηση Array:" << endl;
printArray (arr, μέγεθος);
// Λειτουργία κλήσης bubbleSort ()
bubbleSort (arr, μέγεθος);
// Εκτύπωση του ταξινομημένου πίνακα
cout << "Ταξινομημένη σειρά με αύξουσα σειρά:" << endl;
printArray (arr, μέγεθος);
επιστροφή 0;
}

Παραγωγή:

Μη ταξινομημένη σειρά: 
16 12 15 13 19 
Ταξινομημένη σειρά με αύξουσα σειρά:
12 13 15 16 19

Python Υλοποίηση του αλγόριθμου Bubble Sort

Ακολουθεί η εφαρμογή Python του αλγορίθμου Bubble Sort:

# Εφαρμογή Python του
# βελτιστοποιημένος αλγόριθμος Bubble Sort
# Λειτουργία για εκτέλεση Bubble Sort
def bubbleSort (arr, μέγεθος):
# Βρόχος για πρόσβαση σε κάθε στοιχείο της λίστας
για i στην περιοχή (μέγεθος-1):
# Μεταβλητή για να ελέγξετε εάν υπάρχει ανταλλαγή
Ανταλλαγή = Λάθος
# loop για σύγκριση δύο παρακείμενων στοιχείων της λίστας
για j in range (μέγεθος-i-1):
# Σύγκριση δύο παρακείμενων στοιχείων λίστας
αν arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = θερμοκρασία
ανταλλαγή = Αληθινό
# Αν δεν άλλαξαν στοιχεία, αυτό σημαίνει ότι η λίστα έχει ταξινομηθεί τώρα,
# στη συνέχεια σπάστε το βρόχο.
αν αλλάξει == Λάθος:
Διακοπή
# Εκτυπώνει τα στοιχεία της λίστας
def printArray (arr):
για στοιχείο σε arr:
εκτύπωση (στοιχείο, τέλος = "")
Τυπώνω("")
arr = [16, 12, 15, 13, 19]
# Εύρεση του μήκους της λίστας
μέγεθος = len (arr)
# Εκτύπωση της δεδομένης μη ταξινομημένης λίστας
εκτύπωση ("Λίστα χωρίς ταξινόμηση:")
printArray (arr)
Συνάρτηση # Calling bubbleSort ()
bubbleSort (arr, μέγεθος)
# Εκτύπωση της ταξινομημένης λίστας
εκτύπωση ("Ταξινομημένη λίστα με αύξουσα σειρά:")
printArray (arr)

Παραγωγή:

Μη ταξινομημένη λίστα:
16 12 15 13 19 
Ταξινομημένη λίστα με αύξουσα σειρά:
12 13 15 16 19

Σχετιζομαι με: Πώς να χρησιμοποιήσετε για βρόχους στο Python

Γ Εφαρμογή του αλγόριθμου Bubble Sort

Ακολουθεί η εφαρμογή C του αλγορίθμου Bubble Sort:

// Γ εφαρμογή του
// βελτιστοποιημένος αλγόριθμος Bubble Sort
#περιλαμβάνω 
#περιλαμβάνω 
// Λειτουργία εκτέλεσης Bubble Sort
void bubbleSort (int arr [], int μέγεθος) {
// Βρόχος για πρόσβαση σε κάθε στοιχείο του πίνακα
για (int i = 0; i // Μεταβλητή για να ελέγξετε εάν υπάρχει ανταλλαγή
ανταλλαγή bool = false;
// loop για σύγκριση δύο παρακείμενων στοιχείων του πίνακα
για (int j = 0; j // Συγκρίνοντας δύο παρακείμενα στοιχεία πίνακα
αν (arr [j]> arr [j + 1]) {
// Ανταλλάξτε και τα δύο στοιχεία εάν είναι
// όχι σε σωστή σειρά
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
ανταλλαγή = true;
}
}
// Αν δεν άλλαξαν στοιχεία, αυτό σημαίνει ότι ο πίνακας έχει ταξινομηθεί τώρα,
// στη συνέχεια σπάστε το βρόχο.
αν (swapped == false) {
Διακοπή;
}
}
}
// Εκτυπώνει τα στοιχεία του πίνακα
void printArray (int arr [], int μέγεθος) {
για (int i = 0; printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Εύρεση του μήκους του πίνακα
int size = sizeof (arr) / sizeof (arr [0]);
// Εκτύπωση του δεδομένου μη ταξινομημένου πίνακα
printf ("Μη ταξινομημένη σειρά: \ ⁠n");
printArray (arr, μέγεθος);
// Λειτουργία κλήσης bubbleSort ()
bubbleSort (arr, μέγεθος);
// Εκτύπωση του ταξινομημένου πίνακα
printf ("Ταξινομημένη σειρά με αύξουσα σειρά: \ ⁠n");
printArray (arr, μέγεθος);
επιστροφή 0;
}

Παραγωγή:

Μη ταξινομημένη σειρά: 
16 12 15 13 19 
Ταξινομημένη σειρά με αύξουσα σειρά: 
12 13 15 16 19

Εφαρμογή JavaScript του αλγόριθμου Bubble Sort

Ακολουθεί η εφαρμογή JavaScript του αλγορίθμου Bubble Sort:

// Εφαρμογή JavaScript του
// βελτιστοποιημένος αλγόριθμος Bubble Sort
// Λειτουργία εκτέλεσης Bubble Sort
συνάρτηση bubbleSort (arr, μέγεθος) {
// Βρόχος για πρόσβαση σε κάθε στοιχείο του πίνακα
για (let i = 0; Εγώ// Μεταβλητή για να ελέγξετε εάν υπάρχει ανταλλαγή
var swapped = false;
// loop για σύγκριση δύο παρακείμενων στοιχείων του πίνακα
για (ας j = 0; ι// Συγκρίνοντας δύο παρακείμενα στοιχεία πίνακα
αν (arr [j]> arr [j + 1]) {
// Ανταλλάξτε και τα δύο στοιχεία εάν είναι
// όχι σε σωστή σειρά
ας temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
ανταλλαγή = true;
}
// Αν δεν άλλαξαν στοιχεία, αυτό σημαίνει ότι ο πίνακας έχει ταξινομηθεί τώρα,
// στη συνέχεια σπάστε το βρόχο.
αν (swapped == false) {
Διακοπή;
}
}
}
}
// Εκτυπώνει τα στοιχεία του πίνακα
function printArray (arr, μέγεθος) {
για (let i = 0; Εγώdocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Εύρεση του μήκους του πίνακα
var size = arr.length;
// Εκτύπωση του δεδομένου μη ταξινομημένου πίνακα
document.write ("Μη ταξινομημένη σειρά: 
");
printArray (arr, μέγεθος);
// Λειτουργία κλήσης bubbleSort ()
bubbleSort (arr, μέγεθος);
// Εκτύπωση του ταξινομημένου πίνακα
document.write ("Ταξινομημένη σειρά με αύξουσα σειρά: 
");
printArray (arr, μέγεθος);

Παραγωγή:

Μη ταξινομημένη σειρά:
16 12 15 13 19
Ταξινομημένη σειρά με αύξουσα σειρά:
12 15 13 16 19

Τώρα καταλαβαίνετε τη λειτουργία του αλγόριθμου Bubble Sort

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

Χρησιμοποιώντας το Python, μπορείτε να εφαρμόσετε τον αλγόριθμο Bubble Sort με ευκολία. Εάν δεν είστε εξοικειωμένοι με την Python και θέλετε να ξεκινήσετε το ταξίδι σας, ξεκινώντας με ένα σενάριο "Hello World" είναι μια εξαιρετική επιλογή.

Πώς να ξεκινήσετε με το Python χρησιμοποιώντας ένα σενάριο "Hello World"

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

Διαβάστε Επόμενο

Σχετικά με τον Συγγραφέα