Algoritmos de busca e ordenação implementados no OCTAVE/MATLAB

binarysearch.m

function ret = binarysearch(el,vet)
  
  inf = 1;
  sup = numel(vet);
  
  while(inf <= sup)
    meio = idivide(sup + inf, 2);
    if(el == vet(1, meio))
      ret = meio;
      return;
    end
    if (el < vet(1, meio))
      sup = meio-1;
    else
      inf = meio+1;
    end
  end
  
  ret = -1;
  return;
  
  
end

countingsort.m

function sx = countingsort(x,r)
%--------------------------------------------------------------------------
% Syntax:       sx = countingsort(x,r);
%               
% Inputs:       x is a vector of length n containing integers in the range
%               [1,...,r]
%               
%               r is an upper bound on max(x)
%               
% Outputs:      sx is the sorted (ascending) version of x
%               
% Description:  This function sorts the input array x in ascending order
%               using the counting sort algorithm
%               
% Complexity:   O(n)    best-case performance
%               O(n)    average-case performance
%               O(n)    worst-case performance
%               O(n)    auxiliary space
%               
% Author:       Brian Moore
%               [email protected]
%               
% Date:         January 5, 2014
%--------------------------------------------------------------------------

% Compute histogram
n = numel(x);
C = zeros(r,1);
for j = 1:n
    C(x(j)) = C(x(j)) + 1;
end

% Convert to cumulative values
for i = 2:r
    C(i) = C(i) + C(i - 1);
end

% Sort the array
sx = nan(n,1);
for j = n:-1:1
    sx(C(x(j))) = x(j);
    C(x(j)) = C(x(j)) - 1;
end

end

insertionsort.m

global list;
function list = insertionSort(list)
 
    for i = (2:numel(list))
 
        value = list(i);
        j = i - 1;
 
        while (j >= 1) && (list(j) > value)
            list(j+1) = list(j);
            j = j-1;
        end
 
        list(j+1) = value;
 
    end %for
end %insertionSort

interpolationsearch.m

function ret = interpolationsearch(el,vet)
  
  size = numel(vet);  
  low = 1;
  high = size;
  
  while(vet(1,high) != vet(1, low) && el >= vet(1, low) && el <= vet(1, high))
    
    mid = low + ((el - vet(1, low)) * (high - low) / (vet(1, high) - vet(1, low)));
    
    if(vet(1, mid) < el)
      low = mid + 1;
    elseif(el < vet(1, mid))
      high = mid - 1;
    else
      ret = mid;
      return;
    end
    
  end
  
  if(el == vet(1, low))
    ret = low;
    return;
  else
    ret = -1;
    return;
  end
  
end

mergesort.m

global list;
function list = mergeSort(list)
 
    if numel(list) <= 1
        return;
    else
        middle = ceil(numel(list) / 2);
        left = list(1:middle);
        right = list(middle+1:end);
 
        left = mergeSort(left);
        right = mergeSort(right);
 
        if left(end) <= right(1)
            list = [left right];
            return
        end
 
        %merge(left,right)
        counter = 1;
        while (numel(left) > 0) && (numel(right) > 0)
            if(left(1) <= right(1))
                list(counter) = left(1);
                left(1) = [];
            else
                list(counter) = right(1);
                right(1) = [];
            end           
            counter = counter + 1;   
        end
 
        if numel(left) > 0
            list(counter:end) = left;
        elseif numel(right) > 0
            list(counter:end) = right;
        end
        %end merge        
    endif %if
endfunction %mergeSort

selectionsort.m

function x = selectionsort(x)
%--------------------------------------------------------------------------
% Syntax:       sx = selectionsort(x);
%               
% Inputs:       x is a vector of length n
%               
% Outputs:      sx is the sorted (ascending) version of x
%               
% Description:  This function sorts the input array x in ascending order
%               using the selection sort algorithm
%               
% Complexity:   O(n^2)    best-case performance
%               O(n^2)    average-case performance
%               O(n^2)    worst-case performance
%               O(1)      auxiliary space
%               
% Author:       Brian Moore
%               [email protected]
%               
% Date:         January 5, 2014
%--------------------------------------------------------------------------

% Seletion sort
n = length(x);
for j = 1:(n - 1)
    % Find jth smallest element
    imin = j;
    for i = (j + 1):n
        if (x(i) < x(imin))
            imin = i;
        end
    end
    
    % Put jth smallest element in place
    if (imin ~= j)
        x = swap(x,imin,j);
    end
end

end

function x = swap(x,i,j)
% Swap x(i) and x(j)
% Note: In practice, x xhould be passed by reference

val = x(i);
x(i) = x(j);
x(j) = val;

end

sequencialsearch.m

function ret = sequencialsearch(el,vet)
  
  qtdVet = numel(vet);
  
  for i = 1:qtdVet
    if (vet(1, i) == el)
      ret = i;
      return;
    end
  end
  
  ret = -1;
  return;
  
end

stringmatch.m

function [tempo, posicao] = localizarPalavra(endereco, palavra)
  
  #ABRINDO O ARQUIVO PARA LEITURA
  arquivo = fopen(endereco, 'r');
  texto = fgets(arquivo);
  
  #PEGANDO A QUANTIDADE DE CARACTERES NA LINHA
  qntTxt = length(texto);
  
  #OBTENDO O TAMANHO DA PALAVRA PROCURADA
  qntPl = length(palavra);
  
  #INICIANDO VARIAVEL RESULTADO
  posicao = -1;
  
  start = tic();
  
  for i=1:((qntTxt-qntPl)+1)

    q = 1;
    while((q <= qntPl) && (texto(i+(q-1)) == palavra(q)))    
      q++;
    endwhile
   
    if((q-1) == qntPl)
      posicao = i;
      break;
    endif
   
  endfor  
  
  tempo = toc(start);
  
endfunction