[Algorithm] 선택(Selection)/삽입(Insertion)정렬

 

• 선택 정렬(Selection Sort)
  • 매번 가장 작은 것을 선택한다.
  • 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터를 정렬되지 않은 데이터 중 가장 앞에 있는 데이터와 바꾼다.

  array = [7,5,9,0,3,1,6,2,4,8]
  
  for i in range(len(array)):
      min_index = i  # 가장 작은 원소의 인덱스
      for j in range(i+1, len(array)):
          if array[min_index] > array[j]:
              min_index = j
      array[i], array[min_index] = array[min_index], array[i]  # swap
  
  print(array)
  

• 삽입 정렬(Insertion Sort)
  • 특정한 데이터를 적절한 위치에 삽입

  array = [7,5,9,0,3,1,6,2,4,8]
  
  for i in range(1, len(array)):
      # 인덱스 i부터 1까지 감소하며 반복하는 문법
      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)