[99클럽/코딩테스트 챌린지] 퀵 정렬, 합병정렬

 

https://www.acmicpc.net/problem/11004

원래는 이 문제를 풀기 위해 공부했으나, 구현에 어려움이 있어 문제 자체는 내장함수로 통과하였다.

 

퀵 정렬

시간복잡도: 최선, 평균 = NlogN , 최악 = N^2

분할 정복 알고리즘으로, 배열에서 하나의 피벗을 선택하고, 이를 기준으로 배열을 두 부분으로 나누어 각각 정렬하는 방식이다.

피벗이 하필이면 정렬된 상태로 맨 앞, 맨 뒤에 있을 경우 최악의 결과를 가져오므로.. 피벗을 랜덤하게 선택후 교체해서 최대한 N^2를 막아보기도 한다.

 

정렬 전 arr = [5, 3, 4, 1, 2, 9, 8]

 

정렬 과정

1. pivot 선택

2. 배열 내부 순회 하며, pivot 보다 큰 값, pivot 보다 작은 값을 찾아 서로 위치 변환

3. 위치 변환시 pivot 보다 작은 원소, pivot 보다 큰 원소로 분할 후 재귀적으로 처리

 

5[pivot]

3[l_dix = 1]

4

1

2

9

8[r_idx=6]

 

arr[l_idx] 이 pivot 보다 커질 수 있도록 l_idx를 증가. 이 때, outOfIndex 안나도록 최대범위 지정

arr[r_idx] 이 pivot 보다 감소할 수 있도록 r_idx를 감소, outOfIndex 안나도록 최소범위 지정

5[pivot]

3

4

1

2[r_idx=4]

9[l_dix = 5]

8

 

다른 설명들 같은 경우는 중간에 값의 대소관계에 따라 교환하라고 그림에 설명되어 있는데, 반드시 할 필요는 없다. 중요한건 pivot 기준으로 정렬되었냐 여셔, 다음 순회때 정렬이 같이 될 것이다.

5[pivot]

3

4

1

2[r_idx=4]

9[l_dix = 5]

8

 

r_idx 와 l_idx가 교체가 된 이후에는, r_idx와 pivot을 바꿔주면 된다.

2[r_idx = 0]

3

4

1

5[pivot]

9[l_dix = 5]

8

 

이렇게 순회 후, pivot 보다 이전 배열, 이후 배열만 모아서 재귀적으로 호출해주면 된다. 이 때, 재귀 종료 조건으로 해당 배열의 len이 1이 넘는지 확인해주어야 한다.

 

2

3

4

1

5[pivot]

1

2[pivot]

4

3

3

4[pivot]

8

9[pivot]

numlist = [5, 3, 4, 1, 2, 9, 8]
def quick_sort(l,r):
  # 교차하기 전까지
  if(l >= r): return;
  low = l + 1
  high = r
  p = numlist[l]
  while(low <= high):
    while(low <= r and numlist[low] <= p):
      low += 1
    while(high >= l + 1 and numlist[high] >= p):
      high -= 1
    # 값 교환은 반드시 low < high 이기 전에만 수행되어야 함 중복되면 안됨..
    if(low <= high):
      swap(low, high)
  swap(l, high)
  print(p,numlist[l: r + 1])
  quick_sort(l, high - 1)
  quick_sort(high + 1, r)
def swap(a,b):
    global numlist
    numlist[a], numlist[b] = numlist[b], numlist[a]
quick_sort(0, len(numlist) - 1)

합병정렬

시간복잡도: NlogN

분할 정복 알고리즘으로, 배열을 반으로 나누고 각 부분을 재귀적으로 정렬한 뒤, 두 정렬된 배열을 **병합(merge)**하여 하나의 정렬된 배열로 만드는 방식이다.

 

내부 함수를 length 2 까지 쪼개는 분할과, 그 분할한 배열을 순서에 맞게 합치는 병합 함수로 구성되어 있다.

이걸 처음에 재귀로 구현하는것에 대한 순서 이해가 잘 되지 않았는데, 트리로 그린 다음에 소스를 보면 좀더 이해하기가 수월하다.

다 분할을 끝내 놓고.. 그걸 아래서부터 차례로 병합해야 하기 때문이다.

 

[5, 3, 4, 1, 2, 9 ,8]

--> [5, 3 ,4]      [1, 2, 9, 8] => 분할

--> [5]  [3, 4]   [1, 2] [9, 8] => 분할

--> [5]  [3, 4]   [1, 2] [8, 9] => 병합

--> [3, 4, 5]      [1, 2, 8, 9] => 병합

--> [1, 2, 3, 4, 5, 8, 9] => 병합

numlist = [5, 3, 4, 1, 2, 9, 8]#list(map(int,input().split()))
def merge_sort(arr):
  if len(arr) < 2: return arr;
  size = len(arr) // 2
  list_l = arr[:size]
  list_r = arr[size:]
  return merge(merge_sort(list_l), merge_sort(list_r))
def merge(list1, list2):
    i,j = 0, 0
    merged_list = []
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1
    # list2 남은 항목 처리
    if i == len(list1):
        merged_list += list2[j:]
    # list1 남은 항목 처리
    if j == len(list2):
        merged_list += list1[i:]            
    return merged_list
sorted_arr = merge_sort(numlist)

 

정렬 전: 5 3 4 1 2 9 8