Εφαρμογές αλγορίθμων ταξινόμησης σε Python

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

Σε αυτό το άρθρο, θα συζητήσουμε διαφορετικούς αλγόριθμους ταξινόμησης.

Θα σας καθοδηγήσουμε στους διαφορετικούς αλγόριθμους ταξινόμησης με κάθε βήμα που έρχεται στην εφαρμογή. Το μέρος υλοποίησης θα είναι σε 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))

Επιλογή Ταξινόμηση

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

  Πλήρης οδηγός για τη φιλοξενία του WordPress στο SiteGround

Ας παραθέσουμε εικόνες επιλογής για καλύτερη κατανόηση.

Ας δούμε τα βήματα για την εφαρμογή της ταξινόμησης επιλογής.

  • Αρχικοποιήστε τον πίνακα με εικονικά δεδομένα (ακέραιοι).
  • Επανάληψη πάνω από τον δεδομένο πίνακα.
    • Διατηρήστε τον δείκτη του ελάχιστου στοιχείου.
    • Γράψτε έναν βρόχο που να επαναλαμβάνεται από το τρέχον στοιχείο στο τελευταίο στοιχείο.
      • Ελέγξτε εάν το τρέχον στοιχείο είναι μικρότερο από το ελάχιστο στοιχείο ή όχι.
      • Εάν το τρέχον στοιχείο είναι μικρότερο από το ελάχιστο στοιχείο, αντικαταστήστε το ευρετήριο.
    • Έχουμε μαζί μας τον ελάχιστο δείκτη στοιχείων. Αλλάξτε το τρέχον στοιχείο με το ελάχιστο στοιχείο χρησιμοποιώντας τα ευρετήρια.

Η χρονική πολυπλοκότητα της ταξινόμησης επιλογής είναι 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))

Ταξινόμηση με φυσαλίδες

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

  Πώς να συγχωνεύσετε αρχεία PDF σε Mac

Επαναλαμβάνεται πάνω από τον πίνακα και μετακινεί το τρέχον στοιχείο στην επόμενη θέση μέχρι να είναι μικρότερο από το επόμενο στοιχείο.

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

Ας δούμε τα βήματα για την εφαρμογή της ταξινόμησης με φυσαλίδες.

  • Αρχικοποιήστε τον πίνακα με εικονικά δεδομένα (ακέραιοι).
  • Επανάληψη πάνω από τον δεδομένο πίνακα.
  • Επανάληψη από 0 έως ni-1. Τα τελευταία στοιχεία i έχουν ήδη ταξινομηθεί.
  • Ελέγξτε εάν το τρέχον στοιχείο είναι μεγαλύτερο από το επόμενο στοιχείο ή όχι.
  • Εάν το τρέχον στοιχείο είναι μεγαλύτερο από το επόμενο στοιχείο, τότε αλλάξτε τα δύο στοιχεία.
  • Η χρονική πολυπλοκότητα της ταξινόμησης με φυσαλίδες είναι 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 χρησιμοποιώντας τα αριστερά, δεξιά και μεσαία ευρετήρια.
      • Μετά τις αναδρομικές κλήσεις, συγχωνεύστε τον πίνακα με τη συνάρτηση συγχώνευσης.
      Πώς να αποκτήσετε νεότερο λογισμικό στο Debian Stable

    Η χρονική πολυπλοκότητα της ταξινόμησης συγχώνευσης είναι 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))

    συμπέρασμα

    Υπάρχουν πολλοί άλλοι αλγόριθμοι ταξινόμησης, αλλά παραπάνω είναι μερικοί από τους συχνά χρησιμοποιούμενους. Ελπίζω να σας άρεσε να μαθαίνετε την ταξινόμηση.

    Στη συνέχεια, μάθετε για τους αλγόριθμους αναζήτησης.

    Καλή κωδικοποίηση 🙂 👨‍💻