dev-waterparsley

01. 정렬 알고리즘: 퀵 정렬, 합병 정렬

✅ 퀵 정렬

• 특정 데이터를 기준으로 입력 배열을 두 부분 배열로 분할하고, 각 부분 배열에 대해서 독립적으로 퀵 정렬을 순환적으로 적용하는 방식
• 평균적으로 가장 좋은 성능의 비교 기반 알고리즘: O(nlogn)

▪️ 피벗(pivot, 분할원소)

• 두 개의 부분 배열로 분할할 때 기준이 되는 데이터
• 보통 주어진 배열의 첫번째 원소로 지정

▪️ 피벗이 제자리를 잡도록 하여 정렬하는 방식

🔸분할(partition) 과정

🔸특징

• 분할 정복 방법을 적용한 알고리즘
  • 분할: 정렬한 n개 데이터를 피벗 중심으로 두개의 부분 배열로 분할
  • 정복: 두 부분 배열에 대해 퀵 정렬을 각각 순환적으로 적용하여 두 부분배열을 정렬
  • 결합: 필요 없음

🔸성능

• 분할 과정의 수행 시간 = O(n)
• 최선 수행시간 = O(nlogn)
  • 피벗을 중심으로 항상 동일한 크기의 두 개의 부분 배열로 분할 되는 경우

• 최악 수행시간 = O(n^2)  ←피벗 선택의 임의성만 보장되면 평균 수행 시간을 보일 가능성이 높음!
  • 피벗만 제자리를 잡고 나머지 모든 데이터가 하나의 부분 배열로 분할되는 경우
  • 피벗이 배열에 항상 최대값 또는 최소값이 되는 경우
  • 입력 데이터가 이미 정렬되어 있고, 피벗을 맨 왼쪽 원소로 지정한 경우 

✅ 합병 정렬

• 동일한 크기의 두 개의 부분 배열로 분할하고(쪼개지지 않을 때까) 각 부분 배열을 순환적으로 정렬한 후, 정렬된 두 부분의 배열을 다시 합병하여 하나의 정렬된 배열을 만드는 방식

▪️ 전체 수행 과정

▪️ 합병(merge) 과정

🔸특징

• 분할 정복 방법을 적용한 알고리즘
  • 분할: 정렬한 n개 데이터를 n/2개의 데이터를 갖는 두 부분배열로 분할
  • 정복: 두 부분배열에 대해 합병 정렬을 각각 순환적으로 적용하여 정렬
  • 결합: 정렬된 두 부분 배열을 합병하여 하나의 정렬된 배열을 만듦
• 최선, 최악, 평균 수행 시간 = O(nlogn)

02. 순차 탐색, 이진 탐색

▪️ 탐색

• 주어진 데이터 집합에서 원하는 값을 가진 데이터를 찾는 작업
  • 순차 탐색(sequential search) = O(n)
  • 이진 탐색(binary search) = O(logn)
  • 이진 탐색 트리(binary search tree) = O(logn) O(n)

✅ 순차 탐색

• 리스트 형태로 주어진 데이터를 처음부터 하나씩 차례대로 비교하여 원하는 값을 가진 데이터를 찾는 방법

▪️ 성능 = O(n)

• 탐색 실패의 경우 → n번 비교
• 탐색 성공의 경우 → 최소 1번, 최대 n번, 평균(n+1)/2번 비교

▪️ 특징

• 모든 리스트(배열, 연결리스트)에 적용 가능
• 데이터가 키값과 관련해서 아무런 순서 없이 단순하게 연속적으로 저장된 경우에 적합 → 데이터가 정렬되지 않은 경우에 적합

✅ 이진 탐색

• 정렬된 입력 배열에 대해서 주어진 데이터를 절반씩 줄여가면서 원하는 데이터를 찾는 방법
  • 분할 정복 방법을 적용한 알고리즘

▪️ 탐색 방법

• 입력 배열의 가운데 값(A[(a시작인덱스+b끝인덱스)/2])과 탐색키를 비교
  • 탐색키 = 배열의 가운데 값 → 탐색 성공(배열의 인덱스 (a+b)/2 반환)
  • 탐색키 < 배열의 가운데 값 → 이진 탐색(배열의 전반부)
  • 탐색키 > 배열의 가운데 값 → 이진 탐색(배열의 후반부)

▪️ 수행 과정

▪️성능 = O(logn)

• 한 번 탐색할 때마다 탐색 대상이 되는 데이터 개수 1/2씩 감소

▪️ 특징

• 데이터가 이미 정렬된 경우에만 적용 가능
  • 삽입/삭제 연산 시 정렬 상태를 유지하기 위해 데이터의 이동 발생 → 삽입/삭제가 빈번한 응용 분야에는 부적합

03. 이진 탐색 트리

🔸이진 트리

• 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작다
• 각 노드의 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다

▪️ 탐색 연산

• 루트 노드에서부터 키값의 비교를 통해 왼쪽/오른쪽 서브트리를 따라 이동하면서 원하는 데이터를 찾음

▪️ 삽입 연산

• 삽입할 데이터를 탐색한 후, 탐색이 실패한 위치에 새로운 노드를 자식 노드로 추가
  • 탐색이 성공한 경우(값이 있는 경우) → 삽입 없이 종료

▪️ 삭제 연산

📌 후속자(successor, 계승자) 노드

- 삭제되는 노드의 자식 노드 개수에 따라 구분해서 처리

1. 자식 노드가 없는 경우(리프 노드의 경우)
   • 남은 노드의 위치 조절이 불필요
2. 자식 노드가 하나인 경우
   • 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올린다
3. 자식노드가 두 개인 경우
   • 후속자 노드를 삭제되는 노드의 위치로 올린다
   • 후속자 노드의 자식 노드 개수에 따라 다시 삭제 연산을 처리한다

삭제 연산 예시

▪️성능  = O(logn) / O(n)

• 키값의 비교 횟수에 비례 → 트리의 높이가 h라면 O(h)