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

Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί η ταξινόμηση φυσαλίδων. Επίσης, θα βρείτε λειτουργικά παραδείγματα ταξινόμησης φυσαλίδων σε C, C ++, Java και Python.

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

Πώς λειτουργεί το Bubble Sort;

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

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

 bubbleSort (πίνακας) για i rightElement ανταλλαγή αριστερούElement και rightElement end bubbleSort

Παραδείγματα Python, Java και C / C ++

Python Java C C ++

 # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)

 // Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j  to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )

 // Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Βελτιστοποιημένη ταξινόμηση φυσαλίδων

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

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

Σε μια τέτοια περίπτωση, η μεταβλητή έχει αλλάξει. Έτσι, μπορούμε να αποτρέψουμε περαιτέρω επαναλήψεις.

Ο αλγόριθμος για βελτιστοποιημένη ταξινόμηση φυσαλίδων είναι

 bubbleSort (array) ανταλλάχθηκε <- false για i rightElement swap αριστεράElement και rightElement swapped <- true end bubbleSort

Παραδείγματα βελτιστοποιημένης ταξινόμησης φυσαλίδων

Python Java C C +

 # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

 // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j  to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )

 // Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (

  // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Περίπλοκο

Το Bubble Sort είναι ένας από τους απλούστερους αλγόριθμους ταξινόμησης. Δύο βρόχοι εφαρμόζονται στον αλγόριθμο.

Κύκλος	Αριθμός συγκρίσεων
1ος	(ν-1)
2ος	(ν-2)
3ος	(ν-3)
….	…
τελευταίος	1

Αριθμός συγκρίσεων: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 σχεδόν ισούται με n ²

Πολυπλοκότητα: O (n ² )

Επίσης, μπορούμε να αναλύσουμε την πολυπλοκότητα παρατηρώντας απλώς τον αριθμό των βρόχων. Υπάρχουν 2 βρόχοι, έτσι η πολυπλοκότητα είναιn*n = n²

Χρόνος πολυπλοκότητας:

Χειρότερη περίπλοκη περίπτωση : Εάν θέλουμε να ταξινομήσουμε με αύξουσα σειρά και ο πίνακας είναι σε φθίνουσα σειρά τότε, εμφανίζεται η χειρότερη περίπτωση.O(n²)
Βέλτιστη πολυπλοκότητα περιπτώσεων:O(n)
Εάν ο πίνακας έχει ήδη ταξινομηθεί, τότε δεν υπάρχει ανάγκη ταξινόμησης.
Μέση πολυπλοκότητα περίπτωσης: Εμφανίζεται όταν τα στοιχεία του πίνακα είναι σε ανάμικτη σειρά (ούτε αύξουσα ούτε φθίνουσα).O(n²)

Διαστημική πολυπλοκότητα:
Η πολυπλοκότητα του χώρου οφείλεται στο O(1)γεγονός ότι χρησιμοποιείται μια επιπλέον μεταβλητή θερμοκρασία για ανταλλαγή.

Στον βελτιστοποιημένο αλγόριθμο, η μεταβαλλόμενη μεταβλητή προσθέτει έτσι την πολυπλοκότητα του χώρου, καθιστώντας την O(2).