Algorithms.cpp

#include <iostream>

#include "gtest/gtest.h"

int GetPositionOfMaxInteger(int* arr, int start, int end);
void RearrangeArray(int* arr, int size);

int main(int argc, char** argv)
{
    testing::InitGoogleTest(&argc, argv);
    RUN_ALL_TESTS();
    std::getchar();
}

int GetPositionOfMaxInteger(int* arr, int start, int end)
{
    if (start == end) return start;

    // Split array in two and find the maximum number's position on on each side
    int midpoint = floor(((end - start) / 2.0) + 0.5);
    int maxPosLeft = GetPositionOfMaxInteger(arr, start, start + midpoint - 1);
    int maxPosRight = GetPositionOfMaxInteger(arr, start + midpoint, end);

    return (arr[maxPosLeft] >= arr[maxPosRight]) ? maxPosLeft : maxPosRight;
}
void RearrangeArray(int* arr, int size)
{
    int firstPositivePosition, currentIndex;
    for(currentIndex = 0, firstPositivePosition = -1; currentIndex < size; currentIndex++)
    {
        if(arr[currentIndex] < 0)
        {
            int tmp = arr[++firstPositivePosition];
            arr[firstPositivePosition] = arr[currentIndex];
            arr[currentIndex] = tmp;
        }
    }
}

/* Unit Tests */
TEST(CanGetPositionOfMaxInteger, SingleLargestValue)
{
    int arr0[] = { 3, 1, 5, 6 };
    int pos0 = GetPositionOfMaxInteger(arr0, 0, 3);
    ASSERT_EQ(pos0, 3);

    int arr1[] = { 3, 6 };
    int pos1 = GetPositionOfMaxInteger(arr1, 0, 1);
    ASSERT_EQ(pos1, 1);

    int arr[] = { 3, 6, 9, 1, 240, 3, -1 };
    int pos = GetPositionOfMaxInteger(arr, 0, 6);
    ASSERT_EQ(pos, 4);
}

TEST(CanGetPositionOfMaxInteger, MultipleLargestValues)
{
    int arr[] = { 3, 24, 9, 1, 24, 24, 3, -1 };
    int pos = GetPositionOfMaxInteger(arr, 0, 8);
    ASSERT_EQ(pos, 1);
}

TEST(CanGetPositionOfMaxInteger, RequestedSet)
{
    int arr[] = { 1, 4, 9, 3, 4, 9, 5, 6, 9, 3, 7 };
    int pos = GetPositionOfMaxInteger(arr, 0, 8);
    ASSERT_EQ(pos, 2);
}

TEST(CanRearrangeArray, NegativeBeforePositiveRequestedSet)
{
    int arr[] = { 4, -3, 9, 8, 7, -4, -2, -1, 0, 6, -5 };
    int size = 11;
    RearrangeArray(arr, size);

    bool foundPositive = false;
    bool correct = true;
    for (int i = 0; i < size; i++)
    {
        bool negative = false;
        if (arr[i] < 0) negative = true;
        if (arr[i] >= 0) foundPositive = true;
        if (negative && foundPositive)
        {
            correct = false;
            break;
        };
    }

    ASSERT_TRUE(correct);
}

concise.cpp

#include <iostream>

int GetPositionOfMaxInteger(int* arr, int start, int end)
{
    if (start == end) return start;

    int midpoint = floor(((start + end) / 2.0) + 0.5);
    int maxPosLeft = GetPositionOfMaxInteger(arr, start, midpoint - 1);
    int maxPosRight = GetPositionOfMaxInteger(arr, midpoint, end);

    return (arr[maxPosLeft] >= arr[maxPosRight]) ? maxPosLeft : maxPosRight;
}

void RearrangeArray(int* arr, int size)
{
    int firstPositivePosition, currentIndex;
    for (currentIndex = 0, firstPositivePosition = -1; currentIndex < size; currentIndex++)
    {
        if (arr[currentIndex] < 0)
        {
            int tmp = arr[++firstPositivePosition];
            arr[firstPositivePosition] = arr[currentIndex];
            arr[currentIndex] = tmp;
        }
    }
}

int main(int argc, char** argv)
{
    int arr[] = { 1, 4, 9, 3, 4, 9, 5, 6, 9, 3, 7 };
    int size = 10;
    int pos = GetPositionOfMaxInteger(arr, 0, size);
    std::cout << "First array: ";
    for(int i = 0; i < size; i++)
    {
        std::cout << arr[i];
        if (i < size - 1) std::cout << ",";
        else std::cout << std::endl;
    }
    std::cout << "Position of Leftmost Largest Integer: " << pos << std::endl;

    int arr2[] = { 4, -3, 9, 8, 7, -4, -2, -1, 0, 6, -5 };
    size = 11;
    std::cout << "Second array: ";
    for(int i = 0; i < size; i++)
    {
        std::cout << arr2[i];
        if (i < size - 1) std::cout << ",";
        else std::cout << std::endl;
    }

    RearrangeArray(arr2, size);
    std::cout << "Negative values moved to beginning of array: ";
    for(int i = 0; i < size; i++)
    {
        std::cout << arr2[i];
        if (i < size - 1) std::cout << ",";
        else std::cout << std::endl;
    }

    std::getchar();
}

Sorting.cpp

#include <iostream>

int CountOfNumbersInRange(int* arr, int min, int max, int size)
{
    int count = 0;
    for(int i = 0; i < size; i++)
        if ((min <= arr[i]) && (arr[i] <= max)) count++;
    return count;
}

int main(int argc, char** argv)
{
    int arr[] = { 5, 6, 9, 4, 4, 2, 2, 9, 5, 3, 4, 0, 1, 8, 5, 3, 8, 7 };
    int size = 18;
    int min = 2;
    int max = 7;
    int output = CountOfNumbersInRange(arr, min, max, size);
    std::cout << "Input: ";
    for(int i = 0; i < size; i++)
    {
        std::cout << arr[i];
        if (i < size - 1) std::cout << ",";
        else std::cout << std::endl;
    }
    std::cout << "Numbers between range " << min << " and " << max << ": " << output << std::endl;
    return 0;
}