Algorithms (Array Sorts)

////////////////////////////////
// Input/Output via .bat file //
////////////////////////////////
releaseFile.exe <in.txt >out.txt
pause

/////////////////////////////
// Generate Random Numbers //
/////////////////////////////
#include <time.h>
#include <iostream>
using namespace std;

int main(){
    int n, m = 30000;
    srand((unsigned)time(NULL));
    cin >> n;
    cout << n << endl;;
    for (int i = 1; i <= n; i++) {
        cout << rand() % m + 1 << endl;
    }
}

/////////////////
// Bubble Sort //
/////////////////
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

////////////////
// Quick Sort //
////////////////
void quickSort(int arr[], int li, int di) {
    int j = li;
    int k = di;
    int middle = (li + di) / 2;
    int temp;

    while (arr[j] < arr[middle]) {
        j++;
    }

    while (arr[k] > arr[middle]) {
        k--;
    }

    if (j <= k) {
        temp = arr[j];
        arr[j] = arr[k];
        arr[k] = temp;
        j++;
        k--;
    }

    if (j < di) {
        quickSort(arr, j, di);
    }

    if (li < k) {
        quickSort(arr, li, k);
    }
}

////////////////////
// Insertion Sort //
////////////////////
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

////////////////////
// Selection Sort //
////////////////////
void selectionSort(int &arr[], int n){
    for (int i = 0; i < n; ++i){
        int min = i;
        for (int j = i; j < n; ++j){
            if (array[min] > array[j]){
                min = j;
            }
        }
        int tmp = array[i];
        array[i] = array[min]
        array[min] = tmp;
    }
}

///////////////
// Heap Sort //
///////////////
void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }

    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

////////////////
// Merge Sort //
////////////////
int recursiveMergeSort(int* F, int lowBorder, int highBorder) {
    if (lowBorder >= highBorder) {
        return 0;
    }
    int midBorder = (lowBorder + highBorder) / 2;
    recursiveMergeSort(F, lowBorder, midBorder);
    recursiveMergeSort(F, midBorder + 1, highBorder);
    Merge(F, lowBorder, midBorder, highBorder);
}

void Merge(int* F, int lowBorder, int midBorder, int highBorder) {
    int i;
    int j;
    int k;
    int n1 = midBorder - lowBorder + 1;
    int n2 = highBorder - midBorder;

    int *temp1 = new int[n1];
    int *temp2 = new int[n2];

    for (i = 0; i < n1; i++) {
        temp1[i] = F[lowBorder + i];
    }

    for (j = 0; j < n2; j++) {
        temp2[j] = F[midBorder + 1 + j];
    }

    i = 0;
    j = 0;
    k = lowBorder;

    while (i < n1 && j < n2) {
        if (temp1[i] <= temp2[j]) {
            F[k] = temp1[i];
            i++;
        }
        else {
            F[k] = temp2[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        F[k] = temp1[i];
        i++;
        k++;
    }

    while (j < n2) {
        F[k] = temp2[j];
        j++;
        k++;
    }

    delete[] temp1;
    delete[] temp2;
}

///////////////////
// Binary Search //
///////////////////
int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        //int mid = (l + r) / 2;

        if (arr[mid] == x) {
            return mid;
        }

        if (arr[mid] > x) {
            return binarySearch(arr, l, mid - 1, x);
        }

        return binarySearch(arr, mid + 1, r, x);
    }

    return -1;
}

//////////////////////////////
// BFS = Обхождане в ширина //
//////////////////////////////

/////////////////////////////////
// DFS = Обхождане в дълбочина //
/////////////////////////////////