[파이썬] - 버블 / 선택 정렬

🔎 버블 정렬 _ 시간 복잡도 O(n2)

• 앞 인덱스와 뒤 인덱스를 비교해 앞 인덱스 값이 더 크면 순서를 바꾼다.
• 앞 인덱스부터 마지막 인덱스까지 차례대로 진행하면 제일 큰 숫자가 맨 뒤에 위치하게 된다.
• 결국 앞 뒤 비교를 통해 최댓값이 맨 뒤부터 차례대로 위치하게 된다.
• 이러한 일련의 과정을 통해 정렬하는 것을 버블 정렬이라고 한다.

---

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

nums = [2, 8, 6, 4, 1]
bubble(nums)
print(nums)

---

• 바깥쪽 for문 range의 범위가 len(arr) - 1 인 이유는,
  마지막 0번째 인덱스 하나와 비교할 인접 인덱스가 존재하지 않기 때문이다. (비교 불가)

• 안쪽 for문 range의 범위가 len(arr) - i - 1인 이유는,
  바깥쪽 for문이 한번씩 돌면서 제일 큰 숫자들이 맨 뒤에 정렬되어
  이미 정렬된 부분은 비교할 필요가 없기 때문에 - i를 하는 것이 효율적이다.

🔎 선택 정렬 _ 시간 복잡도 O(n2)

• 첫번째 for문에서 모든 값 중 최솟값을 골라 [0]번 인덱스에 위치시킨다.
• 두번째 for문에서는 남은 인덱스 값 중 최솟값을 골라 [1]번 인덱스에 위치시킨다.
• 결국 남은 값의 전체 비교를 통해 최솟값이 맨 앞부터 차례대로 위치하게 된다.
• 이러한 일련의 과정을 통해 정렬하는 것을 선택 정렬이라고 한다.

---

def selection(arr):
    for i in range(len(arr)-1):
        min_idx = i
        for j in range(i, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return

nums = [2, 9, 1, 7, 3]
selection(nums)
print(nums)

---

• 바깥쪽 for문 range의 범위가 len(arr) - 1 인 이유는,
  마지막 [-1]번째 인덱스가 비교할 인접 인덱스가 없기 때문이다. (비교 불가)

• min_idx에 시작 인덱스 번호를 넣고 시작한다.

• 안쪽 for문을 돌면서 최솟값을 가진 인덱스를 발견하면 기존 min_idx 값으로 치환하면서 진행한다.

🙏 참고

👉 파이썬 버블정렬, 선택정렬, 삽입정렬