Ett hashtabell har en hash function som mappar ett element till ett index där det bör sparas i tabellen. En bra hash function distibuerar elementen jämnt över tabellen för att inte orsaka kollisioner, den ska även vara enkel att beräkna. Så att medelkostnaden blir O(1).
Detta exempel lämpar sig för tabeller som inte är allt för stora.
int hash( const string& key, int tableSize )
{
int hashVal = 0;
for( int i = 0; i < key.length( ); i++ )
hashVal += key[ i ];
return hashVal % tableSize;
}Bör undvikas om möjligt. För en lösning kräver antingen att en ny algoritm eller ny datastruktur används. Två stycken diskuteras i föreläsningarna:
- Separete chaining. Vid kollision används en linked list. Så att vid varje index återfås en lista.
- Open addressing. Att genom en andra algoritm lösa problemet.
- Linear probing. Hitta nästa tomma plats efter det designerade indexet från hash funnktionen i tabellen och placera elementet där i.
- Double hashing. En andra hash function används där positioner som
h1(x) + n*h2(x), där n går från 1 tillsize, tills en tom plats hittas.
För varje element i listan, kolla elementet och jämför med elementet direkt till höger. Om de är osorterade, byt plats på dom. Efter varje passering kommer det sista värdet att vara sorterat. Alltså kan algoritmen effektiviseras genom att efter varje pass minska antalet element som jämförs.
Denna algoritm kräver som mest n-1 omgångar för att få en lista sorterad.
Hitta det minsta värdet och sätt det först i den sorterade delen av listan. Kolla sedan igenom den osorterade delen efter det minsta värdet igen och flytta till slutet av den sorterade delen.
Inte den mest effektiva. Dela upp listan i en sorted och en unsortedd del. Ta ett element från den osorterade delen och jämför bakåt mot den sorterade listan tills rätt plats hittas och då trycks den in.
for(int i = 1; i < a.size; ++i)
{
Comparable tmp = std::move(a[p]);
int j;
for(j = i; j > 0 && tmp < a[j-1]; j-- )
a[j] = std::move(a[j-1])
a[j] = std::move(tmp);
}Dela antalet element i arrayen med två och ta the integer part av resultatet. Dela sedan arrayen i sublists, så många som resultatet blev. Sortera listorna var för sig och mergea ihop. Dela sedan den förra integern med två och ta the integer part. Samma procedur.
for(int gap = a.size()/2; gap > 0; gap /= 2)
{
for(int i = gap; i < a.size(); ++i)
{
Comparable tmp = std::move(a[i]);
int j = i;
for(; j >=gap && tmp < a[j-gap]; j-=gap)
a[j] = std::move(a[j-gap]);
a[j] = std::move(tmp);
}
}Swap mellan rooten och det sista värdet. Åtgärda eventuella fel som gör så att det inte är en heap längre. Ta sedan bort det sista värdet (det som precis var rooten).
Att meargea två sorterade listor görs genom att jämföra de första värdena i listorna och flytta det minsta till en ny lista, reapeat tills en av listorna är tomma. Då är det bara att stoppa resten av den andra i slutet.
För att sortera med mergesort, dela upp listan tills det blir listor som bara innehåller ett element. Använd sedan merge-algoritmen ovan för att slå ihop listorna.
O(n*log(n)), dock kräver denna att en ny lista måste skapas så mer minne krävs.
Medelkostnaden för denna sortering är O(NlogN), i värsta fall O(n^2) Det är en algoritm som baseras på idén om att dela upp problemet i mindre delar och lösa dessa för att sedan kombinera till en stor lösning. "Classic quicksort" följer fyra enkla steg för att sortera arrayen S:
- Om antalet element i S är 1 eller 0, return
- Välj ett element v i S. Kalla detta element för pivot
- Dela upp S utan v, S1 och S2.
return {quicksort(S1)+v+quicksort(S2)}
- Preorder. För varje subtree gå från höger till vänster.
void BinaryTree::preorder(Node \*v)
{
if (v != nullptr)
{
DoSomething(v);
preorder(v->left);
preorder(v->right);
}
}- Postorder. Löven i varje subtree först, först det vänstra.
void BinaryTree::postorder(Node \*v)
{
if (v != nullptr)
{
postorder(v->left);
postorder(v->right);
DoSomething(v);
}
}- Inorder. Från det mest vänstra lövet i det vänstra subtreet till det mest högra lövet i det högra subtreet.
void BinaryTree::inorder(Node \*v)
{
if (v != nullptr)
{
inorder(v->left);
DoSomething(v);
inorder(v->right);
}
}- Om det är ett löv kan noden tas bort direkt.
- Om noden har endast ett child kan noden tas bort och länken från parent kan dras till child istället.
- Om noden har två childs tas det minsta värdet från det högra subtreet och ersätter noden som ska tas bort. noder tas sedan rekursivt bort.
Ett AVL träd är ett träd där varje child tree har samma höjd, med den maximala höjdskillnaden på 1. Ett balanserat träd som är effektivt att söka i.
Efter varje borttagning eller tillägg i trädet måste det försäkras om att trädet fortfarande följer AVL-trädens kriterier. Om det inte gör det måste en operation på trädet utföras, en så kallad rotation. Det finns fyra olika fall och rotationer vid tillägg:
- Insertion on the left subtree of the left child of 𝒏 (LL)
- Insertion on the right subtree of the left child of 𝒏 (LR)
- Insertion on the right subtree of the right child of 𝒏 (RR)
- Insertion on the left subtree of the right child of 𝒏 (RL)
En heap är ett binary tree som är helt fullt med det möjliga undantaget för bottenvåningen som är fylld från vänster till höger. På grund av dessa egenskaper kan heapen representeras i en array. Egenskapen som snabbar upp operationer på heapen kallas för heap-order priority. Det betyder att det minsta värdet är alltid vid rooten. Alltså kommer findMin() alltid vara i konstant tid.
Ett hål skapas vid nästa lediga plats. Om X kan placeras där så görs det. Annars byter parent och hålet plats. Och X placeras om det går. Detta itereras tills X har placerats. Strategin kallas för percolate up.
Borttagningar sker på ett liknande sätt som insert. Rooten tas bort och ersätts med ett hål. Eftersom heapen blir en mindre måste det sista elementet flyttas. Om det inte kan placeras i hålet byter hålet plats med det minsta av sina barn. Detta itereras tills hålet fylls. Strategin kallas för percolate down.
För varje nod som besöks markeras den som besökt med en bool. Detta försäkrar att inga loopar kommer att ske över redan besökta noder.
De noder som ligger närmast startnoden besöks först. Sen kommer de som ligger två steg bort osv. När en nod har besökts kommer den att markeras som besökt med en bool för att inte besöka dubbletter.
Det är en shortest-path algorithm skapad för grafer med viktade kopplingar. Efter att en nod har besökts markeras den som det med hjälp av en bool?. För varje nod loopas närgränsande noder igenom och den med minsta vikt/väg väljs att gå vidare med.
Med denna metod kommer inga noder att besökas flera gånger då endast obesökta är med i beräkningarna.
Hitta det bästa sättet för att skapa länkar mellan noder i en graf.
Vid varje steg så hittar den en nod att lägga till genom att välja den kant(edge) som har minst kostnad mellan huvudnoden och den som ska läggas till. Väldigt lik Dijktras algoritm för shortest-path i hur den loopar igenom och hittar aktuella noder. Skillnaden är i hur vikterna jämförs, men tekniken att markera noder som besökta finns fortfarande.
- För att hitta ett minimalt uppspännande träd T i den sammanhängande grafen G
- Upprepa tills T innehåller alla noder i G
- Låt v vara den kortaste sträckan i G som inte märkts som förbrukad
- Märk v som förbrukad
- Om v inte bildar en cykel i T
- Lägg v till T
- T är ett minimalt uppspännande träd