3 ms·
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:
by maxk42 5y ago
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.
- q-big 5y ago> This should reduce time complexity to O( (n - 1)^2 ) O((n-1)^2) = O(n^2).
- labawi 5y agoI 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.
- y4mi 5y agoit 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]
- labawi 5y agoOriginal code would be correct, if not for a few spaces - probably a typo.
- munk-a 5y agoThis 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)
- deleted 5y ago[deleted]
- maxk42 5y agoIt was just an indentation typo. Swap check should be one level higher.
- raxxorrax 5y agoThat would be decent sort which returns a slighly sorted output.