#c #algorithms

algorithms.md

• Classics
  • factorial and fibonacci (both with loop and recursion)
  • Ackermann Function
• Sort
  • Bubble sort
  • Insertion sort
  • Selection sort
  • Merge sort

Classics

factorial and fibonacci (both with loop and recursion)

#include <stdio.h>
#include <stdlib.h>

void printArr(int arr[], int size);

// 'int *arr[howMany]' won't work because
// cannot declare a static array with variable size
// 'howMany' must be a constant; or use malloc
int *fibr(int howMany); // recursion
int *fibl(int howMany); // loop

int factorialr(int n); // recursion
int factoriall(int n); // loop

int main(void) {
  int *fr = fibr(15);
  printArr(fr, 15);

  int *fl = fibl(15);
  printArr(fl, 15);

  printf("\n");

  int facr = factorialr(5);
  printf("%d\n", facr);

  int facl = factoriall(5);
  printf("%d\n", facl);
}

void printArr(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }

  printf("\n");
}

int *fibr(int howMany) {
  static int *arr;
  arr  = (int*) malloc(howMany * sizeof(int));

  for (int i = 0; i < howMany; i++) {
    if (i == 0 || i == 1) {
      arr[i] = 1;
    } else {
      arr[i] = arr[i - 2] + arr[i - 1];
    }
  }

  return arr;
}

int *fibl(int howMany) {
  static int *arr;
  arr = (int*) malloc(howMany * sizeof(int));

  for (int i = 0; i < howMany; i++) {
    if (i == 0 || i == 1) {
      arr[i] = 1;
    } else {
      arr[i] = arr[i - 2] + arr[i - 1];
    }
  }

  return arr;
}

int factorialr(int n) {
  if (n < 2) {
    return 1;
  } else {
    return n * factorialr(n - 1);
  }
}

int factoriall(int n) {
  int fact = 1;

  for (int i = 2; i <= n; i++) {
    fact *= i;
  }

  return fact;
}

Ackermann Function

#include <stdio.h>

int ack(int m, int n);

int main(void) {
  int a = ack(3, 5);
  printf("%d\n", a);
}

int ack(int m, int n) {
  if (m == 0) {
    return n + 1;
  } else if (m > 0 && n == 0) {
    return ack(m - 1, 1);
  } else { // else if (m > 0 && n > 0)
    return ack(m - 1, ack(m, n - 1));
  }
}

Sort

Bubble sort

#include <stdio.h>

void printArray(int arr[], int arrLength);
void bubbleSort(int arr[], int arrLength);

int main(void) {
  int x[] = { 5, 4, 3, 2, 1 };
  int arrLength = sizeof(x)/sizeof(x[0]);

  bubbleSort(x, arrLength);
  printArray(x, arrLength);
}

void printArray(int arr[], int arrLength) {
    printf("Array: ");

    for (int i = 0; i < arrLength; i++) {
        printf("%i", arr[i]);

        // add space after all, except last
        if (i < arrLength - 1) {
          printf(" ");
        }
    }

    printf(".\n");
}

void bubbleSort(int arr[], int arrLength) {
  int lastIndex = arrLength - 1;

  // anything after 'i' is already sorted
  // except first element right after it,
  // this one will be compared with the lastIndex
  for (int i = lastIndex; i >= 0; i--) {
    
    for (int j = 0; j < i; j++) {
      int current = arr[j];
      int next = arr[j + 1];
      
      // if elements are out of order, swap them
      if (current > next) {
        arr[j] = next;
        arr[j + 1] = current;
      }
    }
  }
}

Insertion sort

#include <stdio.h>

void printArray(int arr[], int arrLength);
void arrSplice(int arr[], int oldIndex, int newIndex);
void insertionSort(int arr[], int arrLength);

int main(void) {
  int x[] = { 5, 4, 3, 2, 1 };
  int arrLength = sizeof(x)/sizeof(x[0]);

  insertionSort(x, arrLength);
  printArray(x, arrLength);
}

void printArray(int arr[], int arrLength) {
    printf("Array: ");

    for (int i = 0; i < arrLength; i++) {
        printf("%i", arr[i]);

        // add space after all, except last
        if (i < arrLength - 1) {
          printf(" ");
        }
    }

    printf(".\n");
}

void arrSplice(int arr[], int oldIndex, int newIndex) {
  // number at oldIndex will be placed in the newIndex index
  // and everything from the newIndex until right before the oldIndex position
  // will be move one index to the right each

  int sorting = arr[oldIndex];

  for (int i = oldIndex - 1; i >= newIndex; i--) {
    arr[i + 1] = arr[i];
  }

  arr[newIndex] = sorting;
}

