introduction sorting techniques c
Λίστα των διαφόρων τεχνικών ταξινόμησης στο C ++.
Η ταξινόμηση είναι μια τεχνική που εφαρμόζεται για την τακτοποίηση των δεδομένων με συγκεκριμένη σειρά. Απαιτείται ταξινόμηση για να διασφαλιστεί ότι τα δεδομένα που χρησιμοποιούμε είναι σε συγκεκριμένη σειρά, ώστε να μπορούμε εύκολα να ανακτήσουμε τις απαιτούμενες πληροφορίες από το σωρό των δεδομένων.
Εάν τα δεδομένα είναι απρόσεκτα και χωρίς ταξινόμηση, όταν θέλουμε μια συγκεκριμένη πληροφορία, τότε θα πρέπει να τα αναζητούμε ένα προς ένα κάθε φορά για να ανακτήσουμε τα δεδομένα.
=> Διαβάστε το The Easy C ++ Training Series.
Συνεπώς, είναι πάντοτε σκόπιμο να διατηρούμε τα δεδομένα μας τακτοποιημένα με συγκεκριμένη σειρά, έτσι ώστε η ανάκτηση πληροφοριών, καθώς και άλλες λειτουργίες που εκτελούνται στα δεδομένα, να μπορούν να γίνονται εύκολα και αποτελεσματικά.
Αποθηκεύουμε δεδομένα με τη μορφή αρχείων. Κάθε εγγραφή αποτελείται από ένα ή περισσότερα πεδία. Όταν κάθε εγγραφή έχει μια μοναδική τιμή ενός συγκεκριμένου πεδίου, το ονομάζουμε βασικό πεδίο. Για παράδειγμα, σε ένα μάθημα, το Roll No μπορεί να είναι ένα μοναδικό ή βασικό πεδίο.
Οι πάροχοι cloud-computing προσφέρουν τις υπηρεσίες τους ως
Μπορούμε να ταξινομήσουμε τα δεδομένα σε ένα συγκεκριμένο πεδίο κλειδιού και μετά να τακτοποιήσουμε με αύξουσα / αυξανόμενη σειρά ή με φθίνουσα / φθίνουσα σειρά.
Ομοίως, σε ένα λεξικό τηλεφώνου, κάθε εγγραφή αποτελείται από το όνομα ενός ατόμου, τη διεύθυνση και τον αριθμό τηλεφώνου. Σε αυτό, ο αριθμός τηλεφώνου είναι ένα μοναδικό ή βασικό πεδίο. Μπορούμε να ταξινομήσουμε τα δεδομένα του λεξικού σε αυτό το τηλεφωνικό πεδίο. Εναλλακτικά, μπορούμε επίσης να ταξινομήσουμε δεδομένα είτε αριθμητικά είτε αλφαριθμητικά.
Όταν μπορούμε να προσαρμόσουμε τα δεδομένα που θα ταξινομηθούν στην ίδια τη βασική μνήμη χωρίς να χρειαστεί άλλη βοηθητική μνήμη, τότε τα ονομάζουμε ως Εσωτερική ταξινόμηση .
Από την άλλη πλευρά, όταν χρειαζόμαστε βοηθητική μνήμη για την αποθήκευση ενδιάμεσων δεδομένων κατά τη διαλογή, τότε ονομάζουμε την τεχνική ως Εξωτερική ταξινόμηση .
Σε αυτό το σεμινάριο, θα μάθουμε λεπτομερώς τις διάφορες τεχνικές ταξινόμησης στο C ++.
Τι θα μάθετε:
Τεχνικές ταξινόμησης σε C ++
Το C ++ υποστηρίζει διάφορες τεχνικές ταξινόμησης όπως αναφέρονται παρακάτω.
Ταξινόμηση φυσαλίδων
Το είδος Bubble είναι η απλούστερη τεχνική στην οποία συγκρίνουμε κάθε στοιχείο με το παρακείμενο στοιχείο και ανταλλάσσουμε τα στοιχεία εάν δεν είναι σωστά. Με αυτόν τον τρόπο στο τέλος κάθε επανάληψης (ονομάζεται πέρασμα), το βαρύτερο στοιχείο αναβλύζει στο τέλος της λίστας.
Δίνεται παρακάτω ένα παράδειγμα Bubble Sort.
Σειρά προς ταξινόμηση:
Όπως φαίνεται παραπάνω, δεδομένου ότι είναι ένας μικρός πίνακας και ήταν σχεδόν ταξινομημένος, καταφέραμε να πάρουμε έναν πλήρως ταξινομημένο πίνακα σε λίγα περάσματα.
Ας εφαρμόσουμε την τεχνική Bubble Sort στο C ++.
#include using namespace std; int main () { int i, j,temp; int a(5) = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < Παραγωγή:
Λίστα εισαγωγής…
10 2 0 43 12
Ταξινομημένη λίστα στοιχείων…
0 2 10 12 43
Όπως φαίνεται από την έξοδο, σε τεχνική ταξινόμησης φυσαλίδων, με κάθε πέρασμα το βαρύτερο στοιχείο διοχετεύεται μέχρι το τέλος της συστοιχίας ταξινομώντας έτσι τη διάταξη εντελώς.
Ταξινόμηση επιλογής
Είναι απλή αλλά εύκολη στην εφαρμογή τεχνική στην οποία βρίσκουμε το μικρότερο στοιχείο στη λίστα και το βάζουμε στη σωστή του θέση. Σε κάθε πάσο, το επόμενο μικρότερο στοιχείο επιλέγεται και τοποθετείται στη σωστή του θέση.
Ας πάρουμε τον ίδιο πίνακα όπως στο προηγούμενο παράδειγμα και να εκτελέσουμε την επιλογή Ταξινόμηση για να ταξινομήσουμε αυτόν τον πίνακα.
Όπως φαίνεται στην παραπάνω εικόνα, για τον αριθμό των στοιχείων N παίρνουμε περάσματα N-1 για να ταξινομήσουμε πλήρως τον πίνακα. Στο τέλος κάθε περάσματος, το μικρότερο στοιχείο στον πίνακα τοποθετείται στη σωστή του θέση στον ταξινομημένο πίνακα.
Στη συνέχεια, ας εφαρμόσουμε το Ταξινόμηση επιλογής χρησιμοποιώντας το C ++.
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(5) = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< Παραγωγή:
Λίστα εισαγωγής στοιχείων προς ταξινόμηση
12 45 8 15 33
Η ταξινομημένη λίστα στοιχείων είναι
8 12 15 33 45
Σε είδος επιλογής, με κάθε πέρασμα, το μικρότερο στοιχείο του πίνακα τοποθετείται στη σωστή του θέση. Ως εκ τούτου, στο τέλος της διαδικασίας ταξινόμησης, έχουμε έναν πλήρως ταξινομημένο πίνακα.
Ταξινόμηση εισαγωγής
Το είδος εισαγωγής είναι μια τεχνική στην οποία ξεκινάμε από το δεύτερο στοιχείο της λίστας. Συγκρίνουμε το δεύτερο στοιχείο με το προηγούμενο (1)αγ) στοιχείο και τοποθετήστε το στη σωστή του θέση. Στο επόμενο πέρασμα, για κάθε στοιχείο, το συγκρίνουμε με όλα τα προηγούμενα στοιχεία του και εισάγουμε αυτό το στοιχείο στη σωστή του θέση.
Οι παραπάνω τρεις τεχνικές ταξινόμησης είναι απλές και εύκολες στην εφαρμογή. Αυτές οι τεχνικές αποδίδουν καλά όταν το μέγεθος της λίστας είναι μικρότερο. Καθώς η λίστα μεγαλώνει, αυτές οι τεχνικές δεν αποδίδουν τόσο αποτελεσματικά.
Η τεχνική θα είναι ξεκάθαρη κατανοώντας την ακόλουθη εικόνα.
Ο πίνακας που θα ταξινομηθεί έχει ως εξής:
Τώρα για κάθε πάσο, συγκρίνουμε το τρέχον στοιχείο με όλα τα προηγούμενα στοιχεία του. Έτσι στο πρώτο πέρασμα, ξεκινάμε με το δεύτερο στοιχείο.
Επομένως, απαιτούμε τον αριθμό Ν περάσεων για να ταξινομήσουμε πλήρως έναν πίνακα που περιέχει αριθμό Ν στοιχείων.
Ας εφαρμόσουμε την τεχνική Εισαγωγή Ταξινόμησης χρησιμοποιώντας το C ++.
#include using namespace std; int main () { int myarray(5) = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < Παραγωγή:
Η λίστα εισαγωγής είναι
12 4 3 1 15
Η ταξινομημένη λίστα είναι
1 3 4 12 15
Η παραπάνω έξοδος δείχνει την πλήρη ταξινομημένη συστοιχία χρησιμοποιώντας την ένταξη εισαγωγής.
Γρήγορη ταξινόμηση
Το Quicksort είναι ο πιο αποτελεσματικός αλγόριθμος που μπορεί να χρησιμοποιηθεί για την ταξινόμηση των δεδομένων. Αυτή η τεχνική χρησιμοποιεί τη στρατηγική «διαίρεση και κατάκτηση» στην οποία το πρόβλημα χωρίζεται σε πολλά υποπροβλήματα και μετά την επίλυση αυτών των υποπροβλημάτων μεμονωμένα συγχωνεύονται μαζί για μια πλήρη ταξινομημένη λίστα.
Στη γρήγορη ταξινόμηση, διαιρούμε πρώτα τη λίστα γύρω από το στοιχείο περιστροφής και στη συνέχεια τοποθετούμε τα άλλα στοιχεία στις σωστές θέσεις τους σύμφωνα με το στοιχείο περιστροφής.
Όπως φαίνεται στην παραπάνω εικόνα, στην τεχνική Quicksort διαιρούμε τη διάταξη γύρω από ένα στοιχείο περιστροφής έτσι ώστε όλα τα στοιχεία μικρότερα από τον άξονα να βρίσκονται στα αριστερά του, ποια από αυτά που είναι μεγαλύτερα από τον άξονα είναι στα δεξιά της. Στη συνέχεια, παίρνουμε αυτές τις δύο συστοιχίες ανεξάρτητα και τα ταξινομούμε και, στη συνέχεια, ενώνουμε ή κατακτούμε για να πάρουμε μια προκύπτουσα ταξινομημένη σειρά.
Το κλειδί για το Quicksort είναι η επιλογή του περιστρεφόμενου στοιχείου. Μπορεί να είναι το πρώτο, το τελευταίο ή το μεσαίο στοιχείο του πίνακα. Το πρώτο βήμα μετά την επιλογή του στοιχείου περιστροφής είναι να τοποθετήσετε τον άξονα στη σωστή του θέση, ώστε να μπορούμε να διαιρέσουμε τον πίνακα σωστά.
Ας εφαρμόσουμε την τεχνική γρήγορης ταξινόμησης χρησιμοποιώντας το C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Παραγωγή:
Πίνακας εισόδου
12 23 3 43 51
Η σειρά ταξινομήθηκε με το Quicksort
3 12 23 43 51
Στην εφαρμογή γρήγορης ταξινόμησης παραπάνω, έχουμε μια ρουτίνα διαμερισμάτων που χρησιμοποιείται για την κατάτμηση του πίνακα εισόδου γύρω από ένα στοιχείο περιστροφής που είναι το τελευταίο στοιχείο του πίνακα. Στη συνέχεια, καλούμε τη ρουτίνα γρήγορης ταξινόμησης αναδρομικά για να ταξινομήσουμε μεμονωμένα τις δευτερεύουσες συστοιχίες όπως φαίνεται στην εικόνα.
Συγχώνευση ταξινόμησης
Αυτή είναι μια άλλη τεχνική που χρησιμοποιεί τη στρατηγική 'Διαίρεση και κατάκτηση'. Σε αυτήν την τεχνική, διαιρούμε πρώτα τη λίστα σε ίσα μισά. Στη συνέχεια, εκτελούμε ανεξάρτητη τεχνική ταξινόμησης σε αυτές τις λίστες έτσι ώστε και οι δύο λίστες να ταξινομούνται. Τέλος, συγχωνεύουμε και τις δύο λίστες για να λάβουμε μια πλήρη ταξινομημένη λίστα.
Η συγχώνευση και η γρήγορη ταξινόμηση είναι ταχύτερες από τις περισσότερες άλλες τεχνικές ταξινόμησης. Η απόδοσή τους παραμένει ανέπαφη ακόμα και όταν η λίστα μεγαλώνει σε μέγεθος.
Ας δούμε μια απεικόνιση της τεχνικής Merge Sort.
Στην παραπάνω εικόνα, βλέπουμε ότι η τεχνική συγχώνευσης διαχωρίζει τον αρχικό πίνακα σε δευτερεύουσες σειρές επανειλημμένα έως ότου υπάρχει μόνο ένα στοιχείο σε κάθε δευτερεύουσα σειρά. Μόλις γίνει αυτό, οι δευτερεύουσες σειρές ταξινομούνται στη συνέχεια ανεξάρτητα και συγχωνεύονται μαζί για να σχηματίσουν έναν πλήρη ταξινομημένο πίνακα.
Στη συνέχεια, ας εφαρμόσουμε το Merge Sort χρησιμοποιώντας τη γλώσσα C ++.
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< Παραγωγή:
Εισαγάγετε τον αριθμό των στοιχείων που θα ταξινομηθούν: 5
Εισαγάγετε 5 στοιχεία προς ταξινόμηση: 10 21 47 3 59
Ταξινομημένος πίνακας
3 10 21 47 59
Ταξινόμηση κελύφους
Η ταξινόμηση κελύφους είναι μια επέκταση της τεχνικής ταξινόμησης εισαγωγής. Στο είδος Εισαγωγής, ασχολούμαστε μόνο με το επόμενο στοιχείο ενώ, στο είδος κελύφους, παρέχουμε μια αύξηση ή ένα κενό χρησιμοποιώντας το οποίο δημιουργούμε μικρότερες λίστες από τη γονική λίστα. Τα στοιχεία στις δευτερεύουσες λίστες δεν χρειάζεται να είναι συνεχόμενα, αλλά συνήθως διαφέρουν μεταξύ τους ως προς τη «διαφορά τιμής».
Η ταξινόμηση κελύφους αποδίδει ταχύτερα από την ταξινόμηση εισαγωγής και απαιτεί λιγότερες κινήσεις από αυτήν της ταξινόμησης εισαγωγής.
Εάν παρέχουμε ένα κενό, τότε θα έχουμε τις ακόλουθες δευτερεύουσες λίστες με κάθε στοιχείο που απέχει 3 στοιχεία.
Στη συνέχεια ταξινομούμε αυτές τις τρεις λίστες.
Ο παραπάνω πίνακας που έχουμε αποκτήσει μετά τη συγχώνευση των ταξινομημένων υπο-συστοιχιών είναι σχεδόν ταξινομημένος. Τώρα μπορούμε να εκτελέσουμε ταξινόμηση εισαγωγής σε αυτόν τον πίνακα για να ταξινομήσουμε ολόκληρο τον πίνακα.
Έτσι βλέπουμε ότι μόλις διαιρέσουμε τον πίνακα σε λίστες χρησιμοποιώντας την κατάλληλη αύξηση και στη συνέχεια τις συγχωνεύουμε μαζί παίρνουμε τη σχεδόν ταξινομημένη λίστα. Η τεχνική ταξινόμησης εισαγωγής σε αυτήν τη λίστα μπορεί να εκτελεστεί και ο πίνακας ταξινομείται σε λιγότερες κινήσεις από το αρχικό είδος εισαγωγής.
Δίνεται παρακάτω η υλοποίηση του Shell Sort στο C ++.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18}; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i Παραγωγή:
Σειρά προς ταξινόμηση:
45 23 53 43 18
Διάταξη μετά το κέλυφος:
18 23 43 45 53
Το κέλυφος Shell λειτουργεί έτσι ως μια τεράστια βελτίωση σε σχέση με το είδος εισαγωγής και δεν παίρνει καν το μισό αριθμό βημάτων για την ταξινόμηση του πίνακα.
Ταξινόμηση σωρού
Το Heapsort είναι μια τεχνική στην οποία η δομή δεδομένων σωρού (min-heap ή max-heap) χρησιμοποιείται για την ταξινόμηση της λίστας. Κατασκευάζουμε πρώτα έναν σωρό από τη λίστα χωρίς ταξινόμηση και χρησιμοποιούμε επίσης το σωρό για να ταξινομήσουμε τον πίνακα.
Το Heapsort είναι αποτελεσματικό, αλλά όχι τόσο γρήγορο ή το είδος συγχώνευσης.
Όπως φαίνεται στην παραπάνω εικόνα, κατασκευάζουμε πρώτα έναν μέγιστο σωρό από τα στοιχεία του πίνακα που θα ταξινομηθούν. Στη συνέχεια, διασχίζουμε το σωρό και ανταλλάξουμε το τελευταίο και το πρώτο στοιχείο. Προς το παρόν το τελευταίο στοιχείο έχει ήδη ταξινομηθεί. Στη συνέχεια, κατασκευάζουμε ξανά έναν μέγιστο σωρό από τα υπόλοιπα στοιχεία.
Διασχίστε ξανά το σωρό και ανταλλάξτε το πρώτο και το τελευταίο στοιχείο και προσθέστε το τελευταίο στοιχείο στη λίστα ταξινόμησης. Αυτή η διαδικασία συνεχίζεται έως ότου υπάρχει μόνο ένα στοιχείο στο σωρό που γίνεται το πρώτο στοιχείο της ταξινομημένης λίστας.
Ας εφαρμόσουμε τώρα το Heap Sort χρησιμοποιώντας το C ++.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Παραγωγή:
Πίνακας εισόδου
4 17 3 12 9
Ταξινομημένος πίνακας
3 4 9 12 17
Μέχρι στιγμής έχουμε συζητήσει εν συντομία όλες τις σημαντικές τεχνικές ταξινόμησης με μια απεικόνιση. Θα μάθουμε καθεμιά από αυτές τις τεχνικές λεπτομερώς στα επόμενα σεμινάρια μαζί με διάφορα παραδείγματα για να κατανοήσουμε κάθε τεχνική.
συμπέρασμα
Απαιτείται ταξινόμηση για τη διατήρηση των δεδομένων σε σωστή σειρά. Η ταξινόμηση χωρίς διαλογή και ενδέχεται να διαρκέσει περισσότερο χρόνο για να έχει πρόσβαση και συνεπώς μπορεί να επηρεάσει την απόδοση ολόκληρου του προγράμματος. Έτσι, για οποιεσδήποτε λειτουργίες που σχετίζονται με δεδομένα όπως πρόσβαση, αναζήτηση, χειραγώγηση κ.λπ., χρειαζόμαστε την ταξινόμηση των δεδομένων.
Υπάρχουν πολλές τεχνικές ταξινόμησης που χρησιμοποιούνται στον προγραμματισμό. Κάθε τεχνική μπορεί να χρησιμοποιηθεί ανάλογα με τη δομή δεδομένων που χρησιμοποιούμε ή τον χρόνο που χρειάζεται ο αλγόριθμος για την ταξινόμηση των δεδομένων ή του χώρου μνήμης που λαμβάνει ο αλγόριθμος για την ταξινόμηση των δεδομένων. Η τεχνική που χρησιμοποιούμε εξαρτάται επίσης από τη δομή δεδομένων που ταξινομούμε.
Οι τεχνικές διαλογής μας επιτρέπουν να ταξινομήσουμε τις δομές δεδομένων μας με συγκεκριμένη σειρά και να τακτοποιήσουμε τα στοιχεία είτε σε αύξουσα είτε φθίνουσα σειρά. Έχουμε δει τις τεχνικές ταξινόμησης όπως το Bubble sort, Selection sort, Insertion sort, Quicksort, Shell sort, Merge sort και Heap sort. Ταξινόμηση φυσαλίδων και είδος επιλογής είναι απλούστερα και ευκολότερα στην εφαρμογή.
Στα επόμενα σεμινάρια μας, θα δούμε κάθε μία από τις παραπάνω αναφερόμενες τεχνικές διαλογής.
=> Κάντε κλικ εδώ για το δωρεάν μάθημα C ++.
Συνιστώμενη ανάγνωση
- Ταξινόμηση σωρού σε C ++ με παραδείγματα
- Συγχώνευση ταξινόμησης σε C ++ με παραδείγματα
- Εισαγωγή Ταξινόμηση σε C ++ με παραδείγματα
- JMeter Video 1: Εισαγωγή, Λήψη και εγκατάσταση του JMeter
- Εισαγωγή στη γλώσσα προγραμματισμού Java - Video Tutorial
- Διαδικασία εισαγωγής και εγκατάστασης Python
- Unix Sort Command με Σύνταξη, Επιλογές και Παραδείγματα
- MongoDB Sort () Μέθοδος με παραδείγματα
