정렬

나동빈님의 책과 유튜브 강의인 '이것이 코딩 테스트다'를 바탕으로 스스로 공부한 내용을 정리한 글입니다.
참고한 영상의 링크는 아래와 같습니다.
이것이 코딩테스트다 - 정렬 알고리즘

---

선택정렬

• 처리(=정렬)되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.

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

for i in range(len(array)):
  min_index = i
  for min_index in range(len(array)):
    if array[i] < array[min_index]: 
      array[min_index], array[i] = array[i], array[min_index]

print(array)

선택정렬의 시간복잡도

• 매번 정렬되지 않은 N번만큼의 가장 작은 수를 앞으로 보내야 한다.
• N, (N-1), (N-2), ... 2
• $(N^2+N-2)/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): # i는 index를 하나씩 줄이면서 첫번째 원소까지
    if array[j] < array[j-1]:
      array[j] , array[j-1] = array[j-1], array[j]
    else: # 자기 자신보다 작은 원소를 만나면 멈춤 (i번째 이전까지는 모두 정렬이 되어있다고 가정하기 때문)
      break

print(array)

삽입정렬의 시간복잡도

• 반복문을 2번 돌아야함으로 $O(N^2)$의 시간복잡도이나
• 현재 리스트가 거의 정렬되어있을 경우 매우 빠르게 동작함.

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)으로 상정합니다.

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


def quick_sort(array, start, end):
  if start >= end:
    return
  pivot = start
  left = start + 1
  right = end
  # pivot을 기준으로 left, right을 탐색할 예정인데 엇갈리는 순간 pivot을 기준으로
  # 정렬이 되어있다는 의미임으로 while문 탈출.
  while (left <= right):
    # 좌측의 데이터에 대해서, puvot보다 큰 데이터를 찾기 때문에
    # piovot보다 같거나 작으면 한칸씩 이동
    while left <= end and array[pivot] >= array[left]:
      left += 1
    # 우측의 데이터에 대해서, puvot보다 작은 데이터를 찾기 때문에
    # piovot보다 같거나 크면 한칸씩 이동
    while start < right and array[pivot] <= array[right]:
      right -= 1

    # pivot을 기준으로 left에 있는 데이터보다 right에 있는 데이터가 더 큰 상황
    # index 상으로도 left > right인 상황.
    # 이 말은 곧 pivot이 제대로 동작하고 있음을 의미하니, pivot을 right
    # (좌측의 최우단)에 배치시킨다.
    if left > right:
      array[pivot], array[right] = array[right], array[pivot]
    # pivot을 기준으로 left에 있는 데이터보다 right에 있는 데이터가 더 큰 상황
    # 그러나 index 상으로 left < right인 상황 따하서 둘의 데이터 순서를 바꾸어 준다.
    else:
      array[left], array[right] = array[right], array[left]

  quick_sort(array, start, right - 1)
  quick_sort(array, right + 1, end)


quick_sort(array, 0, len(array) - 1)
print(array)

개인적으로 이해하기 어려웠던 알고리즘이라 코드를 짜면서 들었던 생각들이다.

• 한번의 함수 호출 후에 pivot이 어느 위치에 있을지 모르겠지만, pivot 좌측에는 pivot보다 작은 값들이 pivot 우측에는 pivot보다 큰 값들이 위치해 있도록 하는 것이 목표인 알고리즘이다. (log 복잡도를 위해)
• 따라서 pivot이 맨 첫 데이터라고 할때, 왼쪽에 있는 데이터를 searching할때는 pivot보다 큰 데이터를, 오른쪽에 있는 데이터를 searching할때는 pivot보다 작은 데이터를 search하면 되며 한번 탐색한 index는 더이상 볼 필요가 없기 때문에 while문으로 탐색해도 무방하다. (대신 out-of-index 뜨지 않게 종료조건 잘 맞춰주기)
• (좌>우로 탐색해서) 찾은 pivot보다 큰 데이터의 index가 (우>좌로 탐색해서) 찾은 pivot보다 작은 데이터의 index보다 클 경우 pivot을 기준으로 정렬이 되어있다는 것을 의미한다. 따라서 (우>좌로 탐색해서) 찾은 pivot보다 작은 데이터와 pivot의 위치를 바꿔주면 pivot을 기준으로 좌측은 크기가 무조건 작고, 우측은 무조건 큰게 보장이 되기에 좌/우 영역에 한정해서 재귀호출을 걸어주면 된다.

내가 했던 고민들을 보다 더 직관적으로 파이썬으로 풀어서 반영해준 코드는 아래와 같다.

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

def quick_sort(array):
  print(array)
  if len(array) <= 1:
    return array

  pivot = array[0]
  tail = array[1:]

  left_side = [x for x in tail if x<=pivot]
  right_side = [x for x in tail if x>pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

• if len(array) <=1인 이유는 left_side나 right_side에 빈 array가 넘어올 수도 있기 때문이다.

계수(count) 정렬

• 데이터의 크기 범위가 제한되어 정수 형태로 표현되어 있을때 사용가능한 정렬 알고리즘이다.
• 데이터 개수가 N, 데이터(양수) 중 최대값이 K일 때 최악의 경우애도 수행시간 $O(N+K)$을 보장한다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 7, 7]
count = [0] * (max(array) - min(array) + 1)  # array의 max, min값을 알고 있다고 가정

for i in array: # N회 반복
  count[i] += 1

for idx, cnt in enumerate(count): # K회 반복
  for _ in range(cnt): # N회 반복
    print(idx, end=" ")

• 이 알고리즘은 array내 최소값과 최대값이 무엇인지 알고 있어야 사용할 수 있다. (차이+1 만큼의 count array를 선언)
• 또한 동일한 값을 가지는 데이터가 여러개 등장할 때 효율적으로 사용할 수가 있다.

문제 - 두 배열의 원소 교체

• 첫번째 줄에 n,k가 공백되어 입력된다. (0<=N<=100,000, 0<=K<=N)
• 두번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 100,000,000보다 작은 자연수이다.
• 세번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수입니다.
• 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

for i in range(k):
  if a[i] < b[i]:
    a[i], b[i] = b[i], a[i]
    
print(sum(a))

• 첫번째 배열은 오름차순, 두번째 배열은 내림차순으로 정렬한 후 1>K까지 원소를 탐색하면서 첫번째 배열의 원소가 두번째 배열의 원소보다 작으면 swapping하면 벼열 A의 합을 최대화할 수 있다.