Η ταξινόμηση είναι ένα από τα πιο χρησιμοποιούμενα χαρακτηριστικά στον προγραμματισμό. Και θα χρειαστεί χρόνος για να ολοκληρωθεί η ταξινόμηση εάν δεν χρησιμοποιούσαμε τον σωστό αλγόριθμο.
Σε αυτό το άρθρο, θα συζητήσουμε διαφορετικούς αλγόριθμους ταξινόμησης.
Θα σας καθοδηγήσουμε στους διαφορετικούς αλγόριθμους ταξινόμησης με κάθε βήμα που έρχεται στην εφαρμογή. Το μέρος υλοποίησης θα είναι σε Python. Μπορείτε εύκολα να το μετατρέψετε σε οποιαδήποτε γλώσσα μόλις λάβετε τον αλγόριθμο. Αυτό είναι το θέμα της σύνταξης της γλώσσας.
Θα δούμε διαφορετικούς αλγόριθμους από τον χειρότερο στον καλύτερο σε αυτό το σεμινάριο. Οπότε, μην ανησυχείς. Ακολουθήστε το άρθρο και εφαρμόστε τα.
Ας βουτήξουμε στους αλγόριθμους ταξινόμησης.
Πίνακας περιεχομένων
Ταξινόμηση εισαγωγής
Η ταξινόμηση εισαγωγής είναι ένας από τους απλούς αλγόριθμους ταξινόμησης. Είναι εύκολο να εφαρμοστεί. Και θα σας κοστίσει περισσότερο χρόνο για να ταξινομήσετε έναν πίνακα. Δεν θα χρησιμοποιηθεί στις περισσότερες περιπτώσεις για ταξινόμηση για μεγαλύτερους πίνακες.
Ο αλγόριθμος ταξινόμησης εισαγωγής διατηρεί ταξινομημένα και μη ταξινομημένα υποτμήματα στον δεδομένο πίνακα.
Το ταξινομημένο υποτμήμα περιέχει μόνο το πρώτο στοιχείο στην αρχή της διαδικασίας ταξινόμησης. Θα πάρουμε ένα στοιχείο από τον μη ταξινομημένο πίνακα και θα το τοποθετήσουμε στη σωστή θέση στον ταξινομημένο υποπίνακα.
Ας δούμε τις οπτικές απεικονίσεις της εισαγωγής ταξινόμησης βήμα προς βήμα με ένα παράδειγμα.
Ας δούμε τα βήματα για την εφαρμογή της ταξινόμησης εισαγωγής.
- Αρχικοποιήστε τον πίνακα με εικονικά δεδομένα (ακέραιοι).
- Επανάληψη πάνω από τον δεδομένο πίνακα από το δεύτερο στοιχείο.
- Πάρτε την τρέχουσα θέση και το στοιχείο σε δύο μεταβλητές.
- Γράψτε έναν βρόχο που επαναλαμβάνεται μέχρι να εμφανιστεί το πρώτο στοιχείο του πίνακα ή το στοιχείο που είναι μικρότερο από το τρέχον στοιχείο.
- Ενημερώστε το τρέχον στοιχείο με το προηγούμενο στοιχείο.
- Μείωση της τρέχουσας θέσης.
- Εδώ, ο βρόχος πρέπει να φτάσει είτε στην αρχή του πίνακα είτε να βρει ένα μικρότερο στοιχείο από το τρέχον στοιχείο. Αντικαταστήστε το στοιχείο τρέχουσας θέσης με το τρέχον στοιχείο.
Η χρονική πολυπλοκότητα της ταξινόμησης εισαγωγής είναι O(n^2), και η πολυπλοκότητα χώρου αν O(1).
Αυτό είναι; ταξινομήσαμε τον δεδομένο πίνακα. Ας τρέξουμε τον παρακάτω κώδικα. Ελπίζω να έχετε εγκαταστήσει την Python, αν όχι, ρίξτε μια ματιά στον οδηγό εγκατάστασης. Εναλλακτικά, μπορείτε να χρησιμοποιήσετε έναν διαδικτυακό μεταγλωττιστή Python.
def insertion_sort(arr, n): for i in range(1, n): ## current position and element current_position = i current_element = arr[i] ## iteratin until ### it reaches the first element or ### the current element is smaller than the previous element while current_position > 0 and current_element < arr[current_position - 1]: ## updating the current element with previous element arr[current_position] = arr[current_position - 1] ## moving to the previous position current_position -= 1 ## updating the current position element arr[current_position] = current_element if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] insertion_sort(arr, 9) ## printing the array print(str(arr))
Επιλογή Ταξινόμηση
Η ταξινόμηση επιλογής είναι παρόμοια με την ταξινόμηση εισαγωγής με μια μικρή διαφορά. Αυτός ο αλγόριθμος διαιρεί επίσης τον πίνακα σε ταξινομημένα και μη ταξινομημένα υποτμήματα. Και στη συνέχεια, σε κάθε επανάληψη, θα πάρουμε το ελάχιστο στοιχείο από το μη ταξινομημένο υποτμήμα και θα το τοποθετήσουμε στην τελευταία θέση του ταξινομημένου υποτμήματος.
Ας παραθέσουμε εικόνες επιλογής για καλύτερη κατανόηση.
Ας δούμε τα βήματα για την εφαρμογή της ταξινόμησης επιλογής.
- Αρχικοποιήστε τον πίνακα με εικονικά δεδομένα (ακέραιοι).
- Επανάληψη πάνω από τον δεδομένο πίνακα.
- Διατηρήστε τον δείκτη του ελάχιστου στοιχείου.
- Γράψτε έναν βρόχο που να επαναλαμβάνεται από το τρέχον στοιχείο στο τελευταίο στοιχείο.
- Ελέγξτε εάν το τρέχον στοιχείο είναι μικρότερο από το ελάχιστο στοιχείο ή όχι.
- Εάν το τρέχον στοιχείο είναι μικρότερο από το ελάχιστο στοιχείο, αντικαταστήστε το ευρετήριο.
- Έχουμε μαζί μας τον ελάχιστο δείκτη στοιχείων. Αλλάξτε το τρέχον στοιχείο με το ελάχιστο στοιχείο χρησιμοποιώντας τα ευρετήρια.
Η χρονική πολυπλοκότητα της ταξινόμησης επιλογής είναι O(n^2) και η πολυπλοκότητα χώρου εάν O(1).
Προσπαθήστε να εφαρμόσετε τον αλγόριθμο καθώς είναι παρόμοιος με την ταξινόμηση εισαγωγής. Μπορείτε να δείτε τον κωδικό παρακάτω.
def selection_sort(arr, n): for i in range(n): ## to store the index of the minimum element min_element_index = i for j in range(i + 1, n): ## checking and replacing the minimum element index if arr[j] < arr[min_element_index]: min_element_index = j ## swaping the current element with minimum element arr[i], arr[min_element_index] = arr[min_element_index], arr[i] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] selection_sort(arr, 9) ## printing the array print(str(arr))
Ταξινόμηση με φυσαλίδες
Η ταξινόμηση με φυσαλίδες είναι ένας απλός αλγόριθμος. Εναλλάσσει τα γειτονικά στοιχεία σε κάθε επανάληψη επανειλημμένα μέχρι να ταξινομηθεί ο δεδομένος πίνακας.
Επαναλαμβάνεται πάνω από τον πίνακα και μετακινεί το τρέχον στοιχείο στην επόμενη θέση μέχρι να είναι μικρότερο από το επόμενο στοιχείο.
Οι εικονογραφήσεις μας βοηθούν να κατανοήσουμε οπτικά την ταξινόμηση με φυσαλίδες. Ας τους δούμε.
Ας δούμε τα βήματα για την εφαρμογή της ταξινόμησης με φυσαλίδες.
Η χρονική πολυπλοκότητα της ταξινόμησης με φυσαλίδες είναι O(n^2) και η πολυπλοκότητα χώρου αν O(1).
Μπορείτε να εφαρμόσετε εύκολα την ταξινόμηση με φυσαλίδες μέχρι τώρα. Ας δούμε τον κωδικό.
def bubble_sort(arr, n): for i in range(n): ## iterating from 0 to n-i-1 as last i elements are already sorted for j in range(n - i - 1): ## checking the next element if arr[j] > arr[j + 1]: ## swapping the adjucent elements arr[j], arr[j + 1] = arr[j + 1], arr[j] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] bubble_sort(arr, 9) ## printing the array print(str(arr))
Ταξινόμηση συγχώνευσης
Η ταξινόμηση συγχώνευσης είναι ένας αναδρομικός αλγόριθμος για την ταξινόμηση του δεδομένου πίνακα. Είναι πιο αποτελεσματικός από τους αλγόριθμους που συζητήθηκαν προηγουμένως όσον αφορά την πολυπλοκότητα του χρόνου. Ακολουθεί την προσέγγιση διαίρει και βασίλευε.
Ο αλγόριθμος ταξινόμησης συγχώνευσης χωρίζει τον πίνακα σε δύο μισά και τα ταξινομεί χωριστά. Αφού ταξινομήσει τα δύο μισά του πίνακα, τα συγχωνεύει σε έναν ενιαίο ταξινομημένο πίνακα.
Καθώς είναι ένας αναδρομικός αλγόριθμος, διαιρεί τον πίνακα έως ότου ο πίνακας γίνει ο απλούστερος (πίνακας με ένα στοιχείο) προς ταξινόμηση.
Ήρθε η ώρα για εικονογράφηση. Ας το δούμε.
Ας δούμε τα βήματα για την εφαρμογή της ταξινόμησης συγχώνευσης.
- Αρχικοποιήστε τον πίνακα με εικονικά δεδομένα (ακέραιοι).
- Γράψτε μια συνάρτηση που ονομάζεται συγχώνευση για τη συγχώνευση υπο-πίνακες σε έναν μόνο ταξινομημένο πίνακα. Αποδέχεται τον πίνακα ορισμάτων, τα αριστερά, τα μέσα και τα δεξιά ευρετήρια.
- Λάβετε τα μήκη των μηκών του αριστερού και του δεξιού υποπίνακα χρησιμοποιώντας τα δεδομένα ευρετήρια.
- Αντιγράψτε τα στοιχεία από τον πίνακα στον αντίστοιχο αριστερό και δεξιό πίνακα.
- Επαναλάβετε τους δύο υπο-πίνακες.
- Συγκρίνετε τα δύο στοιχεία του υποπίνακα.
- Αντικαταστήστε το στοιχείο πίνακα με το μικρότερο στοιχείο από τους δύο υποπίνακες για ταξινόμηση.
- Ελέγξτε αν υπάρχουν στοιχεία και στους δύο υποπίνακες.
- Προσθέστε τα στον πίνακα.
- Γράψτε μια συνάρτηση που ονομάζεται merge_sort με πίνακα παραμέτρων, αριστερά και δεξιά ευρετήρια.
- Εάν ο αριστερός δείκτης είναι μεγαλύτερος ή ίσος με τον δεξιό δείκτη, τότε επιστρέψτε.
- Βρείτε το μεσαίο σημείο του πίνακα για να χωρίσετε τον πίνακα σε δύο μισά.
- Αναδρομικά καλέστε το merge_sort χρησιμοποιώντας τα αριστερά, δεξιά και μεσαία ευρετήρια.
- Μετά τις αναδρομικές κλήσεις, συγχωνεύστε τον πίνακα με τη συνάρτηση συγχώνευσης.
Η χρονική πολυπλοκότητα της ταξινόμησης συγχώνευσης είναι O(nlogn) και η πολυπλοκότητα χώρου εάν O(1).
Αυτό είναι όλο για την υλοποίηση του αλγόριθμου ταξινόμησης συγχώνευσης. Ελέγξτε τον παρακάτω κωδικό.
def merge(arr, left_index, mid_index, right_index): ## left and right arrays left_array = arr[left_index:mid_index+1] right_array = arr[mid_index+1:right_index+1] ## getting the left and right array lengths left_array_length = mid_index - left_index + 1 right_array_length = right_index - mid_index ## indexes for merging two arrays i = j = 0 ## index for array elements replacement k = left_index ## iterating over the two sub-arrays while i < left_array_length and j < right_array_length: ## comapring the elements from left and right arrays if left_array[i] < right_array[j]: arr[k] = left_array[i] i += 1 else: arr[k] = right_array[j] j += 1 k += 1 ## adding remaining elements from the left and right arrays while i < left_array_length: arr[k] = left_array[i] i += 1 k += 1 while j < right_array_length: j += 1 k += 1 def merge_sort(arr, left_index, right_index): ## base case for recursive function if left_index >= right_index: return ## finding the middle index mid_index = (left_index + right_index) // 2 ## recursive calls merge_sort(arr, left_index, mid_index) merge_sort(arr, mid_index + 1, right_index) ## merging the two sub-arrays merge(arr, left_index, mid_index, right_index) if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] merge_sort(arr, 0, 8) ## printing the array print(str(arr))
συμπέρασμα
Υπάρχουν πολλοί άλλοι αλγόριθμοι ταξινόμησης, αλλά παραπάνω είναι μερικοί από τους συχνά χρησιμοποιούμενους. Ελπίζω να σας άρεσε να μαθαίνετε την ταξινόμηση.
Στη συνέχεια, μάθετε για τους αλγόριθμους αναζήτησης.
Καλή κωδικοποίηση 🙂 👨💻