Algoritmi

Table of Contents

1. Algoritmi

1.1. Algoritmi di Sorting

1.1.1. Insertion Sort

La struttura ciclica inizia le iterazioni dal secondo elemeno in poi. Per ciascun j-esimo elemento l'algoritmo lo confronta con gli elementi precedenti tramite una struttura ciclica condizionata while più interna.

  • Se trova un elemento più grande lo sposta in avanti.
  • Se trova un elemento minore o uguale termina il ciclo più interno (while).

L'algoritmo cessa l'esecuzione quando termina il ciclo più esterno (for) 

procedure insertionSort(in/out: arr, in: n)
var i, j: integer
begin
   for j := 2 to n step 1 do
      i := j-1
      while (i > 0 .AND. arr(i) > arr(j))
         i := i-1
      endwhile
      arr(i+1) = arr(j)
   endfor
end

1.1.2. Merge Sort

procedure mergeSort(in/out: arr; in: left, right)
var mid: integer
begin
   if (left < right) then
      mid := (left + right) div 2
      mergeSort(arr, left, mid)
      mergeSort(arr, mid+1, right)
      merge(arr, left, mid, right)
   end if
end

procedure merge(in/out: arr, in: left, mid, right)
var i, j, k: integer
var b: array[1..(right-left+1)] of integer

begin
   i := left
   j := center + 1
   k := 0

   while i <= center .AND. j <= right do
      if arr[i] <= arr[j] then
         b[k] := arr[i]
         i := i+1
      else
         b[k] := arr[j]
         j := j+1
      end if
      k := k+1
   end while

   while i <= center do
      b[k] := arr[i]
      i := i+1
      k := k+1
   end while


   while j <= right do
      b[k] := a[j]
      j := j + 1
      k := k + 1
   end while

   for k := left to right do
      a[k] := b[k-left]
   end for
end

1.1.3. Quick Sort

Si tratta d un algoritmo di ordinamento ricorsivo che implementa la strategia divide et impera. Si seleziona un elemento pivot che divide in due il vettore in modo da ottenere due sottosequenze, successivamente tutti gli elementi maggiori del pivot vengono spostati alla sua destra, mentre tutti quelli minori o uguali alla sua sinistra. 

function integer partition(in/out: arr: array of real; in: left: integer; in: right: integer)
  var i, j: integer
  var temp, pivot: real
begin
  pivot := arr[(left + right) div 2]  -- Seleziona il pivot come elemento centrale
  i := left
  j := right

  while i <= j do
    while arr[i] < pivot do
      i := i + 1
    endwhile
    while arr[j] > pivot do
      j := j - 1
    endwhile
    if i <= j then
      -- Scambia gli elementi arr[i] e arr[j]
      temp := arr[i]
      arr[i] := arr[j]
      arr[j] := temp
      i := i + 1
      j := j - 1
    endif
  endwhile
  return i 
end

procedure quickSort(in/out: arr: array of real; in: left: integer; in: right: integer)
  var pivotIndex: integer
begin
  if left < right then
    -- Divide l'array in due sottosequenze
    pivotIndex := partition(arr, left, right)
    -- Ordina ricorsivamente le due sottosequenze
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex, right)
  endif
end

1.1.4. Exchange Sort

Ad ogni passo si controllano due elementi adiacenti e, se non ordinati, si scambiano. L'operazione si ripete fino a quando l'array non è completamente ordinato. Esempio in plike: 

procedure exchangeSort(in: n; in/out: v)
 var: i, j, n: integer
 var: v: array [1..n] of real
 var: ordinato: logical
 var: scambio: real

 begin
  ordinato := .FALSE.
  while ordinato = .FALSE. do
   ordinato := true
   for i := 1 to n-1 do     
    if (v(i) > v(i+1)) then
     scambio := v(i+1)
     v(i+1) := v(i)
     v(i) := scambio
     ordinato := false
    endif
   endfor
  endwhile
 end

1.1.5. Selection Sort

Ad ogni passo si individua il più piccolo elemento e lo si scambia con l'elemento che occupa il primo posto. Esempio in plike: 

procedure selectionSort(in: n; in/out: v)
 var: i, j, n, p: integer
 var: v: array [1..n] of real
 var: min: real
 begin
  for i := 1 to n-1 do
   min := v(i)
   p := i
   for j := i+1 to n do
    if (v(j)<min) then
     min:=v(j)
     p:=j
    endif
   endfor
  endfor
 end

1.2. Alogirtmi di Ricerca

1.2.1. Sequential Search

