Array Algorithms

Now that you’ve learned how to pass arrays into functions, let’s explore some common algorithms that may be useful for this course. Luckily since Java and C++ share similar syntax, many of the algorithms you encountered in CSCE146 can be easily transferred over to C++ with minor adjustments 🚀.

To keep our code organized, lets create a massive project that holds all our array algorithms. The project will be like a code bank where we can copy and paste array algorithms to other projects as we need them.

Project Setup

If you have something similar to the suggested file structure from earlier in the tutorial, then create a folder called Arrays or Array Algorithms where your Tutorials or Practice code are located. I’ve gone ahead and listed the filenames that we will be using:

• DirectoryCSCE240

  • DirectoryAssignments

    • …
  • DirectoryLectures

    • …
  • DirectoryTest

    • …
  • DirectoryTutorials

    • DirectoryArrays

      • algorithms.cc
      • algorithms.h
      • driver.cc
      • makefile
    • …

Since we know the names of the files for the project, we can go ahead and write the scripts to compile and link everything in our makefile:

makefile

# Built-in variables:
# $< = the first prerequisite
# $^ = all prerequisites
# $@ = the target

compiler = g++
flags = -Wall -std=c++17
compile = $(compiler) -c
link = $(compiler) $(flags)

algorithms.o : algorithms.cc algorithms.h
    $(compile) $(flags) $<

driver.o : driver.cc algorithms.h
    $(compile) $(flags) $<

driver : driver.o algorithms.o
    $(link) $^
    ./a.out

clean :
    rm *.o a.out

Searching

In your header file, lets create a couple of prototypes for different searching algorithms. This is the only time I’ll show the full header file. Future additions will only show what code to add:

algorithms.h

// Copyright 2024 CSCE240

#ifndef ALGORITHMS_H_
#define ALGORITHMS_H_

/* Searching Algorithms */

// Linear

int IndexOf(const int[], int, int);
int IndexOf(const char[], char);  // char overload

bool Contains(const int[], int, int);
bool Contains(const char[], char);  // char overload

// Binary

bool BinaryContains(const int[], int, int);
bool BinaryContains(const int[], int, int, int);  //  recursive helper function

#endif

Now move over to your source file, algorithms.cc, to write the implementations.

Linear Search

We’ll first write the implementation for the linear search functions since they are pretty straight forward. Starting from the first index to the last index of the array, if the current value matches a target, stop the loop and return something.

IndexOf

IndexOf is useful when you need to know where an element is located. We return an integer which represents an index in the array or we return -1 which symbolizes that the target was not found.

Numeric Function

This is the only time I’ll show the complete source file, future snippets will only show the new code to add:

algorithms.cc

// Copyright 2024 CSCE240

#include "algorithms.h"

#include <iostream>

using std::cout;
using std::endl;

/* Searching Algorithms */

// Linear

int IndexOf(const int array[], int size, int target) {
  for (int i = 0; i < size; ++i) {
    if (array[i] == target) return i;
  }
  return -1;
}

Char Function

You may have noticed from the prototype in the header file that we didn’t require an integer for the size. This is to show how you can use a different approach with char arrays. Instead of iterating for a set number of times, you can use the null terminator \0 as a deciding factor for when to end iteration.

algorithms.cc

//  Char Overload
int IndexOf(const char array[], char target) {
  int i = 0;
  while (array[i] != '\0') {
    if (array[i] == target) return i;
    ++i;
  }
  return -1;
}

Test

We’ve completed the implementation of the IndexOf functions so we can now move to driver.cc to test these functions. This will be the only time the complete driver will be shown.

Driver

driver.cc

// Copyright 2024 CSCE240

#include <iostream>

#include "algorithms.h"
#include "namespaces.h"

using std::cout;
using std::endl;

int main() {
  const int kSize = 5;
  int arr1[kSize] = {2, 4, 6, 8, 10};
  cout << (IndexOf(arr1, kSize, 6) == 2) << endl;
  cout << (IndexOf(arr1, kSize, 5) == -1) << endl;
  char arr2[kSize] = "code";
  cout << (IndexOf(arr2, 'd') == 2) << endl;
  cout << (IndexOf(arr2, 'f') == -1) << endl;

  return 0;
}

Terminal

make driver
g++ -c -Wall -std=c++17 driver.cc
g++ -c -Wall -std=c++17 algorithms.cc
g++ -Wall -std=c++17 driver.o algorithms.o
./a.out
1
1
1
1

