알고리즘(Algorithm) - 정렬 알고리즘 개념 이해와 구현하기 (+재귀함수)

선택 정렬(Selection Sort)

• 데이터가 무작위로 있을 때, 이 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두번째에 위치한 데이터와 바꾸는 과정을 반복한다.
• 시간복잡도: O(N^2)

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

for i in range(len(array)):
  for j in range(i+1, len(array)):
    if array[i] > array[j]:
      array[i], array[j] = array[j], array[i] #swap

print(array)

 

 

 

삽입 정렬(Insertion Sort)

 

• 데이터 집합을 순회하는 과정에서 정렬이 필요한 요소를 뽑아 다시 적절한 곳에 삽입한다.
• 데이터가 정렬되어 있을 때 효율적이다.
• 시간복잡도: O(N^2) 이지만, 정렬되어 있는 경우 O(N)

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

for i in range(1, len(array)):
  for j in range(i, 0, -1):
    if array[j - 1] > array[j]:
      array[j - 1], array[j] = array[j], array[j - 1]

print(array)

 

여기에서 range(i, 0, -1)가 헷갈릴 수 있는데,

예를들어, range(1, 2)일 때 헷갈리지 않으려면 1이상 2 미만이라고 생각하면 된다.

그럼 값 "1"만 출력된다.

그럼 range(1, 0, -1) 이면? 1 이상 0미만인 것이 되는데 끝에 -1은 수직선상에서 정방향(--->)이 아닌 반대방향(<----)으로 움직인다고 생각하면 된다. 그러니 해석할 때도 1 이하 0 초과라고 반대로? 해석하면 값이 1이 된다. 

 

버블 정렬(Bubble Sort)

 

• 인접한 두 수를 비교하여 오름차순 혹은 내림차순으로 정렬한다.
• 시간복잡도: O(N^2)

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

for i in range(0, len(array)-1):
  for j in range(i+1, len(array)):
    if array[i] > array[j]:
      #자리를 바꿔준다.
      tmp = array[i]
      array[i] = array[j]
      array[j] = tmp
print(array)

 

 

 

병합 정렬(Merge Sort)

 

• 데이터 집합을 쪼개고 다시 합치는 과정에서 정렬한다.
• 데이터 집합이 메모리에 한번에 올리기때문에 보통 데이터 크기가 클 때 쓰기 좋다.
• 그렇지만, O(n) 수준의 메모리가 필요하다는 게 단점이다.
• 시간복잡도: O(n log n)

 

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

def mergeLR(x, y):
  re = []
  i, j = 0, 0

  while i < len(x) and j < len(y):
    if x[i] < y[j]:
      re.append(x[i])
      i += 1
    else:
        re.append(y[j])
        j += 1

  if i == len(x):
    while j < len(y):
      re.append(y[j])
      j += 1

  if j == len(y):
    while i < len(x):
      re.append(x[i])
      i += 1

  return re

def mergeSort(array):
  if len(array) <= 1:
    return array

  #나누기
  div = len(array) // 2
  left = mergeSort(array[:div])
  right = mergeSort(array[div:])

  #합치기
  x = mergeLR(left, right)
  return x

print(mergeSort(array))

 

print(re)를 하였을 때,

 

 

 

퀵정렬(Quick Sort)

 

• 데이터 집합 내에 기준값(pivot)을 정하고 해당 피벗을 기준으로 집합을 두개로 나눈다.
• 한쪽은 피벗값보다 작은값들만, 다른 한쪽은 큰값들을 넣어 정렬한다.
• 데이터 집합을 더 이상 두개로 나눌 수 없을 때까지 재귀적으로 피벗/집합 나누기가 재귀적으로 돈다.
• 시간복잡도: O(n log n)  

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

def quickSort(array):
  if len(array) <= 1:
    return array

  pivot = array[len(array)//2] #반으로 잘랐을때 해당값을 기준으로

  left, right, center = [], [], []

  for i in array:
    if i < pivot:
      left.append(i)
    elif i > pivot:
      right.append(i)
    else:
      center.append(i)

  return quickSort(left) + center + quickSort(right)

 

 

 

 

병합정렬과 퀵정렬에서 재귀 개념이 나오는데 재귀함수가 무엇인지 알아보자.

 

재귀란 '자기 자신을 호출하는 것'이라고 생각하면 된다.

그럼 재귀함수는 '자기 자신을 호출하는 함수' 이다.

 

가장 간단한 예로 카운트다운을 하는 것을 생각해보자.

3, 2, 1 을 카운트 다운할 때 파이썬 코드를 재귀함수를 이용하여 구현할 수 있다.

def count_down(n):
    if n == 1:  # 가장 간단한 경우
        print(1)
    else:
        print(n)
        count_down(n - 1)  # 숫자 하나 줄여서 다시 세기

 

count_down(3)을 호출하면?

• count_down(3)은 3을 출력하고, 다시 count_down(2)를 호출
• count_down(2)는 2를 출력하고, 다시 count_down(1)을 호출
• count_down(1)은 1을 출력하고, 더 이상 호출하지 않는다.

이렇게 하면 화면에 3, 2, 1이 차례로 출력된다.

 

 

 

시간복잡도

정렬	Best	Avg	Worst	Run-time(정수 60,000개) 단위: 초
선택정렬	n^2	n^2	n^2	10.842
삽입정렬	n	n^2	n^2	7.438
버블정렬	n^2	n^2	n^2	22.894
병합정렬	n log n	n log n	n log n	0.026
퀵정렬	n log n	n log n	n^2	0.014
힙정렬	n log n	n log n	n log n	0.034