La ricerca sequenziale è un metodo di ricerca molto semplice che consiste nello scorrere tutti gli elementi dell'array fino a quando l'elemento desiderato non viene trovato (o la lunghezza dell'array viene raggiunta). 

function integer sequentialSearch(in: arr, n, t)
var i: integer
begin
   for i := 1 to n do
      if arr(i) = t then
         return i
      end if
   end for
   return -1   
end

1.2.2. Binary Search

La ricerca binaria serve a trovare un valore in un vettore che deve necessariamente essere ordinato. Lavora dividendo costantemente l'intervallo di ricerca a metà fino a quando il valore non viene trovato o l'intervallo diventa vuoto. 

procedure binarySearch(in: arr, target, n, out: result)
var left, right, mid: integer
begin
   left := 1               // Inizio dell'intervallo (assumendo array indicizzato da 1)
   right := n              // Fine dell'intervallo
   result := -1            // Valore predefinito per "non trovato"

   while left <= right do
      mid := (left + right) div 2   // Calcola l'indice centrale
      if arr(mid) = target then
         result := mid              // Trovato: salva la posizione
         return result              // Esci dalla procedura
      else if arr(mid) < target then
         left := mid + 1            // Cerca nella metà destra
      else
         right := mid - 1           // Cerca nella metà sinistra
      end if
   end while

   return result  // Se non trovato, restituisce -1
end

2. Puntatori

3. Strutture Dati Astratte

3.1. Stack

Lo stack è una struttura dati astratta che segue il principio LIFO (Last In First Out). Operazioni prinicpali:

  • Push (Inserisci elemento in cima)
  • Pop (Rimuovi elemento in cima)
  • Peek (Visualizza elemento in cima)

Lo stack può essere implementato tramite array o Linked List (quest'ultima implementazione è preferibile).

3.1.1. Operazioni

  1. Dichiarazione

    In P-Like: 

    Type stack_pointer: *nodo_stack
nodo_stack: record
   info: integer //esempio
   link: stack_pointer
end

var head: stack_pointer

    In linguaggio C: 

    typedef struct nodo_stack {
  int info;
  struct nodo_stack *link;
} NodoStack;

NodoStack *head = NULL;
  2. Push

    Modifica la head dello stack per puntare al nuovo nodo. In P-Like: 

    

    

    
In linguaggio C:

    

    

    void push(NodoStack **head, int val) {
  NodoStack *new_node = malloc(sizeof(NodoStack));
  if (new_node != NULL) {
    new_node->info = val;
    new_node->link = *head
    *head = new_node;
  }
}

    

    

    

    3. 

  3. Pop
    

    

    
In P-Like:

    

    

    

    

    
In linguaggio C:

    

    

    int pop(NodoStack **head) {
// Stack vuoto
  if (*head == NULL) return -1;
  NodoStack *temp = *head;
  int val = temp->info;
  *head = temp->link;
  free(temp);
  return val;
}

    

    

    

    4. 









3.2. Linked List





Una linked list è una struttura dati lineare composta da una sequenza di nodi. Ogni nodo contiene due elementi:



    

  1. Un campo info che contiene il dato memorizzato
    2. 

  2. Un campo link che punta al prossimo nodo della lista
    3. 





La lista viene definita tramite un puntatore alla testa (head)







3.2.1. Operazioni






    

  1. Dichiarazione
    

    

    
In P-Like:

    

    

    Type list_pointer : *nodo_lista
nodo_lista : record
    info: ...
    link: list_pointer
end
var head: list_pointer

    

    

    
In linguaggio C:

    

    

      typedef struct nodo_lista {
    int info;
    struct nodo_lista *link;
} NodoLista;
NodoLista *head = NULL; // Lista vuota

    

    

    

    2. 

  2. Creazione di un nodo
    

    

    
In linguaggio C:

    

    

    NodoLista *creaNodo(int valore) {
 NodoLista *nuovoNodo = (NodoLista *)malloc(sizeof(NodoLista));
 if (nuovoNodo != NULL) {
   nuovoNodo->info = valore;
   // Nessun nodo successivo
   nuovoNodo->link = NULL;
 }
 return nuovoNodo;
}

    

    

    

    3. 

  3. Inserimento
    

      

    1. Ordinato
      

      

      
In P-Like:

      

      

      Begin list_ordered_insert
  {Inserimento del nuovo nodo}
  var: new_node, previous, temp: list_pointer

  {Allocazione spazio per il nuovo nodo}
  new_node := allocate()
  new_node.info := elemento

  if head = NULL then
    {Caso in cui la lista è vuota}
    new_node.link := NULL
    head := new_node
  else
    {Ricerca della posizione di inserimento}
    temp := head
    previous := NULL
    while (temp != NULL) AND (temp.info < elemento) do
      previous := temp
      temp := temp.link
    end while

    if previous = NULL then
      {Inserimento in testa}
      new_node.link := head
      head := new_node
    else
      {Inserimento dopo 'previous'}
      new_node.link := previous.link
      previous.link := new_node
    end if
  end if
End list_ordered_insert

      

      

      
In linguaggio C:

      

      

      void list_ordered_insert(NodoLista **head, int elemento) {
  // Allocazione spazio per il nuovo nodo
  NodoLista *new_node = malloc(sizeof(NodoLista));
  if (new_node == NULL) {
    printf("Errore di allocazione memoria\n");
    return;
  }
  new_node->info = elemento; // Assegna valore
  // Ricerca della posizione di inserimento
  NodoLista *temp = *head, *previous = NULL;
  while (temp != NULL && temp->info < elemento) {
    previous = temp;
    temp = temp->link;
  }

// Inserimento del nuovo nodo
if (previous == NULL) {
  // Inserimento in testa
  new_node->link = *head;
  *head = new_node;
 } else {
  // Inserimento tra previous e temp
  new_node->link = previous->link;
  previous->link = new_node;
 }

      

      

      

      2. 

    2. Ordinato Ricorsivo
      

      

      
In P-Like:

      

      

      procedure recursive_ordered_insert(head, new_node)
if (new_node = NULL) then
   return // Nessun nodo da inserire
   endif
   if (head = NULL) then
          new_node.link := head
          head := new_node
   else
          if (new_node.key < head.key) then
             new_node.link := head
             head := new_node
          else
             recursive_ordered_insert(head.link, new_node)
             endif
             endif
end recursive_ordered_insert

      

      

      
In linguaggio C:

      

      

      void recursive_ordered_insert(NodoLista **head, NodoLista *new_node) {
  if (new_node == NULL) {
    // Nodo non valido
    return;
  }
}
if (*head == NULL || new_node->key < (*head)->key) {
  new_node->link = *head;
  *head = new_node;
 } else {
  recursive_ordered_insert(&((*head)->link), new_node);
 }

      

      

      

      3. 

    3. In coda
      

      

      
In P-Like:

      

      

       procedure inserimento_in_coda(head, new_node)
 var: head, current, new_node: list_pointer

 begin
    current := head

    if current = NULL then
       current := new_node
    else
       while (current.next != NULL) do
          current := current.next
       end while

    current.next := new_node

    end if
end

      

      

      

      4. 

    4. In Coda Ricorsivo
      

      

      
In P-Like:

      

      

       procedure inserimento_in_coda(head, new_node)
 var: head, current, new_node: list_pointer

  begin
   current := head
   // Caso base
   if current = NULL then
      current := new_node
   else
      // Caso ricorsivo
      if (current.next != NULL) do
         inserimento_in_coda(current.next, new_node)
      end if
   end if
end

      

      

      

      5. 

    5. Tra due nodi
      6. 

    

    4. 

  4. Eliminazione
    

      

    1. In testa
      2. 

    2. In coda
      3. 

    3. Tra due nodi
      4. 

    

    5. 

  5. Visualizzazione
    

    

    
In P-Like:

    

    

    procedure list_visualize(head)
first := head
while first != NULL do
   print first.info
   first := first.link
end while
end list_visualize

    

    

    
In linguaggio C:

    

    

    void list_visualize(NodoLista *head) {
  NodoLista *current = head;
  while (current != NULL) {
    printf("%d -> ", current->info);
    current = current->link;
  }
  printf("NULL\n");
}

    

    

    

    6. 

  6. Visualizzazione Ricorsiva
    

    

    
In P-Like:

    

    

    procedure list_visualize_ricorsiva(head_list)
if head_list != NULL then
   print head_list.info
   list_visualize_ricorsiva(head_list.link)
else
   // Fine della lista
   endif
end list_visualize_ricorsiva

    

    

    
In linguaggio C:

    

    

    void list_visualize_ric(NodoLista *head) {
  if (head != NULL) {
    printf("%d -> ", head->info);
    list_visualize_ric(head->link);
  } else {
    printf("NULL\n");
  }
}

    

    

    

    7. 









3.3. Pila






3.4. Coda








4. Ricorsione






5. Complessità Computazionale








Date: 2025-01-09 Thu 00:00


Author: Gianmarco


Created: 2025-01-17 Fri 00:27


Validate