Now that we’ve verified that the functions are working correctly, we can comment out the cout lines so that we are only getting output for the functions we are testing instead of everything.

Contains

Contains can be used when you need to know if an element exists in an array. While iterating we return true if the target element is found. Otherwise we return false at the end of the function.

Numeric Function

Move back to your source file, algorithms.cc, and add the implementation for the Contains function:

algorithms.cc

bool Contains(const int arr[], int size, int target) {
  for (int i = 0; i < size; ++i) {
    if (arr[i] == target) return true;
  }
  return false;
}

Char Function

Again we’ll use the null terminator approach with the overloaded char function:

algorithms.cc

bool Contains(const char array[], char target) {
  int i = 0;
  while (array[i] != '\0') {
    if (array[i] == target) return true;
    ++i;
  }
  return false;
}

Test

We can use the previously created arrays to also test the Contains functions:

Driver

driver.cc

const int kSize = 5;
int arr1[kSize] = {2, 4, 6, 8, 10};
cout << (Contains(arr1, kSize, 6) == true) << endl;
cout << (Contains(arr1, kSize, 5) == false) << endl;
char arr2[kSize] = "code";
cout << (Contains(arr2, 'd') == true) << endl;
cout << (Contains(arr2, 'f') == false) << endl;

Terminal

make driver
g++ -c -Wall -std=c++17 driver.cc
g++ -c -Wall -std=c++17 algorithms.cc
g++ -Wall -std=c++17 driver.o algorithms.o
./a.out
1
1
1
1

Now that we know the functions work, we can also comment out every line utilizing cout and arr2.

Binary Search

Binary Search is a faster approach to searching than the linear way as it looks to divide & conquer an array by halving it into smaller relevant sections. If you need a refresher, you can view this quick video by Fireship.

Note

A caveat with Binary Search is that though it is a much quicker searching algorithm, it requires an array to be sorted.

I provided the Java version, which should be very similar to the code found in CSCE146, next to the C++ version along with marks to show which lines have been changed. Add the C++ implementation to the source file:

Java

SearchAlgorithms.java

static boolean BinaryContains(int[] array, int target) {
  return BinaryContains(array, target, 0, array.length - 1);
}

//  Recursive Helper Function
static boolean BinaryContains(
  int[] array,
  int target,
  int startIndex,
  int endIndex
) {
  if (startIndex > endIndex) return false;

  // calculate the midpoint
  int mid = (startIndex + endIndex) / 2;

  if (array[mid] == target) return true;
  // check to the left of the midpoint
  else if (array[mid] > target) return BinaryContains(
    array,
    target,
    0,
    mid - 1
  );
  // check to the right of the midpoint
  else return BinaryContains(array, target, mid + 1, endIndex);
}

C++

algorithms.cc

bool BinaryContains(const int array[], int size, int target) {
  return BinaryContains(array, target, 0, size - 1);
}

bool BinaryContains(const int array[], int target, int start_index,
                    int end_index) {
  if (start_index > end_index) return false;

  // calculate the midpoint
  int mid = (start_index + end_index) / 2;

  if (array[mid] == target) return true;
  // check to the left of the midpoint
  else if (array[mid] > target)
    return BinaryContains(array, target, 0, mid - 1);
  // check to the right of the midpoint
  else
    return BinaryContains(array, target, mid + 1, end_index);
}

Note

Aside from language syntax, just two lines changed 🥳! The recursive helper function requires an ending index parameter. Since we don’t have the .length property in C++, we require the size of the array and subtract 1 from it.

Test

Now to test our new function in the driver. Since arr1 is already sorted, we can use it as a testing parameter:

Driver

drive.cc

int arr1[kSize] = {2, 4, 6, 8, 10};
cout << (BinaryContains(arr1, kSize, 4) == true) << endl;
cout << (BinaryContains(arr1, kSize, 9) == false) << endl;

Terminal

make driver
g++ -c -Wall -std=c++17 algorithms.cc
g++ -Wall -std=c++17 driver.o algorithms.o
./a.out
1
1

Now that we’ve test all our Searching Algorithms you can comment out the cout statements, and arr1. We’ll create a new array in the next section.

Sorting

As you learned in CSCE146, many programs require you to organize data. You’ll probably get at least 1 assignment where sorting a numeric array will either make or break your program. We’ll go over four that you should be familiar with: Bubble Sort, Selection Sort, Merge Sort, and Quick Sort. For each section we’ll follow the same pattern: Declare, Implement, and Test. We’ll also look to sort our arrays using ascending order.

