정렬 알고리즘(Sorting)(1) - 선택정렬, 삽입정렬

정렬(Sorting)

데이터를 특정한 기준에 따라 순서대로 나열

 

선택정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꿈

 

출처 : 이코테

 

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] #스와프

print(array)

 

 

선택정렬의 시간 복잡도

N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내기 -> N + (N-1) + (N-2) + ... + 1 -> O(N^2)

 

삽입정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

선택정렬에 비해 효율적으로 동작

 

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)

 

선택정렬의 시간 복잡도

반복문 중첩 사용 -> O(N^2)

삽입 정렬은 현재 리스트의 데이터가 거의 정렬이 되어 있는 상태라면 매우 빠르게 동작

최선의 경우 O(N)의 시간 복잡도를 가짐