[n524] 알고리즘 (2)

Divide and Conquer(분할 정복) 방법

• 분할과 정보는 큰 문제를 작은 단위로 나눠서 푸는 알고리즘 방법이다. 
• 재귀 호출과의 차이점은 재귀의 경우 같은 함수 코드를 재호출 하는 것이며, 분할 정복은 비슷한 작업을 재진행 하는 점이다. 즉, 분할 정복은 같은 함수 코드를 재호출 하는 것은 아닐 수 있다. 
• 문제 분할을 스텝 1~5 방향으로 했다면, 문제 해결은 스텝 5~1 방향으로 되어야 한다. 즉 문제를 분할 하는 과정과 해결하는 과정이 있다. 

 

 

퀵정렬과 병합정렬(Quick Sort and Merge Sort)

• 둘 다 분할과 정복 (divide and conquer) 개념으로 문제를 해결한다.
• 보통, 퀵 정렬이 병합 정렬 시간 복잡도는 둘 다 O(nlogn)이다. 
• 퀵 정렬은 좌 우로 나눠서 재귀적으로 수행하기 때문에 병합 정렬보다 빠르다. 
  • 캐시를 덜 활용하고 하드웨어적으로 효율적이다.
  • 불안정 정렬의 대표적인 경우이다.
  • 퀵소트도 분할정복(divide and conquer)을 통해 정렬하고, 재귀적으로 수행을 하기 때문에 더 빠르다.
  • 퀵 소트는 불균형한 구조에서는 최악의 성능을 보인다. 성능 편차가 다르니 때문에 실무에서는 잘 사용되지 않는다. 
• 병합 정렬은 divide and conquer 로직으로, 전체 데이터의 처음과 끝을 계속 탐색하기 때문에 퀵 정렬보다 느리다. 

 

퀵 정렬 (Quick Sort)

• 이상적인 경우

 

• 최악의 경우 (불균형)

# 퀵소트 파이썬 코드 case - 1 : 재귀적으로 해결

def quick_sort(node, first, last):
  def partition(first,last):
    pivot = node[last]
    left = first
    #print(pivot, first,last)    # 확인용
    for right in range(first, last):
      if node[right] < pivot:
        node[left], node[right] = node[right], node[left]
        left += 1
    node[left], node[last] = node[last], node[left]
    return left

  # 첫번째 노드가 마지막 노드보다 작은 경우, 재귀진행
  if first < last:
    pivot = partition(first, last)
    quick_sort(node, first, pivot - 1)
    quick_sort(node, pivot + 1, last)


node = [54,26,93,17,77,31,44,55,20]
quick_sort(node,0,8)

print(node)

# 퀵소트 파이썬 코드 case - 2 : List comprehension 사용

def quick_sort(ARRAY):
    ARRAY_LENGTH = len(ARRAY)
    if( ARRAY_LENGTH <= 1):
        return ARRAY
    else:
        PIVOT = ARRAY[0]
        GREATER = [ element for element in ARRAY[1:] if element > PIVOT ]
        LESSER = [ element for element in ARRAY[1:] if element <= PIVOT ]
        return quick_sort(LESSER) + [PIVOT] + quick_sort(GREATER)

ARRAY = [54,26,93,17,77,31,44,55,20]
print(quick_sort(ARRAY))

GitHub - DAWUNHAN/algorithms-and-dataStructure: Algorithms and DataStructure with Python

 

 

병합 정렬 (Merge Sort)

서비리스트를 최소한으로 나눈 뒤, 비교 -> 정렬 -> 교환을 반복한다.

 

총 정리