bubble_sort.md

brief

Nums = [5,3,1,2,4,6]
[[3,5],1,2,4,6]
[3,[1,5],2,4,6]
[3,1,[2,5],4,6]
[3,1,2,[4,5],6]
[3,1,2,4,[5,6]]

[[1,3],2,4,5,6]
[1,[2,3],4,5,6]
[1,2,[3,4],5,6]
[1,2,3,[4,5],6]

bubble and swap whats in the bubble

Optimisation

1. each pass will result in the ith element from the end of nums being sorted.
2. have a flag to mark if any swap happened. if no swaps in a pass, all sorted and can stop

code

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def bubble_sort(nums):
            is_sorted = False
            N = len(nums)
            while not is_sorted:
                is_sorted = True
                for i in range(1, N):
                    if nums[i] < nums[i-1]:
                        is_sorted = False
                        nums[i], nums[i-1] = nums[i-1], nums[i]
                N -= 1
            return nums
        return bubble_sort(nums)

complexity

At most n passes. first pass (worse case) each pass iterates through nums.

Time complexity: O(n^2)

In place sort. Space complexity: O(n)