SearchFunctions

//
// Created by Alex Preston on 2019-03-19.
//

#include <ctime>
#include <iostream>
using namespace std;
#include "SortFunctions.h"


void fillArray(int ARR_SIZE, int selction[], int merge[]){

    merge[ARR_SIZE];
    selction[ARR_SIZE];
    int rNum = 0;
    //cout << "IS this executing" << endl;

    for(int i = 0; i < ARR_SIZE; i++){
        rNum = (rand() % 1000) + 1;
        selction[i] = rNum;
        merge[i] = rNum;
    }

}

void printArray(int arr[], int SIZE){
    //cout << "IS those executing" << endl;
    //cout << SIZE << endl;
    for(int i = 0; i < SIZE; i++){
        cout << arr[i] << " ";
    }
   // cout << "IS those this executing" << endl;
}

int selectionSort(int numbers[], int numbersSize) {
    int i;
    int j;
    int ticker = 0;
    int indexSmallest;
    int temp;      // Temporary variable for swap
    ticker+=5;
    ticker++;
    for (i = 0; i < numbersSize - 1; ++i) {
        ticker+=2;
        // Find index of smallest remaining element
        indexSmallest = i;
        ticker++;
        ticker++;
        for (j = i + 1; j < numbersSize; ++j) {
            ticker+=2;
            ticker++;
            if (numbers[j] < numbers[indexSmallest] ) {
                indexSmallest = j;
                ticker+=2;

            }
        }

        // Swap numbers[i] and numbers[indexSmallest]
        temp = numbers[i];
        numbers[i] = numbers[indexSmallest];
        numbers[indexSmallest] = temp;
        ticker+=3;
    }
    return ticker;
}

int merge(int numbers[], int i, int j, int k, int ticker) {
    int mergedSize;                            // Size of merged partition
    int mergePos;                              // Position to insert merged number
    int leftPos;                               // Position of elements in left partition
    int rightPos;                              // Position of elements in right partition
    int* mergedNumbers = nullptr;
    mergePos = 0;
    mergedSize = k - i + 1;
    leftPos = i;                               // Initialize left partition position
    rightPos = j + 1;                          // Initialize right partition position
    mergedNumbers = new int[mergedSize];       // Dynamically allocates temporary array
    ticker+=10;
    // for merged numbers

    // Add smallest element from left or right partition to merged numbers
    while (leftPos <= j && rightPos <= k) {
        ticker++;
        ticker++;
        if (numbers[leftPos] < numbers[rightPos]) {
            mergedNumbers[mergePos] = numbers[leftPos];
            ++leftPos;
            ticker+=3;
        }
        else {
            mergedNumbers[mergePos] = numbers[rightPos];
            ++rightPos;
            ticker+=2;

        }
        ++mergePos;
        ticker++;
    }

    // If left partition is not empty, add remaining elements to merged numbers

    while (leftPos <= j) {
        mergedNumbers[mergePos] = numbers[leftPos];
        ++leftPos;
        ++mergePos;
        ticker+=4;
    }

    // If right partition is not empty, add remaining elements to merged numbers
    while (rightPos <= k) {
        mergedNumbers[mergePos] = numbers[rightPos];
        ++rightPos;
        ++mergePos;
        ticker+=4;
    }

    // Copy merge number back to numbers
    ticker++;
    for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
        numbers[i + mergePos] = mergedNumbers[mergePos];
        ticker+=3;
    }
    int difTick = ticker;
    ticker++;
    return difTick;
}

int mergeSort(int numbers[], int i, int k, int ticker) {
    int j;
    ticker++;
    //cout << "IS this working" << endl;
    ticker++;
    if (i < k) {
        j = (i + k) / 2;  // Find the midpoint in the partition
        ticker++;
        // Recursively sort left and right partitions
        mergeSort(numbers, i, j, ticker);
        ticker++;
        mergeSort(numbers, j + 1, k, ticker);
        ticker++;

        // Merge left and right partition in sorted order
        ticker += merge(numbers, i, j, k, ticker);
    }
    return ticker;
}