Answer to Question #328261 in C for Mominul

Question

Suppose you are given 1000 unordered integer numbers ranging from 10-100. Now you have to sort these numbers decreasing order. Implement a suitable sorting algorithm which would take lesser time in C language. Your program would take these 1000 numbers from the user and gives output of these 1000 numbers but in sorted order. Write a short note on why you have chosen your algorithm to solve this problem.

Answer 1

For sorting I have chosen the bucket-sort algorithm as it has a liner time of execution and since all numbers are in the small diapason it requires only a tiny amount of additional memory (namely for 91 integers_

#include <stdio.h>
#define N 1000
#define MIN 10
#define MAX 100

/* Read n numbers from the user */
void read_numbers(int arr[], int n) {
    int i;

    for (i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
}


/* Bucket sort of n numbers 
 * All numbers are in the range MIN to MAX */
void bucket_sort(int arr[], int n) {
    int backets[MAX-MIN+1];
    int i, j, k, n_backet;


    for (j=0; j<MAX-MIN+1; j++) {
        backets[j] = 0;
    }


    for (i=0; i<n; i++) {
        n_backet = arr[i] - MIN;
        backets[n_backet]++;
    }

    i = 0;
    for (j=0; j<MAX-MIN+1; j++) {
        for (k=0; k<backets[j]; k++) {
            arr[i++] = j + MIN;
        }
    }
}

/* Print n numbers */
void print_numbers(int arr[], int n) {
    int i;

    for (i=0; i<n; i++) {
        printf("%8d", arr[i]);
        if (i%10 == 9) {
            printf("\n");
        }
    }
}

int main() {
    int arr[N];


    read_numbers(arr, N);
    bucket_sort(arr, N);
    print_numbers(arr, N);


    return 0;
}