🧨 문제

nums라는 리스트가 입력으로 주어졌을 때, 버블정렬 알고리즘으로 리스트를 오름차순으로 정렬하는 함수를 만들어라.

🎯 풀이

def bubbleSort(arr):
	length = len(arr) -1
    for i in range(length):
      for j in range(length - i):
        if arr[j] > arr[j+1]:
          arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

🏹 거품 정렬 (bubble sort)

거품 정렬 또는 버블 정렬( - 整列, 영어: bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 $O(n^{2})$로 상당히 느리다.

거품 정렬의 순서
1. 리스트의 첫번째 요소와 두번째 요소의 대소 관계를 비교한다
2. 대소관계에 따라 작은 것을 앞으로 위치 시킨다.(오름차순 기준)
3. 비교하는 리스트의 인덱스를 하나씩 증가시켜 1,2를 반복한다.
4. 리스트의 끝 요소까지 진행되면 가장 큰 수가 리스트 끝에 배치된다.
5. 큰 수 부터 정렬된, 뒤에 원소를 제외하고, 1,2,3을 반복한다.

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

출처
위키백과

시간 복잡도

전체 원소의 개수가 $n$개 라고 할 때,
총 $1 + 2 + ... + (n - 2) + (n - 1)$번 순회하면 정렬이 완료 된다.

$1 + 2 + ... + (n - 2) + (n - 1) =$ $\sum_{i=1}^{n-1}{i}$
$=\frac{n(n-1)}{2}$ $=O(n^2)$

예시

1회
1
[6, 5, 3, 2, 8]
[5, 6, 3, 2, 8]

2
[5, 6, 3, 2, 8]
[5, 3, 6, 2, 8]

3
[5, 3, 6, 2, 8]
[5, 3, 2, 6, 8]

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

[5, 3, 2, 6, 8]

---

2회
1
[5, 3, 2, 6, 8]
[3, 5, 2, 6, 8]

2
[3, 5, 2, 6, 8]
[3, 2, 5, 6, 8]

3
[3, 2, 5, 6, 8]

[3, 2, 5, 6, 8]

---

3회

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

2
[3, 2, 5, 6, 8]

[2, 3, 5, 6, 8]

---

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

[2, 3, 5, 6, 8]