Geek asks and answers

How to sort an int array in linear time?

I did the homework to make a program to sort the array in ascending order. I have done this:

#include <stdio.h>
int main()
 {
    int a[100],i,n,j,temp;
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    for(i=0;i<n;++i)
      {
       printf("%d. Enter element: ",i+1);
       scanf("%d",&a[i]);
     }
    for(j=0;j<n;++j)
    for(i=j+1;i<n;++i)
     {
         if(a[j]>a[i])
          {
             temp=a[j];
             a[j]=a[i];
             a[i]=temp;
         }
    }
    printf("Ascending order: ");
    for(i=0;i<n;++i)
        printf("%d  ",a[i]);
    return 0;
}

The input will be no more than 10 digits. Can this be done in less code than here? I want the code to be as short as possible. Any help would be appreciated. Thank!

+3
source share
2 answers

If you know the range of array elements, one way is to use another array to store the frequency of each of the array elements (all elements must be int:)) and print the sorted array. I publish it for a large number of elements ( 10 [TG42] ). You can reduce it according to your needs:

#include <stdio.h>
#include <malloc.h>

int main(void){
    int t, num, *freq = malloc(sizeof(int)*1000001);

    memset(freq, 0, sizeof(int)*1000001);   // Set all elements of freq to 0
    scanf("%d",&t);                         // Ask for the number of elements to be scanned (upper limit is 1000000)

    for(int i = 0; i < t; i++){
        scanf("%d", &num);
        freq[num]++;
    }

    for(int i = 0; i < 1000001; i++){
        if(freq[i]){
            while(freq[i]--){
                printf("%d\n", i);
            }
        }
    }
}

. , Θ (n) .

: 1

, n 0 to k, k. k = O (n), Θ(n) . , x, x. , x . , 17 , x, x 18. , , ,

, A[1...n] , A.length = n. : B[1....n] , C[0....k] .

:

for i ← 1 to k do
c[i] ← 0
for j ← 1 to n do
    c[A[j]] ← c[A[j]] + 1
//c[i] now contains the number of elements equal to i
for i ← 2 to k do
    c[i] ← c[i] + c[i-1]
// c[i] now contains the number of elements ≤ i
for j ← n downto 1 do
    B[c[A[i]]] ← A[j]
    c[A[i]] ← c[A[j]] - 1

1. . .

+3

10 , . - ( , ), , C qsort():

static int compare_int(void const *v1, void const *v2)
{
    int i1 = *(int *)v1;
    int i2 = *(int *)v2;
    if (i1 < i2)
        return -1;
    else if (i1 > i2)
        return +1;
    else
        return 0;
}

:

qsort(a, n, sizeof(a[0]), compare_int);

, . , , :

static int compare_int(void const *v1, void const *v2)
{
    return *(int *)v1 - *(int *)v2;
}

, .. , ; , ; , N th 0, , .

, , , qsort(). - . - O (N 2). Sort ( O (N 2)), , Bubble Sort) ( ) Shell Sort ( O (N 3/2)) Heap Sort (O (NlgN)) (O (NlgN) , O (N 2) ), Intro Sort. , , , ; , . , 10 100 , - . 1000 1 000 000 , . . .

, 10 , 100.

+4

More articles:


All Articles