OP's algorithm has both indexes going from 1 to n, and swapping when a[i] < a[j].
Yours is more efficient and easy to see why it's correct, but OP's is slightly simpler and more surprising.
Back in the 90’s for my high-school computer class, we were saving records on disk using TurboPascal and I was trying to sort my file in-place.
The sort was super slow, which I assumed was the disk head having to jump back and forth over larger distances of the array of records when comparing and swapping.
I reasoned if I could keep the compares and swaps between I and I+1, and then sweep those I’s forward, it’s the same number of overall compares but less head jumping with each compare/swap being adjacent records.
My implementation did speed things up quite a bit. I have no idea if my reasoning was right, or if I had some other inadvertent bottleneck. But I was proud of the speedier result.
I never explicitly pointed it out to the teacher, though, and didn’t get full marks on that homework because he said my overall program wasn’t user friendly enough.
// Given array a[1], ..., a[n]
for i = 1 to n - 1:
swapped = false
for j = i + 1 to n:
if a[i] > a[j]:
swapped = true
swap(a[i], a[j])
if swapped == false:
break
O((n-1)^2) = O(n^2).
As for time complexity, it changes from ϴ(n²) to O(n²). Alternatively, you can drop the O-notation and calculate precisely so as to include constant factor speedups, though your algorithm may end up slower in the worst case.
def swap(lst, a, b):
tmp = lst[a]
lst[a] = lst[b]
lst[b] = tmp
def optimized_sort(numbers):
i = 0
while i < len(numbers):
swapped = False
j = i + 1
while j < len(numbers):
if numbers[i] > numbers[j]:
swapped = True
swap(numbers, i, j)
if swapped == False:
break
j +=1
i+=1
return numbers
numbers = [1, 4,7,3,7,12,55,3,11,2,9,88,8]
optimized_sort([*numbers]) => [1, 4, 2, 7, 7, 12, 3, 3, 8, 9, 55, 11, 88]
(Whitespace dependent languages suck when it comes to passing around code snippets - it's just the honest truth)
Hey! That's my sorting algorithm! (Well, I'm sure it has been independently discovered many times, but one of those times was by me before I had learned of O(n log n) sorting; I used it many times including in the INOI 2004 programming contest, about which I asked the following question ten years ago in 2011 on math.SE about this algorithm and Catalan numbers, a truly surprising property that is not mentioned in this paper: https://math.stackexchange.com/questions/36022/how-do-the-ca...
> For situations where a quadratic-time sorting algorithm is fast enough, I usually use the following:
> It looks like bubble sort, but is closer to selection sort. It is easy to see why it works: in each iteration of the outer loop, `a[i]` is set to be the smallest element of `a[i…n]`.----
Also: A few years ago I emailed Prof. Richard Stanley of Enumerative Combinatorics fame asking whether it was related to any of the hundreds of problems in his Catalan Numbers list, and he said he didn't know a direct connection at the time (so maybe it's an addition to his list?):
> > permutations equal to the product of all their inversions (in lexicographic order) [multiplying on the left]
> Example: The permutation 1423 has two inversions (24) and (34), and the product (34)(24) is the same as 1423.
> Non-example: The permutation 3412 has four inversions (13), (14), (23) and (24), and the product (24)(23)(14)(13) is 4321 which is not the same as 3412.
> Among the permutations of {1, 2, 3, 4}, there are 14 examples (and 10 non-examples).
And 14 is C_4, the fourth Catalan number.