정렬 깨부수기 0일차(python3)

출처 : 파이썬 알고리즘 인터뷰

DFS....BFS....

이번엔 소팅이다....

정렬 깨부수기 0단계 : 간단하게 정렬에 대해 정리하기

정렬 알고리즘

목록의 요소를 특정 순서대로 넣는 알고리즘

• 주로 숫자식 순서와 사전식 순서로 정렬함

• 안정정렬과 불안정정렬로 나눌 수 있음

  • 안정정렬 : 중복 값에 대해 입력 순서 유지하면서 정렬

  • 불안정정렬 : 중복 값에 대해 입력 순서 유지 보장할 수 없음

대표적인 정렬 알고리즘

• 버블정렬
• 병합정렬
• 퀵정렬
• 삽입정렬

버블정렬

인접한 두개의 요소를 비교하고 재정렬하는 것을 반복

def bubblesort(A):
  for i in range(1, len(A)):
    for j in range(0, len(A)-1):
      if A[j] > A[j+1]:
        A[j], A[j+1] = A[j+1], A[j]

병합정렬

분할 정복의 진수....

게다가 안정정렬...

퀵 정렬(파티션 교환 정렬)

피벗을 기준으로 좌우를 나누고,

피벗보다 작으면 왼쪽, 크면 오른쪽으로 파티셔닝하여 재귀호출(분할 정복 구조)

로무토 파티션

항상 맨 오른쪽의 피벗을 택하는 방식

def quicksort(A, lo, hi):
  def partition(lo, hi):
    # 가장 오른쪽 값을 기준으로 피벗 설정
    pivot = A[hi]
    left = lo
    for right in range(lo, hi):
      if A[right] < pivot:
        A[left], A[right] = A[right], A[left]
        left += 1
    A[left], A[hi] = A[hi], A[left]
    return left

  if lo < hi:
    pivot = partition(lo, hi)
    quicksort(A, lo, pivot-1)
    quicksort(A, pivot+1, hi)

피벗값보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 둔다는 방식이라는 것~