Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
1
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 15

void fill_array(int *arr, int size);
void print_array(int *arr, int size);
void binary_insertion_sort(int *arr, int size);
int binary_search(int *arr, int low, int high, int key);

int main() {
    int arr[MAX_SIZE];
    int size = sizeof(arr) / sizeof(int);

    // Generate random array based on time
    srand(time(NULL));
    fill_array(arr, size);

    printf("Unsorted array:\n");
    print_array(arr, size);

    // Sort array using binary insertion sort
    binary_insertion_sort(arr, size);

    printf("\nSorted array:\n");
    print_array(arr, size);

    return 0;
}

void fill_array(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        arr[i] = rand() % 100;
    }
}

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

void binary_insertion_sort(int *arr, int size) {
    int i, j, temp, pos;
    for (i = 1; i < size; i++) {
        temp = arr[i];
        pos = binary_search(arr, 0, i-1, temp);
        for (j = i-1; j >= pos; j--) {
            arr[j+1] = arr[j];
        }
        arr[pos] = temp;
    }
}

int binary_search(int *arr, int low, int high, int key) {
    if (high <= low) {
        return (key > arr[low]) ? (low + 1) : low;
    }
    int mid = (low + high) / 2;
    if (key == arr[mid]) {
        return mid + 1;
    }
    if (key > arr[mid]) {
        return binary_search(arr, mid+1, high, key);
    }
    return binary_search(arr, low, mid-1, key);
}