Algorithms: Binary Search, Hashing, Insertion, QuickSort, ShellSort

Posted on Feb 28, 2025 in Service Computing

Binary Search Algorithms in C#

Recursive Binary Search

Recursive Binary Search

public TipoElem Buscar(ArrayList x, TipoElem key, int low, int hi)
{
    if (low <= hi)
    {
        int mid = (low + hi) / 2;
        if (key == (TipoElem)x[mid])
            return (TipoElem)x[mid];
        else if (key < (TipoElem)x[mid])
            return Buscar(x, key, low, mid - 1);
        else
            return Buscar(x, key, mid + 1, hi);
    }
    else
        return new TipoElem("NO SE ENCONTRO");
}

Iterative Binary Search

Iterative Binary Search

public TipoElem Buscar(ArrayList x, TipoElem key, int low, int hi)
{
    int mid;
    while (low <= hi)
    {
        mid = (low + hi) / 2;
        if (key == (TipoElem)x[mid])
            return (TipoElem)x[mid];
        if (key < (TipoElem)x[mid])
            hi = mid - 1;
        else
            low = mid + 1;
    }
    return new TipoElem("NO SE ENCONTRO");
}

IBusqueda Interface

interface IBusqueda

{
    TipoElem Buscar(ArrayList x, TipoElem key, int low, int hi);
}

Hashing Algorithm in C#

Hashing Search

public TipoElem Buscar(Lista[] tabla, TipoElem key)
{
    char c = key.Nombre[0];
    int indice = Convert.ToInt32(Char.ToUpper(c)) - 65;
    Nodo p = tabla[indice].Cab;
    while (p != null)
        if (p.Info == key)
            return p.Info;
        else
            p = p.Sig;
    return new TipoElem("NO SE ENCONTRO");
}

Hashing Class

class Hashing : IOrdenacion

{
    Lista[] tablaHash;

    public Lista[] Tabla
    {
        get { return tablaHash; }
    }

    public void Ordenar(ArrayList x, int lb, int ub)
    {
        tablaHash = new Lista[26];
        for (int i = 0; i < tablaHash.Length; i++)
            tablaHash[i] = new Lista();
        for (int i = 0; i < ub + 1; i++)
        {
            char c = ((TipoElem)x[i]).Nombre[0];
            int indice = Convert.ToInt32(Char.ToUpper(c)) - 65;
            tablaHash[indice].InsOrden((TipoElem)x[i]);
        }
        int j = 0;
        for (int i = 0; i < tablaHash.Length; i++)
        {
            Nodo p = tablaHash[i].Cab;
            while (p != null)
            {
                x[j++] = p.Info;
                p = p.Sig;
            }
        }
    }
}

Insertion Sort Algorithm in C#

class InsertionSort : IOrdenacion

{
    public void Ordenar(ArrayList x, int lb, int ub)
    {
        int i, k;
        TipoElem y;
        for (k = 1; k < ub + 1; k++)
        {
            y = (TipoElem)x[k];
            for (i = k - 1; i >= 0 && y < (TipoElem)x[i]; i--)
                x[i + 1] = x[i];
            x[i + 1] = y;
        }
    }
}

QuickSort Algorithm in C#

QuickSort

public void Ordenar(ArrayList x, int lb, int ub)
{
    if (lb >= ub)
        return;
    int j = 0;
    Partition(x, lb, ub, ref j);
    Ordenar(x, lb, j - 1);
    Ordenar(x, j + 1, ub);
}

public void Partition(ArrayList x, int lb, int ub, ref int j)
{
    int down, up;
    TipoElem temp, a;
    a = (TipoElem)x[lb];
    up = ub;
    down = lb;
    while (down < up)
    {
        while ((TipoElem)x[down] <= a && down < ub)
            down++;
        while ((TipoElem)x[up] > a)
            up--;
        if (down < up)
        {
            temp = (TipoElem)x[down];
            x[down] = x[up];
            x[up] = temp;
        }
    }
    x[lb] = x[up];
    x[up] = a;
    j = up;
}

ShellSort Algorithm in C#

class ShellSort : IOrdenacion

{
    public void Ordenar(ArrayList x, int lb, int ub)
    {
        int[] increments = { 5, 3, 1 };
        int numIncs = 3;
        int j, k, span, incr;
        TipoElem y;
        for (incr = 0; incr < numIncs; incr++)
        {
            span = increments[incr];
            for (j = span; j < ub + 1; j++)
            {
                y = (TipoElem)x[j];
                for (k = j - span; k >= 0 && y < (TipoElem)x[k]; k -= span)
                    x[k + span] = x[k];
                x[k + span] = y;
            }
        }
    }
}

Node and List Classes in C#

class Nodo

{
    TipoElem _info;
    Nodo _sig;

    public Nodo(TipoElem oElem)
    {
        _info = oElem;
    }

    public Nodo Sig
    {
        get { return _sig; }
        set { _sig = value; }
    }

    public TipoElem Info
    {
        get { return _info; }
        set { _info = value; }
    }
}

class Lista

{
    Nodo _cab;
    int _noNodos;

    public Lista()
    {
        _cab = null;
        _noNodos = 0;
    }

    public void InsOrden(TipoElem oElem)
    {
        Nodo r = new Nodo(oElem);
        Nodo p = _cab;
        Nodo q = null;
        while (p != null && oElem > p.Info)
        {
            q = p;
            p = p.Sig;
        }
        if (q == null)
        {
            r.Sig = _cab;
            _cab = r;
        }
        else
        {
            q.Sig = r;
            r.Sig = p;
        }
        _noNodos++;
    }

    public bool Empty
    {
        get { return _cab == null ? true : false; }
    }

    public int NoNodos
    {
        get { return _noNodos; }
        set { _noNodos = value; }
    }

    public Nodo Cab
    {
        get { return _cab; }
        set { _cab = value; }
    }

    public Nodo Busq(TipoElem oElem)
    {
        Nodo p = _cab;
        while (p != null)
            if (p.Info == oElem)
                return p;
            else
                p = p.Sig;
        return p;
    }
}