I created my own list sorting function with Python:
def mysort(l):
for i, (x, y) in enumerate(zip(l, l[1:])):
if y < x:
l[i], l[i + 1] = l[i + 1], l[i]
mysort(l)
else:
return l
And:
>>> mysort(l)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>>
I was thinking that how I would be able to optimize this function.
This function is recursive, thus it runs many times + it has a for loop.
Would it be possible to optimize like with O(log(n))?
The sorting function that you have implemented is a variant of bubble sort, which has a time complexity of O(n^2) in the worst case. This means that the time taken by the algorithm grows quadratically with the size of the input.
To optimize this function, you can use a more efficient sorting algorithm such as quicksort, which has a time complexity of O(n * log(n)) in the average case and O(n^2) in the worst case. Quicksort works by selecting a pivot element and partitioning the list around it, such that all the elements smaller than the pivot are placed before it and all the elements larger than the pivot are placed after it. This process is then repeated recursively on the left and right partitions until the list is fully sorted.
Here's an example of how you can implement quicksort in Python:
def quicksort(l):
if len(l) <= 1:
return l
pivot = l[0]
left = [x for x in l[1:] if x < pivot]
right = [x for x in l[1:] if x >= pivot]
return quicksort(left) + [pivot] + quicksort(right)
This implementation has a time complexity of O(n * log(n)) in the average case, and it can be optimized further by using techniques such as pivot selection and in-place sorting.
I hope this helps! Let me know if you have any questions.
sortmethod. \$\endgroup\$O(log(n))?" – No, this is impossible. The lower bound for comparison-based sort is O(n log n). In other words: comparison-based sort cannot possibly be faster than O(n log n). I will not give a proof here, but the proof is not rocket science, it is routinely assigned as homework in undergrad CS courses. There are non-comparison based sorts that take advantage of additional information and structure be be faster than O(n log n), but obviously that means the additional information and structure does need to exist. Selection sort is an … \$\endgroup\$