News for hackers. Stuff that matters.

A comment on Is this the simplest (and most surprising) sorting algorithm?. Parent comment

Re:Is this the simplest (and most surprising) sorting algori... by maxk42 on Tuesday October 05, 2021 @12:31PM (#28761703)
Because I have a need to optimize:

    // 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
This should reduce time complexity to O( (n - 1)^2 ) and stop sorting after the remainder of the array is sorted and tested one time.
[ Parent | on HN ]
Re:Is this the simplest (and most surprising) sorting algori... by q-big on Tuesday October 05, 2021 @12:57PM (#28762094)
> This should reduce time complexity to O( (n - 1)^2 )

O((n-1)^2) = O(n^2).

[ Parent | on HN ]
Re:Is this the simplest (and most surprising) sorting algori... by labawi on Tuesday October 05, 2021 @01:33PM (#28762657)
I see where you're going, but your implementation broke the sort.

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.

[ Parent | on HN ]
Re:Is this the simplest (and most surprising) sorting algori... by y4mi on Tuesday October 05, 2021 @01:33PM (#28762671)
it doesnt work though

        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]
removing the break gets you the correct order: [1, 2, 3, 3, 4, 7, 7, 8, 9, 11, 12, 55, 88]
[ Parent | on HN ]
Re:Is this the simplest (and most surprising) sorting algori... by labawi on Tuesday October 05, 2021 @02:42PM (#28763732)
Original code would be correct, if not for a few spaces - probably a typo.
[ Parent | on HN ]
Re:Is this the simplest (and most surprising) sorting algori... by munk-a on Tuesday October 05, 2021 @04:11PM (#28764942)
This is why I like me some curly braces.

(Whitespace dependent languages suck when it comes to passing around code snippets - it's just the honest truth)

[ Parent | on HN ]
Re:Is this the simplest (and most surprising) sorting algori... by maxk42 on Tuesday October 05, 2021 @04:49PM (#28765419)
It was just an indentation typo. Swap check should be one level higher.
[ Parent | on HN ]
Re:Is this the simplest (and most surprising) sorting algori... by raxxorrax on Wednesday October 06, 2021 @02:38AM (#28769917)
That would be decent sort which returns a slighly sorted output.
[ Parent | on HN ]