Answer to Question #242061 in C++ for Tasnim

Question

Experiment with the C/C++ implementations of the various sorting and searching algorithms in a

single program with time complexity:

 Bubble sort

 Insertion sort

 Radix sort

 Linear search

 Binary search

Answer 1

bubble sort:

void bubble_sort(int *a, int n) {
    bool swap = true;
    while (swap) {
        int t;
        swap = false;
        n--;
        for (int i = 0; i < n; i++) {
            if (a[i + 1] < a[i]) {
                t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
                swap = true;
            }
        }
    }
}

insertion sort:

void insertion_sort(int *a, int n) {
    int i, j, t;
    for (int i = 1; i < n; i++) {
        t = a[i];
        j = i;
        while (j > 0 && a[j - 1] > t) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = t;
    }
}

radix sort:

int getMax(int *array, int n) {
    int max = array[0];
    for (int i = 1; i < n; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

void countingSort(int *array, int size, int place) {
    const int max = 10;
    int output[size];
    int count[max];
    for (int i = 0; i < max; ++i) {
        count[i] = 0;
    }
    for (int i = 0; i < size; i++) {
        count[(array[i] / place) % 10]++;
    }
    for (int i = 1; i < max; i++) {
        count[i] += count[i - 1];
    }
    for (int i = size - 1; i >= 0; i--) {
        output[count[(array[i] / place) % 10] - 1] = array[i];
        count[(array[i] / place) % 10]--;
    }
    for (int i = 0; i < size; i++) {
        array[i] = output[i];
    }
}

void radix_sort(int array[], int size) {
    int max = getMax(array, size);
    for (int place = 1; max / place > 0; place *= 10) {
        countingSort(array, size, place);
    }
}

linear search:

int linear_search(int * arr, int n, int x) {
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

binary search:

int binarySearch(int *arr, int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 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;
}