Here my doubt, I have the objective of making a program that can verify if the elements entered by keyboard in an array are ordered:
n=3
for i in range(n):
x=int(input("Valores: "))
array.append(x)
It's not sorting a list, it's checking whether or not the list is sorted, I tried and didn't find the right way to solve the problem.
The usual strategy when faced with a difficult calculation (is the list sorted?) is to think of a function to solve it.
In this case we build a function that receives a list and returns a boolean value
True
orFalse
, depending on whether or not the list meets the condition of being sorted (each element greater than or equal to the previous element).The process is simple: we go through the list starting from the second element, always comparing it with the previous element. If we find an element out of order, we change the value to return and exit the loop.
Note: An empty list is defined to be ordered.
We also build some test cases to make sure it works:
what it produces:
With that function already done and tested, you can use it in your program:
Edit
The proposed method is of order
O(n)
, that is, the time it takes to check the list is proportional to n, the number of elements in the list. In the worst case (when the list is sorted), you have to iterate through the entire list, which takes n steps.Methods based on
sort
are slow and inefficient: first you have to sort the list, order operationO(n log n)
at best, plus the time it takes you to compare the lists, operation ofO(n)
. Also, they consume twice as much memory (the list + the sorted copy).With simple cases the difference is not noticeable, but when it comes to real life (list with thousands of objects), the difference is unacceptable.
You should learn the basic algorithms first. There will not always be a bookstore that will get you out of trouble.
You can achieve it in a simple way, by sorting the original array and then comparing both the original and the sorted array, if they are the same it will be sorted otherwise your list is not sorted.
You can adapt it to what you want.