CODEWITHSUNDEEP
arraysalgorithm
fggwi369
fggwi369

Reputation: 13

given the min and max element in the array, how to sort it?

Given an array A of n integers, find an algorithm that can sort array A in O(n + y − x) time, where x is the minimum integer in A and y is the maximum integer in A. so far I can only think of putting the smallest element in A[0] and the largest in A[n], can anyone help?(homework question)

#include <stdio.h>
int sort(int array, int x, int y){
    int j = 0;
    int temp = 0;
    for (j<=4){
        if (array[j] == x){
            temp = array[0];
            array[0] = array[j];
            array[j]=temp;
        }
        else if (array[j] == y){
            temp = array[4];
            array[0] = array[j];
            array[j]=temp;
        }
        //////////////////////////////////////////////
        ////////////////////////////////////////////
        ////////////////////////////////////////////
    }
    return 0;
}

int main(){
    int array[5]={3,2,5,4,1};
    sort(array,1,5);
    int i = 0;
    for (i<=4){
        printf("%d\n",array[i]);
    }
    return 0;
}

Upvotes: 0

Views: 2355

Answers (1)

Alexandros Panagiotakis
Alexandros Panagiotakis

Reputation: 928

This is indirectly asking you to use counting sort. The concept is simple:

  1. Create an array of size y - x with all 0 elements
  2. Go through the initial array adding 1 to the index in the new array that corresponds to the value [O(n)]
  3. Go through the new array outputting the index as many times as the value stored [O(y - x)]

Example:

  • Initial array [3, 2, 3, 4, 1]

  • New array [0, 0, 0, 0]

  • Adding 1 to corresponding value [1, 1, 2, 1]

  • Returning the index as many times as many times as needed [1, 2, 3, 3, 4]

Corresponding index in our case means value - x

There is also a deeper explanation on wikipedia: https://en.wikipedia.org/wiki/Counting_sort

Upvotes: 4

Related Questions