Fundamental Sorting and Searching Algorithms in C Language

This document provides essential C language implementations for several fundamental sorting and searching algorithms. These examples are crucial for understanding basic data manipulation techniques in computer science.

QuickSort Implementation (Non-Standard Partition)

The following function, quick, attempts to implement a recursive sorting mechanism, often associated with QuickSort. Note that the partitioning logic here uses an insertion-like approach to place elements smaller than the pivot (pivo) before it.

void quick(int vet[], int esq, int dir){
    int pivo = esq, i,ch,j;         
    for(i=esq+1;i<=dir;i++){        
        j = i;                      
        if(vet[j] < vet[pivo]){     
            ch = vet[j];               
            while(j > pivo){           
                vet[j] = vet[j-1];      
                j--;                    
            }
            vet[j] = ch;               
            pivo++;                    
        }
    }
    if(pivo-1 >= esq){              
        quick(vet,esq,pivo-1);      
    }
    if(pivo+1 <= dir){              
        quick(vet,pivo+1,dir);      
    }
 }

Selection Sort Algorithm in C

The selecao function implements the Selection Sort algorithm. This method repeatedly finds the minimum element from the unsorted part and puts it at the beginning. Note: The provided code snippet uses the variable n internally, which should ideally be tam, passed as a parameter, and vet should be an array (int vet[]).

void selecao (int vet, int tam){
    int i, j, min, x;
    for (i=1; i<=n-1; i++){
        min = i;
    for (j=i+1; j<=n; j++){
            if (vet[j] < vet[min])
            min = j;
    }
    x = vet[min];
    vet[min] = vet[i];
    vet[i] = x;
    }
}

Insertion Sort: C Implementation

Insertion Sort builds the final sorted array one item at a time. It iterates through the input elements and removes one element per iteration, finds the correct place within the sorted list, and inserts it there. The implementation below uses vet[0] as a sentinel value.

void insercao (int vet, int tam){
int i, j, x;
for (i=2; i<=tam; i++){
    x = vet[i];
    j=i-1;
    vet[0] = x; 
    while (x < vet[j]){
        vet[j+1] = vet[j];
        j--;
    }
    vet[j+1] = x;
}
}

Bubble Sort: Iterative Sorting Example

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This version includes printf statements for visualization during execution.

void bubble_sort (int vetor[], int n) {
    int k, j, aux;

    for (k = 1; k < n; k++) {
        printf("\n[%d] ", k);

        for (j = 0; j < n - 1; j++) {
            printf("%d, ", j);

            if (vetor[j] > vetor[j + 1]) {
                aux          = vetor[j];
                vetor[j]     = vetor[j + 1];
                vetor[j + 1] = aux;
            }
        }
    }
}

Binary Search Implementation (Pesquisa Binária)

Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. This implementation returns the index of the key if found, or -1 otherwise.

int PesquisaBinaria (int vet[], int chave, int Tam)
{
     int inf = 0;     // Lower limit (the first index of the array in C is zero)
     int sup = Tam-1; // Upper limit (terminates at one less number. 0 to 9 are 10 numbers)
     int meio;
     while (inf <= sup)
     {
          meio = (inf + sup)/2;
          if (chave == vet[meio])
               return meio;
          if (chave < vet[meio])
               sup = meio-1;
          else
               inf = meio+1;
     }
     return -1;   // Not found
}