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

void printArray(int ar[], int size);
void fillArray(int ar[], int size, int from, int to);
void swap(int arr[], int i, int j);
int bubble(int arr[], int size);
int binarySearch(int arr[], int size, int number);
void sortDescending(int ar[], int size);
int bubbleDescending(int arr[], int size);
void sortInRange(int arr[], int size, int start, int end);
int search(int ar[], int size, int number);
void evenFirst(int arr[], int size);
int evenBubbleSort(int arr[], int size);
int searchNumberNotSorted(int arr[], int size, int number);
int main() {
    int size = 10;
    int arr[size];
    int start = 0, end = 9, number = 7, from =0, to=20;
    if (size<=0|| from>= to) {printf("data not valid\n"); return 1;}
    fillArray(arr, size, 0, 100);
    printArray(arr, size);
    printf("number %d index   = %d\n", number, search(arr, size, number)); //search before sorting
    printf("SortDecsending\n");
    sortDescending(arr, size);
    printArray(arr, size);
    printf("Even first\n");
    evenFirst(arr, size);
    printArray(arr, size);
    printf("Sort in range %d : %d\n", start, end);
    sortInRange(arr, size, start, end);
    printArray(arr, size);

    return 1;
}
int search(int ar[], int size, int number) {
    int i, flag = 0;
    for (i = 0; i < size - 1; i++) {
        if (ar[i] > ar[i + 1]) {
            for (i = 0; i < size - 1; i++) {
                if (ar[i] < ar[i + 1]) {
                    flag = 1; //not sorted
                    break;
                }
            }
            break;
        }
    }
    switch (flag) {
    case 1:
        return searchNumberNotSorted(ar, size, number);

    case 0:
        return binarySearch(ar, size, number);

    }
}

int searchNumberNotSorted(int arr[], int size, int number) {
    int i;
    for (i = 0; i < size; i++) {
        if (arr[i] == number) {
            return i;
        }
    }
    return -1;
}
int binarySearch(int arr[], int size, int number) {
    int middle, left = 0, right = size - 1;
    if (arr[left] <= arr[right]) {
        while (left <= right) {
            middle = (left + right) / 2;
            if (arr[middle] == number)
                return middle;
            if (arr[middle] < number)
                left = middle + 1;
            else
                right = middle - 1;
        }
    } else {
        while (left <= right) {
            middle = (left + right) / 2;
            if (arr[middle] == number)
                return middle;
            if (arr[middle] > number)
                left = middle + 1;
            else
                right = middle - 1;
        }
    }
    return -1;
}

void evenFirst(int arr[], int size) {
    int start = 0, end = 0;
    while (evenBubbleSort(arr, size))
        ;
    while (arr[end] % 2 == 0 && end < size)
        end++;
    sortInRange(arr, size, start, end - 1);
    if (end < size - 1)
        sortInRange(arr, size, end, size - 1);
}

int evenBubbleSort(int arr[], int size) {
    int i, flag = 0;
    for (i = 0; i < size - 1; i++) {
        if (arr[i] % 2 != 0 && arr[i + 1] % 2 == 0) {
            swap(arr, i, i + 1);
            flag = 1;
        }
    }
    return flag;
}
void sortDescending(int ar[], int size) {
    while (bubbleDescending(ar, size))
        ;
}
int bubbleDescending(int ar[], int size) {
    int i, flag = 0;
    for (i = size - 1; i > 0; i--) {
        if (ar[i] > ar[i - 1]) {
            swap(ar, i, i - 1);
            flag = 1;
        }
    }
    return flag;
}

void sortInRange(int arr[], int size, int start, int end) {
    int i, j, min, minIndex;
    if (start < 0 || start >= end || end >= size) {
        printf("error data start = %d end = %d\n", start, end);
        return;
    }
    for (i = start; i <= end; i++) {

        min = arr[i];
        minIndex = i;
        for (j = i + 1; j <= end; j++) {
            if (arr[j] < min) {
                min = arr[j];
                minIndex = j;
            }
        }
        if (i != minIndex)
            swap(arr, i, minIndex);
    }
}
void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void fillArray(int ar[], int size, int from, int to) {
    if (size <= 0)
    srand(time(NULL));
    int i;
    for (i = 0; i < size; i++) {
        ar[i] = from + rand() % (to + 1 - from);

    }
    printf("\n");
}
void printArray(int ar[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", ar[i]);
    printf("\n");
}