En handledning för kodningsintervjuer

Att sortera listor med data är en så avgörande del av behandlingen i ansökningar.

Det är användbart för att visa data och utföra sökningar. Det är därför ingen överraskning att någon bra mjukvaruingenjör ska veta hur man sorterar arrayer. Den här artikeln förklarar några av de vanligaste algoritmerna för sortering av arrayer i JavaScript.

Vad är sortering och varför är det användbart?

Källa: Unsplash

Sortering är den systematiska organisationen av värden efter någon ordning. Denna ordning kan vara fallande eller stigande. Att sortera arrayer i JavaScript är användbart eftersom det gör att data kan visas mer meningsfullt.

Till exempel kan en person vilja se filer sorterade med de senaste filerna först eller produkter sorterade efter pris. Det är också användbart för att utföra binär sökning på data, som bara fungerar med sorterad data.

Även om det finns funktioner och bibliotek som hjälper dig att enkelt sortera data, behöver du fortfarande veta hur sortering fungerar under huven för kodningsintervjuer eller när du måste skriva lågnivåkod.

JavaScript Array Sort Algoritmer

Bubblesort

Bubble Sort är utan tvekan den enklaste algoritmen att förstå och implementera. Det fungerar genom att loopa genom arrayen i ett pass. Med varje pass rör vi oss genom arrayen, från början till slut, och jämför två intilliggande element. Om elementen är i fel ordning byter vi dem.

Vi utför n pass där n är antalet element i arrayen. Med varje pass sorteras arrayen med början från höger. Pseudokoden för algoritmen för att sortera siffror i stigande ordning är följande:

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.

Om man översätter det till JavaScript, skulle koden se ut så här:

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;
}

För att bättre förstå vad som händer rekommenderar jag att du lägger till en console.logs inuti de två slingorna för att se hur arrayen ändras för varje pass.

I koden nedan har jag modifierat sorteringsfunktionen för att lägga till console.logs inuti de två slingorna. Jag har också skapat en liten osorterad array som jag sorterade med hjälp av sorteringsfunktionen.

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);

Resultatet av att köra ovanstående kod skulle bli:

Bubblesortering har en Big O-tidskomplexitet på O(n ^ 2). Detta beror på att den utför n pass, som går genom arrayen för varje pass. Därför skalar den inte bra. Den har emellertid en rymdkomplexitet av O(1) eftersom den modifierar arrayelementen på plats.

Insättningssortering

Insättningssortering är en populär JavaScript-arraysorteringsalgoritm. Anta att vi använder insättningssortering för att sortera värden i stigande ordning. Algoritmen fungerar genom att välja ett nummer, som vi kallar num. Den flyttar sedan num åt vänster tills vartannat tal till vänster om num är mindre än num. Alla nummer kommer att sorteras om detta görs från det andra elementet till slutet. Här är en beskrivning i pseudokod.

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

Och nu är pseudokoden implementerad i JavaScript som följer.

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;
}

Precis som med Bubble Sort, kan du lägga till console.logs för att visualisera vad som händer. Kodavsnittet nedan visar dig Insertion Sort på jobbet.

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);

Och att köra kodavsnittet ovan ger följande resultat:

Sammanfoga sortering

Medan insättningssortering och bubblesortering skalar i kvadratisk tid, skalar sammanslagningssortering i kvasilinjär tid. Den har en tidskomplexitet av O(n * log(n)).

Sammanslagningssortering använder sig av dividera och erövra strategin. Arrayen delas upprepade gånger in i mindre arrayer med 1 element vardera. Efter delningen slås de sedan samman tillbaka.

Uppdelningen är rekursiv så att arrayen kan sättas ihop igen efteråt.

När arrayen slås tillbaka, slås underarrayerna samman i ordning. Sammanfogningen görs på samma sätt som du skulle slå samman en sorterad array. Pseudokoden för att göra det är skriven nedan:

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

Att implementera det i JavaScript skulle ge följande:

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));
}

Om du kör koden med en exempelarray borde den fungera.

Snabb sortering

Precis som Merge Sort förlitar sig Quick Sort på strategin dela-och-härska. Algoritmen väljer ett pivotelement. Därefter flyttar den alla element större än pivoten till höger och mindre än pivoten till vänster. När detta är gjort kommer pivoten att vara i rätt läge.

För att flytta element runt pivoten börjar algoritmen med att flytta pivoten till slutet av arrayen.

Efter att ha flyttat den använder vi en pekare för att slinga från arrayens vänstra sida och letar efter det första talet som är större än pivoten. Samtidigt använder vi en annan pekare från höger i arrayen och letar efter den första siffran som är mindre än pivoten. När båda numren har identifierats byter vi dem. Denna procedur upprepas tills pekaren från vänster är större än pekaren till höger.

När vi slutar byter vi det största av de två siffrorna som senast byttes med pivoten. Vid denna tidpunkt kommer pivoten att vara i rätt läge; siffror mindre än pivoten kommer att vara till vänster, medan de större kommer att vara till höger.

Denna procedur upprepas rekursivt för sub-arrayerna till vänster och höger om pivoten tills sub-arrayerna bara har ett element kvar.

Här är pseudokoden för snabb sortering:

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

Och konvertera det till 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;
}

Att sortera en exempelmatris med Quick Sorter i Node.js bör ge följande:

I bästa fall körs Quicksort i kvasilinjär tidskomplexitet. Utrymmesanvändningen i Quick Sorter skalas också logaritmiskt. Därför är det relativt effektivt jämfört med andra JavaScript-arraysorteringsalgoritmer.

Tips för dina kodningsintervjuer

❇️ Övning är nyckeln. Det hjälper dig att lära dig olika algoritmer, men ännu viktigare, det hjälper dig att utveckla problemlösnings- och beräkningstänkande. Du kan också träna på plattformar som Leetcode och AlgoExpert.

❇️ Försök att lösa problemet först. Istället för att hoppa direkt till lösningen, försök att lösa den, eftersom det hjälper dig att utveckla dina problemlösningsförmåga.

❇️ Om ett problem tar för lång tid, hoppa till lösningen; du kan fortfarande lära dig att lösa problemet från lösningen. De flesta plattformar för lärande erbjuder lösningar. ChatGPT eller Google Bard är också användbara för att förklara begrepp.

❇️ Skriv heller inte kod omedelbart; tavla dina lösningar och tänk igenom dem innan du skriver kod. Pseudokod är också ett användbart sätt att snabbt skriva ner idéer.

Slutsats

I den här artikeln täckte vi de mest populära sorteringsalgoritmerna. Men att lära sig allt detta kan verka överväldigande till en början. Därför brukar jag rekommendera att blanda olika källor istället för att bara lita på en. Glad kodning!

Kolla sedan in förstå sorterad funktion i Python.