Home > Blockchain >  How to find position where a list is sorted up to using loops?
How to find position where a list is sorted up to using loops?

Time:03-20

For example, [4,5,6,1,2,3] should return 2 since the list is sorted up to the 2nd position.

CodePudding user response:

I think an easier to digest implementation would be like this:

Enumerate the list, and at every index, check if the next number is smaller, and return the index if so. Since we can't check the next index when the current index is at the end, stop at the second last element.

l = [4,5,6,1,2,3] 
l2 = [4,5,6,7,8,3] 

def get_unsorted_index(input_list):
  for index, value in enumerate(input_list[:-1]):
     if input_list[index 1] < value:
         return index
  return -1
  
print(get_unsorted_index(l))
print(get_unsorted_index(l2))

Output:

enter image description here

Note: I also return -1 if the entire thing is sorted, might not be necessary.

CodePudding user response:

If the list is sorted every value will always be greater or equal to the one the precedes it, so you don't need loops; a single loop will work. So you can zip() the list with itself to compare adjacent values. Use enumerate() to get the index and catch the exception when the list is actually sorted:

l = [4,5,6,1,2,3] 

try:
    print(next(i for i, (a,b) in enumerate(zip(l, l[1:])) if a > b))
except StopIteration:
    print("list is sorted")    

# prints 2 

You can alternatively pass a default to next() instead of the try/catch. So if your list is already sorted and you want -1 in that case:

l = [1, 2, 3, 4, 5] 

next((i for i, (a,b) in enumerate(zip(l, l[1:])) if a > b), -1)
# -1

CodePudding user response:

If list is sorted if the following entry is bigger than the current entry. Thus you can look at the differences between following entries to find the argument of the last-ordered index in the array. First, make two lists as follows:

l = [4,5,6,1,2,3]
temp1 = l[1:]
temp2 = l[0:-1]

Then we can compute the difference in a 1-line for loop:

diff = [temp1[ii] - temp2[ii] for ii in range(len(temp1))]  # [1, 1, -5, 1, 1]

Now we need to find the first number in diff which is smaller than 0.

try:
    solution = [diff[ii] < 0 for ii in range(len(diff))].index(True)
except ValueError:
    solution = len(l)

Where the try and except is set to catch a case where the array is sorted entirely

  • Related