void insertionSort(int arr[], int arrLength) {
  for (int i = 0; i < arrLength; i++) {
    // current number being sorted
    int sorting = arr[i];

    // compare 'sorting' with every number of the sorted part
    // until a larger number is found or until the end of the loop
    // if no larger number is founded
    // 'sorting' is already in the right place
    for (int j = 0; j < i; j++) {
      // if a larger number than 'sorting' is found
      // 'sorting' will be inserted right before it
      if (sorting < arr[j]) {
        arrSplice(arr, i, j);
        break;
      }
    }
  }
}

Selection sort

#include <stdio.h>

void printArray(int arr[], int arrLength);
void selectionSort(int arr[], int arrLength);

int main(void) {
  int x[] = { 5, 4, 3, 2, 1 };
  int arrLength = sizeof(x)/sizeof(x[0]);

  selectionSort(x, arrLength);
  printArray(x, arrLength);
}

void printArray(int arr[], int arrLength) {
    printf("Array: ");

    for (int i = 0; i < arrLength; i++) {
        printf("%i", arr[i]);

        // add space after all, except last
        if (i < arrLength - 1) {
          printf(" ");
        }
    }

    printf(".\n");
}

void selectionSort(int arr[], int arrLength) {
  // anything before 'i'
  // is considered the sorted part
  for (int i = 0; i < arrLength; i++) {
    // find the smallest number in the unsorted part
    int smallestIndex = i;
    int smallestValue = arr[i];
    for (int j = i + 1; j < arrLength; j++) {
      if (arr[j] < smallestValue) {
        smallestIndex = j;
        smallestValue = arr[j];
      }
    }

    // swap the smallest number in the unsorted part
    // with the first number in the unsorted part
    arr[smallestIndex] = arr[i];
    arr[i] = smallestValue;
  }
}

Merge sort

#include <stdio.h>
#include <math.h>

void printArr(int arr[], int arrLength);
void mergeSort(int arr[], int firstIndex, int lastIndex);
void mergeSortParts(int arr[], int firstIndex, int middleIndex, int lastIndex);

int main(void) {
  int arr[] = { 4, 6, 2, 1, 3, 5 };
  int len = sizeof(arr) / sizeof(arr[0]);

  printArr(arr, len);
  mergeSort(arr, 0, len - 1);
  printArr(arr, len);
}


void printArr(int arr[], int arrLength) {
    printf("Array: ");

    for (int i = 0; i < arrLength; i++) {
        printf("%i", arr[i]);

        // add space after all, except last
        if (i < arrLength - 1) {
          printf(" ");
        }
    }

    printf(".\n");
}

void mergeSortParts(int arr[], int firstIndex, int middleIndex, int lastIndex) {

  int totalLen = lastIndex - firstIndex + 1;
  int tempArr[totalLen];

  // range: firstIndex to middleIndex
  int curLeft = firstIndex;
  // range: middleIndex + 1 to lastIndex
  int curRight = middleIndex + 1;

  for (int i = 0; i < totalLen; i++) {

    // if all itens in the left part
    // were already placed into 'tempArr'
    // catch next at the right part
    if (curLeft > middleIndex) {
      tempArr[i] = arr[curRight];
      curRight = curRight + 1;

    // if all itens in the right part
    // were already placed into 'tempArr'
    // catch next at the left part
    } else if (curRight > lastIndex) {
      tempArr[i] = arr[curLeft];
      curLeft = curLeft + 1;
    } else {

      // otherwise, if both parts still have available items
      // compare them and get smaller
      if (arr[curLeft] < arr[curRight]) {
        tempArr[i] = arr[curLeft];
        curLeft = curLeft + 1;
      } else {
        tempArr[i] = arr[curRight];
        curRight = curRight + 1;
      }
    }
  }

  // copy the tempArr to its respective position at arr
  for (int i = 0; i < totalLen; i++) {
    arr[firstIndex + i] = tempArr[i];
  }
}

void mergeSort(int arr[], int firstIndex, int lastIndex) {
  
  // recursion
  // if current subarray is not of length 1,
  // i.e. its first element and last element doesn't have the same index,
  // split array in half, and call this function with each half
  if (firstIndex != lastIndex) {
    int middleIndex = floor(firstIndex + (lastIndex - firstIndex) / 2);
    
    mergeSort(arr, firstIndex, middleIndex);
    mergeSort(arr, middleIndex + 1, lastIndex);
    
    mergeSortParts(arr, firstIndex, middleIndex, lastIndex);
  }
}