[정렬] 정렬 (1) 선택 정렬 / 삽입 정렬

정렬 알고리즘 개요

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
• 오름차순이나 내림차순 정렬
• 정렬 알고리즘을 이용하여 데이터를 정렬한 후 이진 탐색 적용 가능
• 대표적으로 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬이 있음
• 알고리즘의 효율성 고려 필요 - 상황에 적절하지 못한 정렬 알고리즘 사용 시 시간이 많이 소요되니 주의

(1) 선택 정렬

• 아직 정렬되지 않은 범위에 대해서 가장 작은 데이터를 선정해 맨 앞 데이터와 바꾸는 과정을 반복하는 알고리즘
• 매번 가장 작은 데이터를 선택
• 과정 예시: [3, 4, 2, 1, 0] 이라고 할때
  1. 0 ~ 4번 인덱스 중 가장 작은 데이터 0과 맨 앞 데이터 3 스왑 ➡️ [0, 4, 2, 1, 3]
  2. 1 ~ 4번 인덱스 중 가장 작은 데이터 1과 해당 범위의 맨 앞 데이터 4 스왑 ➡️ [0, 1 , 2, 4, 3]
  3. 2 ~ 4번 인덱스 중 가장 작은 데이터 2와 해당 범위의 맨 앞 데이터 2 스왑 ➡️ [0, 1 , 2, 4, 3]
  4. 3 ~ 4번 인덱스 중 가장 작은 데이터 4와 해당 범위의 맨 앞 데이터 5 스왑 ➡️ [0, 1, 2, 3, 4]
  5. 종료
• 데이터의 개수를 N이라고 할 때, (N - 1)번 반복 수행
• 시간 복잡도는 O(N^2)
  • 반복문이 이중으로 중첩되기 때문
  • N = 100 이상이면 급속도로 느려짐
  • 매우 비효율적인 정렬 알고리즘
• 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 선택 정렬
for i in range(len(array)):
  min_idx = i
  for j in range(i + 1, len(array)):
    if array[min_idx] > array[j]:
      min_idx = j
  array[i], array[min_idx] = array[min_idx], array[i]

print(array)

(2) 삽입 정렬

• 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입
• 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적
  • 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸지만, 삽입 정렬은 그렇지 않기 때문에 더 효율적
• 특정 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정
  • 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤, 그 위치에 삽입
  • 첫 번째 데이터는 그 자체로 정렬되어 있다고 가정하기 때문에 삽입 정렬은 항상 두 번째 데이터부터 시작
• 과정 예시: [3, 4, 2, 1, 0] 이라고 할때
  1. 3은 이미 정렬되어 있다고 가정, 4부터 적절한 위치를 탐색. 4는 3보다 크기 때문에 현재 위치 그대로 변경 없음 ➡️ [3, 4, 2, 1, 0]
  2. 2는 3, 4보다 작기 때문에 3의 앞에 삽입됨 ➡️ [2, 3, 4, 1, 0]
  3. 1은 2, 3, 4보다 작기 때문에 2의 앞에 삽입됨 ➡️ [1, 2, 3, 4, 0]
  4. 0은 1, 2, 3, 4보다 작기 때문에 1의 앞에 삽입됨 ➡️ [0, 1, 2, 3, 4]
  5. 종료
• 삽입정렬 시 정렬이 이루어진 원소는 항상 오름차순 유지
  • 특정 데이터가 삽입될 위치를 선정할 때 (삽입될 위치를 찾기 위해 왼쪽으로 한 칸씩 이동할 때) 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 됨
• 시간복잡도는 O(N^2)
  • 반복문 2번 중첩
  • 선택 정렬과 비슷한 시간 소요
  • 단, 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
    • 최선의 경우 O(N) 시간 복잡도
  •  정렬이 거의 되어 있는 상황에서는 퀵 정렬보다 강력함
• 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 삽입 정렬
for i in range(1, len(array)):
  for j in range(i, 0, -1):
    if array[j] < array[j - 1]:
      array[j], array[j - 1] = array[j - 1], array[j]
    else:
      break
      
print(array)

• 참고) range(start, end, step)
  • step에 -1이 들어가면 start 인덱스부터 시작해서 (end + 1) 인덱스까지 1씩 감소

•