Utility Functions

Before getting into the Sorting Algorithms, lets create a couple of utility functions to help with implementation and testing. Most algorithms will look to swap elements in a similar way so we’ll create a Swap function. We’ll always need to print our arrays to check that our functions are working, so we’ll also create a Print function.

1. Declare

   Go to your header file algorithms.h and declare the following utility functions:

   algorithms.h

   /* Utility Algorithms */
   
   void Print(const int[], int);
   void Swap(int[], int, int);

2. Implement

   Now in our source file, algorithms.cc, add the implementation for each function:

   algorithms.cc

   void Swap(int array[], int i, int j) {
     int temp = array[i];
     array[i] = array[j];
     array[j] = temp;
   }
   
   void Print(const int array[], int size) {
     for (int i = 0; i < size; ++i) {
       cout << array[i] << endl;
     }
   }

   Note

   We’ll test these functions after we complete our first sorting algorithm.

BubbleSort

The Bubble Sort algorithm works by comparing each element in an array to the one beside it, then swapping them if they are less than the current element. You start from the front of the array and work your way to the end meaning that the last indices are sorted before the beginning indices. If you prefer a visualized explanation, you can view this short video by Boot Dev.

1. Declare

   Lets declare the BubbleSort Function in our header file first:

   algorithms.h

   /* Sorting Algorithms */
   
   void BubbleSort(int[], int);

2. Implement

   Next we define the implementation to the BubbleSort Function in the source file:

   algorithms.cc

   /* Sorting Algorithms */
   
   void BubbleSort(int array[], int size) {
     bool has_swapped = true;
   
     while (has_swapped) {
       has_swapped = false;
   
       for (int i = 0; i < size - 1; ++i) {
         if (array[i] > array[i + 1]) {
           Swap(array, i, i + 1);
           has_swapped = true;
         }
       }
       --size;
     }
   }

3. Test

   The final step is to test our functions in the driver file:

   Driver

   drive.cc

   int array[kSize] = {
         5, 7, 3, 4, 1,
   };
   BubbleSort(array, kSize);
   Print(array, kSize);

   Terminal

   make driver
   g++ -c -Wall -std=c++17 driver.cc
   g++ -c -Wall -std=c++17 algorithms.cc
   g++ -Wall -std=c++17 driver.o algorithms.o
   ./a.out
   1
   3
   4
   5
   7

SelectionSort

The Selection Sort algorithm is another one of the starter sorting algorithms. How it works is that you assume that the current indexed element contains the smallest element. You then compare the current smallest element to the rest of the elements in the array, updating the index with the smallest element as you need to.

At the end of the loop, if the current smallest or largest index has changed, then you know that a swap must be made. The difference between this and the Bubble Sort algorithm is that you first sort the beginning elements, then you sort the ending elements. If you prefer to watch a video, Michael Sambol created a short video to help explain the Selection Sort algorithm.

1. Declare

   First we’ll declare the SelectionSort function in our header file:

   algorithms.h

   void SelectionSort(int[], int);

2. Implement

   Next we’ll add the implementation in the source file:

   void SelectionSort(int array[], int size) {
     for (int i = 0; i < size - 1; ++i) {
       int smallest_index = i;
       for (int j = i + 1; j < size; ++j) {
         if (array[smallest_index] > array[j]) smallest_index = j;
       }
       if (smallest_index != i) Swap(array, i, smallest_index);
     }
   }

3. Test

   As always, lets test the function to see if it works as intended:

   Driver

   drive.cc

   int array[kSize] = {
         5, 7, 3, 4, 1,
   };
   SelectionSort(array, kSize);
   Print(array, kSize);

   Terminal

   make driver
   g++ -c -Wall -std=c++17 driver.cc
   g++ -c -Wall -std=c++17 algorithms.cc
   g++ -Wall -std=c++17 driver.o algorithms.o
   ./a.out
   1
   3
   4
   5
   7

MergeSort

The first advanced sorting algorithm learned in CSCE146 is the Merge Sorting algorithm. Merge Sort is a divide-and-conquer algorithm that splits an array into smaller subarrays, sorts each subarray, and then merges the sorted subarrays back together.

Here’s a quick video by Boot Dev if you need more of a visual explanation.

