CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Jan 2018
    Location
    Java 8
    Posts
    16

    Question sorting an array

    Hi I ran into this practice problem and it states
    Code:
    Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees.
    
    Example
    
    For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be
    sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].
    so what i have is:
    Code:
    int[] sortByHeight(int[] a) {
        
        for(int i=0; i<a.length; i++){ //goes through the array
           
            if(a[i] != -1){ //if the values at index i does not equal -1 executes the following
                
                int min = i; //going to compare the rest of the array with the value at this index
                    
                for(int j = i+1; j<a.length; j++){ //going through the array from the index above i
                    if(a[j] < a[i] && a[j] != -1) //if the value at index i+1 is less than the index at i and the value at index i+1 is not 
                                                            //equal to -1
                        min = j; //then set the index of the smaller value to the min
                }
    
                int temp = a[min]; //swaps values
                a[min] = a[i];
                a[i] = temp;
            }
    
        }
        
        return a;
            
    }
    im not sure why but this wont sort when a: [-1, 150, 190, 170, -1, -1, 160, 180]
    i get a return of the same array.
    im curious to know if anyone sees what im doing wrong.
    for my first if statement isn't it supposed to for to the next index if the value is equal it -1?

  2. #2
    Join Date
    Feb 2017
    Posts
    677

    Re: sorting an array

    One common solution strategy is to make a problem simpler by reducing it to a standard problem.

    In this case you could copy all people to another array, sort it using a standard algorithm and then copy people back into the original array. The trees will remain where they were and all people will be back again but now in sorted order.

    If you want to write the sorting algorithm from the ground up there's another possibility along the same lines.

    You first implement your own standard sort algorithm and make sure it works. You then introduce a level of indirection. Instead of accessing the a array directly you access it by way of an index array b. If this is the a array,

    a = [-1, 150, 190, 170, -1, -1, 160, 180]

    then b would look like this

    b = [1,2,3,6,7]

    holding the indexes of a where there are people.

    Now the sorting algorithm is modified so that all a[i] accesses are replaced by a[b[i]] accesses. In this way people get ordered while the trees are ignored.
    Last edited by wolle; May 28th, 2018 at 10:45 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured