Сортирање листа података је тако кључни део обраде у апликацијама.
Користан је за приказивање података и обављање претрага. Стога није изненађење да сваки добар софтверски инжењер зна како да сортира низове. Овај чланак објашњава неке од најчешћих алгоритама за сортирање низова у ЈаваСцрипт-у.
Преглед садржаја
Шта је сортирање и зашто је корисно?
Извор: Унспласх
Сортирање је систематско организовање вредности по неком реду. Овај редослед може бити силазни или растући. Сортирање низова у ЈаваСцрипт-у је корисно јер омогућава садржајнији приказ података.
На пример, особа ће можда желети да види датотеке поређане прво са најновијим датотекама или производе сортиране по цени. Такође је корисно за обављање бинарне претраге података, која ради само са сортираним подацима.
Иако постоје функције и библиотеке које вам помажу да лако сортирате податке, још увек морате да знате како сортирање функционише испод хаубе за кодирање интервјуа или када морате да пишете код ниског нивоа.
Алгоритми за сортирање низова ЈаваСцрипт
Буббле Сорт
Буббле Сорт је вероватно најлакши алгоритам за разумевање и имплементацију. Ради тако што се петља кроз низ у пролазу. Са сваким пролазом, крећемо се кроз низ, од почетка до краја, упоређујући два суседна елемента. Ако су елементи у погрешном редоследу, мењамо их.
Изводимо н пролаза где је н број елемената у низу. Са сваким пролазом, низ се сортира почевши са десне стране. Псеудокод за алгоритам за сортирање бројева у растућем редоследу је следећи:
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.
Преводећи га у ЈаваСцрипт, код би изгледао овако:
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;
}
Да бисте боље разумели шта се дешава, препоручио бих да додате цонсоле.логс унутар две петље да видите како се низ мења са сваким пролазом.
У коду испод, модификовао сам функцију сортирања да бих додао цонсоле.логс унутар две петље. Такође сам направио мали несортирани низ који сам сортирао помоћу функције сортирања.
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);
Резултат покретања горњег кода би био:
Разврставање мехурића има велику О временску сложеност од О(н ^ 2). То је зато што изводи н пролаза, који се провлаче кроз низ за сваки пролаз. Због тога се не мери добро. Међутим, он има просторну сложеност од О(1) пошто модификује елементе низа на месту.
Инсертион Сорт
Сортирање уметањем је популаран ЈаваСцрипт алгоритам за сортирање низа. Претпоставимо да користимо сортирање уметањем за сортирање вредности у растућем редоследу. Алгоритам функционише тако што бирамо број, који ћемо назвати нум. Затим помера нум лево док сваки други број лево од нум не буде мањи од броја. Сви бројеви ће бити поређани ако се то уради од другог елемента до краја. Ево описа у псеудокоду.
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
А сада, псеудокод имплементиран у ЈаваСцрипт-у је следећи.
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;
}
Као и код Буббле Сорт, додавање цонсоле.логс помаже вам да визуализујете шта се дешава. Исечак кода испод показује вам Сортирање уметањем на послу.
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);
А покретање горњег исечка даје следећи резултат:
Сортирање спајањем
Док се сортирање уметањем и сортирање мехурићем скале у квадратном времену, сортирање спајањем се скалира у квазилинеарном времену. Има временску сложеност од О(н * лог(н)).
Сортирање спајањем користи стратегију завади па владај. Низ се више пута дели на мање низове од по 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
Примена у ЈаваСцрипт-у би донела следеће:
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));
}
Ако покренете код са примером низа, требало би да функционише.
Куицк Сорт
Као и сортирање спајањем, брзо сортирање се ослања на стратегију завади па владај. Алгоритам бира стожерни елемент. Затим помера све елементе веће од осовине удесно и мање од осовине са леве стране. Када се ово уради, стожер ће бити у исправном положају.
Да би померио елементе око стожера, алгоритам почиње померањем осовине до краја низа.
Након што га померимо, користимо показивач за петљу са леве стране низа, тражећи први број већи од стожера. Истовремено, користимо другу петљу показивача са десне стране низа, тражећи први број мањи од стожера. Када се идентификују оба броја, мењамо их. Овај поступак се понавља све док показивач са леве стране не буде већи од показивача са десне стране.
Када се зауставимо, мењамо већи од два последња броја замењена са пивот-ом. У овом тренутку, стожер ће бити у исправном положају; бројеви мањи од стожера биће лево, док ће они већи бити десно.
Ова процедура се рекурзивно понавља за поднизе лево и десно од стожера све док поднизови немају преостао само један елемент.
Ево псеудокода за брзо сортирање:
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
И претварање у ЈаваСцрипт:
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;
}
Сортирање примера низа помоћу Куицк Сорт у Ноде.јс би требало да добије следеће:
У најбољем случају, Куицксорт ради у квазилинеарној временској сложености. Коришћење простора у брзом сортирању такође се логаритамски скалира. Стога је релативно ефикасан у поређењу са другим алгоритмима за сортирање низова ЈаваСцрипт.
Савети за ваше интервјуе за кодирање
❇ Вежба је кључна. Помаже вам да научите различите алгоритме, али што је још важније, помаже вам да развијете вештине решавања проблема и рачунарског размишљања. Такође можете вежбати на платформама као што су Леетцоде и АлгоЕкперт.
❇ Покушајте прво да решите проблем. Уместо да скочите право на решење, покушајте да га решите, јер вам то помаже да развијете своје вештине решавања проблема.
❇ Ако проблем траје предуго, пређите на решење; још увек можете научити да решите проблем из решења. Већина платформи за учење нуди решења. ЦхатГПТ или Гоогле Бард су такође корисни за објашњење концепата.
❇ Такође, немојте одмах писати код; Ваша решења на табли и размислите о њима пре него што напишете код. Псеудокод је такође користан начин за брзо записивање идеја.
Закључак
У овом чланку смо покрили најпопуларније алгоритме за сортирање. Међутим, учење свега овога у почетку може изгледати неодољиво. Стога обично препоручујем мешање различитих извора уместо да се ослањате само на један. Срећно кодирање!
Затим погледајте разумевање сортиране функције у Питхон-у.