1. Declare

   Just like in CSCE146, we’ll declare the primary function to call in the main function along with a utility function that will only be called in the MergeSort function.

   algorithms.h

   void MergeSort(int[], int);
   void Merge(int[], int[], int, int[], int);

2. Implement

   Now we’ll move on to defining the implementation. Java code from CSCE146 will be provided along with a C++ version. First are the MergeSort functions:

   Java

   SortingAlgorithms.java

   static void mergeSort(int[] array) {
     // check if the array has one element
     int size = array.length;
     if (size < 2) return;
   
     // calculate middle index
     int mid = size / 2;
   
     // determine sizes of left and right sub arrays
     int leftSize = mid;
     int rightSize = size - mid;
   
     // create left and right sub arrays
     int[] left = new int[leftSize];
     int[] right = new int[rightSize];
   
     // populate left sub array
     for (int i = 0; i < mid; i++) left[i] = array[i];
   
     // populate right sub array
     for (int i = mid; i < size; i++) right[i - mid] = array[i];
   
     // recursively create smaller sub arrays
     mergeSort(left);
     mergeSort(right);
   
     // merge sub arrays
     merge(left, right, array);
   }

   C++

   algorithms.cc

   void MergeSort(int array[], int size) {
     // check if array has one element
     if (size < 2) return;
   
     // calculate mid index
     int mid = size / 2;
   
     // determine sizes of left and right subarrays
     const int kLeftSize = mid;
     const int kRightSize = size - mid;
   
     // create left and right subarrays
     int left[kLeftSize];
     int right[kRightSize];
   
     // populate left subarray
     for (int i = 0; i < mid; ++i) {
       left[i] = array[i];
     }
   
     // populate right subarray
     for (int i = mid; i < size; ++i) {
       right[i - mid] = array[i];
     }
   
     // recursively create smaller subarrays
     MergeSort(left, kLeftSize);
     MergeSort(right, kRightSize);
   
     // merge subarrays
     Merge(array, left, kLeftSize, right, kRightSize);
   }

   Next are the utility Merge functions:

   Java

   SortingAlgorithms.java

   static void merge(int[] left, int[] right, int[] array) {
     // sizes of left and right sub arrays
     int leftSize = left.length;
     int rightSize = right.length;
   
     // pointers for left, right, and merged arrays
     int i = 0; // left array index
     int j = 0; // right array index
     int k = 0; // merged array's index
   
     // merge elements into the array in sorted order
     while (i < leftSize && j < rightSize) {
       // compare elements from left and right sub arrays
       if (left[i] <= right[j]) {
         array[k] = left[i];
         i++;
         k++;
       } else {
         array[k] = right[j];
         j++;
         k++;
       }
     }
   
     // copy remaining elements from left sub array
     while (i < leftSize) {
       array[k] = left[i];
       i++;
       k++;
     }
   
     // copy remaining elements from right sub array
     while (j < rightSize) {
       array[k] = right[j];
       j++;
       k++;
     }
   }

   C++

   algorithms.cc

   void Merge(int array[], int left_array[], int left_size, int right_array[],
              int right_size) {
     int i = 0;  // left array index
     int j = 0;  // right array index
     int k = 0;  // merged array's index
   
     // merge elements into the array in sorted order
     while (i < left_size && j < right_size) {
       // compare elements from left and right subarrays
       if (left_array[i] <= right_array[j]) {
         array[k] = left_array[i];
         ++i;
         ++k;
       } else {
         array[k] = right_array[j];
         ++j;
         ++k;
       }
     }
   
     // copy remaining elements from left subarray
     while (i < left_size) {
       array[k] = left_array[i];
       ++i;
       ++k;
     }
   
     // copy remaining elements from right subarray
     while (j < right_size) {
       array[k] = right_array[j];
       ++j;
       ++k;
     }
   }

   Caution

   This implementation of MergeSort uses stack-allocated arrays (int left[] and int right[]) for simplicity and to align with the current tutorial section on arrays. While this approach is straightforward and easy to understand, it can be further optimized by using dynamic memory allocation with pointers.

   Note

   Dynamic memory allows for greater flexibility and efficiency, especially when working with large datasets, as it avoids excessive stack memory usage. In the upcoming section on pointers, we’ll revisit this algorithm to show how dynamic allocation can make the implementation more robust and scalable.

