Ένα σεμινάριο για την κωδικοποίηση συνεντεύξεων
Η ταξινόμηση λιστών δεδομένων είναι ένα τόσο κρίσιμο μέρος της επεξεργασίας σε εφαρμογές.
Είναι χρήσιμο για την εμφάνιση δεδομένων και την εκτέλεση αναζητήσεων. Επομένως, δεν αποτελεί έκπληξη το γεγονός ότι κάθε καλός μηχανικός λογισμικού πρέπει να γνωρίζει πώς να ταξινομεί πίνακες. Αυτό το άρθρο εξηγεί μερικούς από τους πιο συνηθισμένους αλγόριθμους για την ταξινόμηση πινάκων σε JavaScript.
Πίνακας περιεχομένων
Τι είναι η ταξινόμηση και γιατί είναι χρήσιμη;
Πηγή: Ξεβιδώστε
Η ταξινόμηση είναι η συστηματική οργάνωση των τιμών με κάποια σειρά. Αυτή η σειρά μπορεί να είναι φθίνουσα ή αύξουσα. Η ταξινόμηση πινάκων σε JavaScript είναι χρήσιμη καθώς επιτρέπει στα δεδομένα να εμφανίζονται πιο ουσιαστικά.
Για παράδειγμα, ένα άτομο μπορεί να θέλει να δει πρώτα αρχεία ταξινομημένα με τα πιο πρόσφατα αρχεία ή προϊόντα ταξινομημένα κατά τιμή. Είναι επίσης χρήσιμο για την εκτέλεση δυαδικής αναζήτησης σε δεδομένα, η οποία λειτουργεί μόνο με ταξινομημένα δεδομένα.
Αν και υπάρχουν λειτουργίες και βιβλιοθήκες που σας βοηθούν να ταξινομείτε εύκολα τα δεδομένα, πρέπει να γνωρίζετε πώς λειτουργεί η ταξινόμηση κάτω από την κουκούλα για την κωδικοποίηση συνεντεύξεων ή πότε πρέπει να γράψετε κώδικα χαμηλού επιπέδου.
Αλγόριθμοι ταξινόμησης πίνακα JavaScript
Ταξινόμηση με φυσαλίδες
Το Bubble Sort είναι αναμφισβήτητα ο πιο εύκολος αλγόριθμος για κατανόηση και εφαρμογή. Λειτουργεί κάνοντας loop μέσω του πίνακα σε ένα πέρασμα. Με κάθε πέρασμα, περνάμε μέσα από τον πίνακα, από την αρχή μέχρι το τέλος, συγκρίνοντας δύο γειτονικά στοιχεία. Εάν τα στοιχεία είναι σε λάθος σειρά, τα ανταλλάσσουμε.
Εκτελούμε n περάσματα όπου n είναι ο αριθμός των στοιχείων του πίνακα. Με κάθε πέρασμα, ο πίνακας ταξινομείται ξεκινώντας από τα δεξιά. Ο ψευδοκώδικας για τον αλγόριθμο για την ταξινόμηση των αριθμών σε αύξουσα σειρά είναι ο εξής:
1. Let n be the number of elements in the array 2. Loop n times, keeping count of the loops using i (doing the following in each loop) a. loop the array from the second element to the (n - i)th element b. if the previous element is greater than the current element, swap them.
Μεταφράζοντας το σε JavaScript, ο κώδικας θα μοιάζει με αυτό:
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
Για να κατανοήσετε καλύτερα τι συμβαίνει, θα συνιστούσα να προσθέσετε ένα console.logs μέσα στους δύο βρόχους για να δείτε πώς αλλάζει ο πίνακας με κάθε πέρασμα.
Στον παρακάτω κώδικα, έχω τροποποιήσει τη συνάρτηση ταξινόμησης για να προσθέσω console.logs μέσα στους δύο βρόχους. Έχω δημιουργήσει επίσης έναν μικρό μη ταξινομημένο πίνακα τον οποίο ταξινόμησα χρησιμοποιώντας τη συνάρτηση ταξινόμησης.
function sort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
console.log(`Pass: ${i}`);
for (let j = 1; j < n - i; j++) {
if (arr[j - 1] > arr[j]) {
const temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
console.log(arr);
}
}
return arr;
}
const array = [9, 2, 7, 4, 1];
sort(array);
console.log(array);
Το αποτέλεσμα της εκτέλεσης του παραπάνω κώδικα θα ήταν:
Η ταξινόμηση με φυσαλίδες έχει πολυπλοκότητα χρόνου Big O O(n ^ 2). Αυτό συμβαίνει επειδή εκτελεί n περάσματα, τα οποία περνούν βρόχο μέσω του πίνακα για κάθε πέρασμα. Επομένως, δεν κλιμακώνεται καλά. Ωστόσο, έχει πολυπλοκότητα χώρου O(1) αφού τροποποιεί τα στοιχεία του πίνακα στη θέση τους.
Ταξινόμηση εισαγωγής
Η ταξινόμηση εισαγωγής είναι ένας δημοφιλής αλγόριθμος ταξινόμησης πίνακα JavaScript. Ας υποθέσουμε ότι χρησιμοποιούμε ταξινόμηση εισαγωγής για να ταξινομήσουμε τις τιμές με αύξουσα σειρά. Ο αλγόριθμος λειτουργεί επιλέγοντας έναν αριθμό, τον οποίο θα ονομάσουμε num. Στη συνέχεια μετακινείται το num αριστερά έως ότου κάθε άλλος αριθμός στα αριστερά του num είναι μικρότερος από τον num. Όλοι οι αριθμοί θα ταξινομηθούν εάν αυτό γίνει από το δεύτερο στοιχείο μέχρι το τέλος. Εδώ είναι μια περιγραφή σε ψευδοκώδικα.
1. Let n be the number of elements in the array
2. Loop i from 1 to n - 1 (start from the second element)
a. Set currentElement to array[i]
b. Set j to i - 1
c. While j >= 0 and array[j] > current_element
i. Move array[j] to array[j+1]
ii. Decrement j by 1
d. Set array[j+1] to current_element
Και τώρα, ο ψευδοκώδικας που εφαρμόζεται στο JavaScript είναι ο εξής.
function insertionSort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
}
return array;
}
Όπως και με το Bubble Sort, η προσθήκη console.logs σάς βοηθά να οπτικοποιήσετε τι συμβαίνει. Το παρακάτω απόσπασμα κώδικα σάς δείχνει την Ταξινόμηση Εισαγωγής στην εργασία.
function sort(array) {
const n = array.length;
for (let i = 1; i < n; i++) {
const currentElement = array[i];
let j = i - 1;
console.log("Placing element:", currentElement);
while (j >= 0 && array[j] > currentElement) {
array[j + 1] = array[j];
j -= 1;
}
array[j + 1] = currentElement;
console.log("Placed it at position:", j + 1);
console.log(array);
}
return array;
}
const array = [4, 1, 2, 5, 3];
sort(array);
Και η εκτέλεση του παραπάνω αποσπάσματος έχει το ακόλουθο αποτέλεσμα:
Ταξινόμηση συγχώνευσης
Ενώ η κλίμακα Εισαγωγής Ταξινόμησης και Ταξινόμησης με Φούσκα σε τετραγωνικό χρόνο, η Ταξινόμηση Συγχώνευσης κλιμακώνεται σε σχεδόν γραμμικό χρόνο. Έχει χρονική πολυπλοκότητα O(n * log(n)).
Η ταξινόμηση συγχώνευσης χρησιμοποιεί τη στρατηγική διαίρει και βασίλευε. Ο πίνακας χωρίζεται επανειλημμένα σε μικρότερους πίνακες από 1 στοιχείο ο καθένας. Μετά τη διαίρεση, στη συνέχεια συγχωνεύονται ξανά.
Η διαίρεση είναι αναδρομική έτσι ώστε ο πίνακας να μπορεί να επανασυναρμολογηθεί μετά.
Κατά τη συγχώνευση του πίνακα πίσω, οι υποσυστοιχίες συγχωνεύονται με τη σειρά. Η συγχώνευση γίνεται με τον ίδιο τρόπο που θα συγχωνεύατε έναν ταξινομημένο πίνακα. Ο ψευδοκώδικας για να γίνει αυτό είναι γραμμένος παρακάτω:
1. If the length of the array is 1 or less, return the array (base case)
2. Find the middle index:
a. Set mid to the floor of (length of the array / 2)
3. Divide the array into two subarrays:
a. Create leftArray and copy the first half of the array into it (from index 0 to mid)
b. Create rightArray and copy the second half of the array into it (from index mid+1 to the end)
4. Recursively call MergeSort on leftArray
5. Recursively call MergeSort on rightArray
6. Merge the two sorted subarrays:
a. Create an empty resultArray
b. While both leftArray and rightArray are not empty:
i. If the first element in leftArray is less than or equal to the first element in rightArray, append it to resultArray
ii. Otherwise, append the first element in rightArray to resultArray
c. Append any remaining elements in leftArray to resultArray (if any)
d. Append any remaining elements in rightArray to resultArray (if any)
7. Return resultArray
Η εφαρμογή του σε JavaScript θα είχε τα εξής:
function sort(array) {
// Base case in which we stop subdividing the array
if (array.length == 1) {
return array;
}
// Finding the middle point of the array
const m = Math.round(array.length / 2);
// Divide the array into two halves
const leftUnsorted = array.slice(0, m);
const rightUnsorted = array.slice(m);
// Recursively call merge sort
const leftSorted = sort(leftUnsorted);
const rightSorted = sort(rightUnsorted);
// Return a merged sorted array
return merge(leftSorted, rightSorted);
}
function merge(left, right) {
// Merge two sorted lists
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex += 1;
} else {
result.push(right[rightIndex]);
rightIndex += 1;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
Εάν εκτελείτε τον κώδικα με έναν πίνακα παραδειγμάτων, θα πρέπει να λειτουργεί.
Γρήγορη ταξινόμηση
Όπως το Merge Sort, έτσι και το Quick Sort βασίζεται στη στρατηγική διαίρει και βασίλευε. Ο αλγόριθμος επιλέγει ένα στοιχείο περιστροφής. Στη συνέχεια, μετακινεί όλα τα στοιχεία μεγαλύτερα από τον άξονα προς τα δεξιά και μικρότερα από τον άξονα προς τα αριστερά του. Μόλις γίνει αυτό, ο άξονας περιστροφής θα είναι στη σωστή θέση.
Για να μετακινήσετε στοιχεία γύρω από τον άξονα, ο αλγόριθμος ξεκινά μετακινώντας τον άξονα στο τέλος του πίνακα.
Αφού τον μετακινήσουμε, χρησιμοποιούμε έναν δείκτη για να κάνουμε βρόχο από τα αριστερά του πίνακα, αναζητώντας τον πρώτο αριθμό μεγαλύτερο από το pivot. Ταυτόχρονα, χρησιμοποιούμε έναν άλλο βρόχο δείκτη από τα δεξιά του πίνακα, αναζητώντας τον πρώτο αριθμό μικρότερο από το pivot. Μόλις εντοπιστούν και οι δύο αριθμοί, τους ανταλλάσσουμε. Αυτή η διαδικασία επαναλαμβάνεται έως ότου ο δείκτης από τα αριστερά είναι μεγαλύτερος από τον δείκτη προς τα δεξιά.
Όταν σταματήσουμε, ανταλλάσσουμε τον μεγαλύτερο από τους δύο αριθμούς που ανταλλάχτηκαν τελευταία με τον άξονα περιστροφής. Σε αυτό το σημείο, ο άξονας θα είναι στη σωστή θέση. Οι αριθμοί μικρότεροι από τον άξονα θα είναι προς τα αριστερά, ενώ οι μεγαλύτεροι θα είναι προς τα δεξιά.
Αυτή η διαδικασία επαναλαμβάνεται αναδρομικά για τους υπο-πίνακες στα αριστερά και δεξιά του άξονα περιστροφής έως ότου οι υποπίνακες έχουν μόνο ένα στοιχείο αριστερά.
Εδώ είναι ο ψευδοκώδικας για γρήγορη ταξινόμηση:
1. If lessThanPointer is less than greaterThanPointer:
a. Choose a pivot element from the array
b. Move elements such that elements less are to the left and elements greater are to the right:
c. Recursively call Quicksort on leftSubarray
d. Recursively call Quicksort on rightSubarray
Και μετατρέποντάς το σε JavaScript:
function sort(array, low, high) {
if (low < high) {
// Choose the pivot index and partition the array
const pivotIndex = move(array, low, high);
// Recursively sort the subarrays to the left and right of the pivot
sort(array, low, pivotIndex - 1);
sort(array, pivotIndex + 1, high);
}
}
function move(array, low, high) {
// Select the pivot element (in this case, the last element)
const pivotElement = array[high];
// Initialize the index for the smaller element
let i = low - 1;
for (let j = low; j < high; j++) {
// If the current element is less than or equal to the pivot, swap it with the element at index i+1
if (array[j] <= pivotElement) {
i += 1;
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Swap the pivot element into its correct position
const temp = array[i];
array[i] = array[j];
array[j] = temp;
// Return the index of the pivot element
return i + 1;
}
Η ταξινόμηση ενός παραδείγματος πίνακα με Γρήγορη ταξινόμηση στο Node.js θα πρέπει να αποφέρει τα εξής:
Στην καλύτερη περίπτωση, το Quicksort εκτελείται σε σχεδόν γραμμική χρονική πολυπλοκότητα. Η χρήση του χώρου στη Γρήγορη ταξινόμηση κλιμακώνεται επίσης λογαριθμικά. Επομένως, είναι σχετικά αποτελεσματικό σε σύγκριση με άλλους αλγόριθμους ταξινόμησης πίνακα JavaScript.
Συμβουλές για τις συνεντεύξεις σας για την κωδικοποίηση
❇️ Η εξάσκηση είναι το κλειδί. Σας βοηθά να μάθετε διαφορετικούς αλγόριθμους, αλλά το πιο σημαντικό, σας βοηθά να αναπτύξετε δεξιότητες επίλυσης προβλημάτων και υπολογιστικής σκέψης. Μπορείτε επίσης να εξασκηθείτε σε πλατφόρμες όπως Leetcode και AlgoExpert.
❇️ Προσπαθήστε πρώτα να λύσετε το πρόβλημα. Αντί να μεταβείτε κατευθείαν στη λύση, προσπαθήστε να τη λύσετε, καθώς σας βοηθά να αναπτύξετε τις δεξιότητές σας στην επίλυση προβλημάτων.
❇️ Εάν ένα πρόβλημα διαρκεί πολύ, μεταβείτε στη λύση. μπορείτε ακόμα να μάθετε να λύνετε το πρόβλημα από τη λύση. Οι περισσότερες πλατφόρμες μάθησης προσφέρουν λύσεις. Το ChatGPT ή το Google Bard είναι επίσης χρήσιμα για την εξήγηση εννοιών.
❇️ Επίσης, μην γράφετε αμέσως κώδικα. πίνακας των λύσεών σας και σκεφτείτε τες πριν γράψετε κώδικα. Ο ψευδοκώδικας είναι επίσης ένας χρήσιμος τρόπος γρήγορης καταγραφής ιδεών.
συμπέρασμα
Σε αυτό το άρθρο, καλύψαμε τους πιο δημοφιλείς αλγόριθμους ταξινόμησης. Ωστόσο, η εκμάθηση όλων αυτών μπορεί να φαίνεται συντριπτική στην αρχή. Ως εκ τούτου, συνήθως συνιστώ την ανάμειξη διαφόρων πηγών αντί να βασίζεστε απλώς σε μία. Καλή Κωδικοποίηση!
Στη συνέχεια, ελέγξτε την κατανόηση της ταξινομημένης συνάρτησης στην Python.