Search code examples
algorithmpseudocode

What does this algorithm do?


Got an exam tomorrow and one of the practice question asks what this algorithm written in pseudocode does. Can anyone help?

Algorithm ???  
Input A: Array of Integers; n: Integer;  
Variables i, c: Integers;  

Begin 
    for i:=0 to n-1 do  
        c:=1;  
        while ((i+c)<n) and (A[i]<A[i+c]) do
           c:=c+1;
        od
        output(i,A[i],c-1);
    od
End

Solution

  • The algorithm takes an array of integers (sorted or unsorted) and outputs the number of items in the same array with an index higher than the current position and that are larger than the current index positions value.

    For example

    manually sorted array of ascending integers :

    public static void main(String[] args){
        // stores an array of integers
        int [] myArray = {0,1,2,3};
        // assuming the length of array is n
        int n = myArray.length;
        // counter variables
        int i,c;
        // starting from array index 0 to the length of the array
        for(i=0;i<(n);i++){
            c = 1;
            while(((i+c)<n) && (myArray[i]<myArray[i+c])){
                c++;
            }
            System.out.println("index value..."+i+", myArray value..."+myArray[i]+", number of items in array with index greater than current with values greater than current..."+(c-1));
        }
    
    }
    

    would give the output

    index value...0, myArray value...0, number of items in array with index greater than current with values greater than current...3
    index value...1, myArray value...1, number of items in array with index greater than current with values greater than current...2
    index value...2, myArray value...2, number of items in array with index greater than current with values greater than current...1
    index value...3, myArray value...3, number of items in array with index greater than current with values greater than current...0
    

    for a manually sorted array of descending integers :

     
    int [] myArray = {10,9,8};
    

    the output is :

    index value...0, myArray value...10, number of items in array with index greater than current with values greater than current...0
    index value...1, myArray value...9, number of items in array with index greater than current with values greater than current...0
    index value...2, myArray value...8, number of items in array with index greater than current with values greater than current...0
    

    for an array of integers all the same :

    int [] myArray = {1,1,1};
    

    the output would be

    index value...0, myArray value...1, number of items in array with index greater than current with values greater than current...0
    index value...1, myArray value...1, number of items in array with index greater than current with values greater than current...0
    index value...2, myArray value...1, number of items in array with index greater than current with values greater than current...0