3. Test

   Finally, we replace the previous function called with the new one in the driver:

   Driver

   drive.cc

   int array[kSize] = {
         5, 7, 3, 4, 1,
   };
   MergeSort(array, kSize);
   Print(array, kSize);

   Terminal

   make driver
   g++ -c -Wall -std=c++17 driver.cc
   g++ -c -Wall -std=c++17 algorithms.cc
   g++ -Wall -std=c++17 driver.o algorithms.o
   ./a.out
   1
   3
   4
   5
   7

QuickSort

The last sorting algorithm we’ll look at is QuickSort. Quick Sort is a divide-and-conquer algorithm that selects a “pivot” element, then rearranges the array so that all elements less than the pivot are on one side, and all elements greater than the pivot are on the other. It then recursively sorts these smaller partitions, resulting in a fully sorted array with efficient average-case performance.

If you prefer a visual explanation, you can look at a short video by Computerphile

1. Declare

   Just like in CSCE146, we’ll declare a primary function to call along with two utility functions that will only be called in the primary function:

   algorithms.h

   void QuickSort(int[], int);
   void Quick(int[], int, int);
   int Partition(int[], int, int);

2. Implement

   Now we move to the source file and add the implementation. First the primary function QuickSort which consists of calling a utility function with an array, the beginning index, and the ending index as the parameters.

   The difference is the added size parameter which we need to get the last index of the array to call the utility function:

   Java

   SortingAlgorithms.java

   static void QuickSort(int[] array) {
     Quick(array, 0, array.length - 1);
   }

   C++

   algorithms.cc

   void QuickSort(int array[], int size) {
     Quick(array, 0, size - 1);
   }

   Next we define the implementation for the Quick function we just called in the primary function. There are no changes in implementation from Java to C++.

   The Quick function is the core of the QuickSort algorithm, implementing the recursive divide-and-conquer approach. It works by calling the Partition function to divide the array into two parts around a pivot element and recursively calling itself to sort the left and right partitions.

   Java

   SortingAlgorithms.java

   static void Quick(int[] array, int startIndex, int endIndex) {
     // check if array is sorted
     if (startIndex >= endIndex) return;
   
     // get the pivot element's index
     int pivot = Partition(array, startIndex, endIndex);
   
     Quick(array, startIndex, pivot - 1); // left
     Quick(array, pivot + 1, endIndex); // right
   }

   C++

   algorithms.cc

   void Quick(int array[], int start_index, int end_index) {
     // check if array is sorted
     if (start_index >= end_index) return;
   
     // get the pivot element's index
     int pivot = Partition(array, start_index, end_index);
   
     Quick(array, start_index, pivot - 1);  // left
     Quick(array, pivot + 1, end_index);    // right
   }

   The last function to implement is the utility Partition function. The Partition function rearranges the elements in the specified subarray around a pivot element. It selects the last element as the pivot and ensures that smaller elements are placed to the left and larger elements are placed to the right.

   Again, the implementation is the same between both languages:

   Java

   SortingAlgorithms.java

   static int Partition(int[] array, int startIndex, int endIndex) {
     // select the last element as the pivot
     int pivot = array[endIndex];
     int i = startIndex;
   
     // iterate and move elements smaller than the pivot to the left
     for (int j = startIndex; j <= endIndex; j++) {
       if (array[j] < pivot) {
         Swap(array, i, j);
         i++;
       }
     }
   
     // swap the pivot element with the element at index i
     Swap(array, i, endIndex);
     return i; // where the pivot is
   }

   C++

   algorithms.cc

   int Partition(int array[], int start_index, int end_index) {
     // select the last element as the pivot
     int pivot = array[end_index];
     int i = start_index;
   
     // iterate and move elements smaller than the pivot to the left
     for (int j = start_index; j <= end_index; ++j) {
       if (array[j] < pivot) {
         Swap(array, i, j);
         ++i;
       }
     }
   
     // swap the pivot element with the element at index i
     Swap(array, i, end_index);
     return i;  // where the pivot is
   }

3. Test

   Finally, we can conduct our final sorting test in the driver file:

   Driver

   drive.cc

   int array[kSize] = {
         5, 7, 3, 4, 1,
   };
   QuickSort(array, kSize);
   Print(array, kSize);

   Terminal

   make driver
   g++ -c -Wall -std=c++17 driver.cc
   g++ -c -Wall -std=c++17 algorithms.cc
   g++ -Wall -std=c++17 driver.o algorithms.o
   ./a.out
   1
   3
   4
   5
   7