[Python 기본] 정렬 알고리즘(선택정렬, 삽입정렬, 버블정렬)

정렬의 가장 기본 구조: swap

- 다른 언어와 달리 파이썬은 멀티 할당이 가능하기 때문에 swap을 1줄로 간결하게 처리 가능하다

# 대입연산자 = : 왼쪽은 new, 오른쪽은 old
arr = [3, 10]
arr[0], arr[1] = arr[1], arr[0]
print(arr)
# [10, 3]

 

1) 선택정렬

'호랑이 없는 골에 토끼가 왕 노릇 한다'

제일 작은(큰) 값을 찾기 위해 앞에서부터 비교하며 진행 -> 부등식

 

[과정](작은 값부터 오름차순 정렬)

# step = 0: 배열에서 제일 작은 값을 찾는 과정

1. 배열의 옆의 값과 실시간으로 비교하여 더 작은 값을 기록지에 기록하며 갱신해 나간다

 

2. 배열의 끝까지 진행이 완료되면 제일 작은 값과 제일 앞에 있던 값을 swap한다

3. 두 번째 

# step = 1: 배열에서 두 번째 작은 값을 찾는 과정

[코드화]

arr = [15, 12, 10, 20, 2]
for i_step in range(len(arr)):
  min_step = i_step
  for j in range(i_step+1, len(arr)):
    if arr[j] < arr[min_step]:
      min_step = j
  arr[min_step], arr[i_step] = arr[i_step], arr[min_step]
print(arr)
# [2, 10, 12, 15, 20]

 

 

2) 삽입정렬

'카드게임의 카드 정리'

- 기존에 정렬이 되어 있는 상태에서 값을 비교해 중간에 삽입한다

참고) 선택정렬과의 차이: 어떤 값이 더 작은지 기록할 기록지가 필요하지 않다

 

[과정]

arr = [9, 5, 1, 4, 3]

0step: 9

1step: 9,(5) -> 기존 정렬된 9와 새로운 카드 5를 비교, 새로운 카드 5가 작으면 둘을 swap => 5,9

2step: 5,9,(1) -> 기존 정렬된 5,9와 새로운 카드 1을 비교

                           정렬된 9와 새로운 카드 1을 비교, 새로운 카드 1이 작으면 둘을 swap => 5,1,9

                           정렬된 5와 새로운 카드 1을 비교, 새로운 카드 1이 작으면 둘을 swap => 1,5,9

3step: 1,5,9,(4) -> 기존 정렬된 1,5,9와 새로운 카드 4를 비교
                              정리된 9와 새로운 카드 4를 비교 & swap => 1,5,4,9
                              정리된 5와 새로운 카드 4를 비교 & swap => 1,4,5,9
                              정리된 1와 새로운 카드 4를 비교 => 1,4,5,9
4step: 1,4,5,9,(3) -> 기존 정렬된 1,4,5,9와 새로운 카드 3을 비교
                                 정리된 9와 새로운 카드 3을 비교 & swap => 1,4,5,3,9
                                 정리된 5와 새로운 카드 3을 비교 & swap => 1,4,3,5,9
                                 정리된 4와 새로운 카드 3을 비교 & swap => 1,3,4,5,9
                                 정리된 1와 새로운 카드 3을 비교 => 1,3,4,5,9

최종 결과: 1,3,4,5,9

[코드화]

arr = [9, 5, 1, 4, 3]
for step in range(1, len(arr)):
  for i in range(step,0,-1):
    if arr[i] < arr[i-1]:
      arr[i-1], arr[i] = arr[i], arr[i-1]
print(arr)
# [1, 3, 4, 5, 9]

 

 

3) 버블정렬

'컨베이어 벨트'

- 계속해서 값을 뒤로 전달한다

- 값을 2개씩(i, i+1) 비교하면서 swap

코드상 삽입정렬과 유사, 개념상 선택정렬과 유사

참고) 선택정렬과의 차이: 어느 값이 작은지 기록할 기록지가 필요하지 않다

버블정렬은 계속 swap하며 진행하지만, 선택정렬은 최종 결정되고 나서 1번 swap한다

 

[과정](작은 값부터 오름차순 정렬 = 제일 뒤에 가장 큰 값이 오도록)

arr = [-2, 45, 0, 11, -9]

(i / i+1)을 비교

0step: 0/1, 1/2, 2/3, 3/4 [i = 0,1,2,3]

1step: 0/1, 1/2, 2/3        [i = 0,1,2]

2step: 0/1, 1/2               [i = 0,1]

3step: 0/1                      [i = 0]

최종 결과: [-9, -2, 0, 11, 45]

 

# step = 0

# step = 1 (맨 뒤의 값은 고정하고 나머지 배열에서 과정을 반복한다)

 

[코드화]

arr = [-2, 45, 0, 11, -9]
for step in range(len(arr)):
  for i in range(0,len(arr)-step-1):
    if arr[i] > arr[i+1]:
      arr[i], arr[i+1] = arr[i+1], arr[i]
print(arr)
# [-9, -2, 0, 11, 45]