A Software Guy Blog
0%

200825 TIL

Posted on Edited on In ,

Quick Sort

  • Pivot을 기준으로 왼쪽에는 작은 숫자 오른 쪽에 큰 숫자가 오도록 하고, Pivot을 기준으로 좌우를 분할하여 subarray에 대해서도 이어서 진행한다.

  • Hoare Parition: 리스트에서 첫 번째 데이터를 피벗으로 정한다.

  • 시간 복잡도: O(NlogN)

  • 가장 왼쪽 데이터를 pivot으로 정할 경우, 이미 데이터가 정렬되어 있는 경우에 O(N^2)의 시간 복잡도가 걸린다.

  • Example:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    # Implementation of quick sort
    def quick_sort(array, start, end):
      if start >= end:
        return

      pivot = start # pick a pivot according to the Hoare Partition
      left = start + 1
      right = end
      while left <= right:
        # Loop until find element which is greater than pivot value.
        while left <= end and array[left] <= array[pivot]:
          left += 1

        # Loop until find element which is less than pivot value.
        while right > start and array[right] >= array[pivot]:
          right -= 1

        # partition completed
        if left > right:
          array[right], array[pivot] = array[pivot], array[right]

        else:
          array[left], array[right] = array[right], array[left]

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

Merge Sort

  • 대표적인 Divide-and-Conquer algorithm
  • array를 반으로 나누면서 진행, 더이상 나눠질 수 없을 때까지 나눈 뒤 병합(merge)하는 과정을 거친다.
  • 병합하는 과정에서 두개의 배열 원소들을 비교 하는 과정을 거친다.
  • Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Implementation of MergeSort
def merge_sort(arr):
  if len(arr) > 1:
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    merge_sort(left)
    merge_sort(right)

    # Merge
    i = j = k = 0
    while i < len(left) or j < len(right):
      if i < len(left) and j < len(right):
        if left[i] < right[j]:
          arr[k] = left[i]
          i += 1
        else:
          arr[k] = right[j]
          j += 1
      else:
        if i < len(left):
          arr[k] = left[i]
          i += 1
        if j < len(right):
          arr[k] = right[j]
          j += 1
      k += 1

Count Sort

  • 특정 조건에서 선형 시간에 O(N + K)에서 정렬할 수 있는 알고리즘 이다.

  • 최악의 경우에도 수행시간 O(N + K)를 보장 한다.

  • 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 경우 효과적이다.

    • 데이터 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용 할 수는 없다.

  • Count Sort는 앞에서 소개 했던 비교 기반의 정렬 알고리즘이 아니다.

  • Example

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # Implementation of Count sort
    def count_sort(array):
      count = [0] * (max(array) + 1)

      for e in array:
        count[e] += 1

      j = 0
      for i in range(len(count)):
        for _ in range(count[i]):
          array[j] = i
          j += 1
  • IMPORTANT
  • 내부의 데이터가 정렬되어 있다는 것을 전제 하고 탐색을 O(logN) 시간에 수행 할 수 있는 알고리즘 이다.
  • 탐색하고자 하는 데이터의 시작점, 끝점, 중간점을 가지고 찾으려고 하는 데이터와 중간점의 데이터를 비교 하면서 탐색 범위를 반으로 나누면서 탐색을 수행한다.
  • 탐색 범위가 계속 반으로 줄기 때문에 O(logN) 시간 복잡도가 나올 수 있다.
  • Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def binary_search_recursive(array, target, start, end):
  if start > end:
    return None

  mid = (start + end) // 2
  if array[mid] == target:
    return mid

  elif array[mid] > target:
    return binary_search_recursive(array, target, start, mid - 1)

  else:
    return binary_search_recursive(array, target, mid + 1, end)


def binary_search_iterative(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      start = end + 1

  return None

  • lower bound

    • 정렬 되어 있을때 해당 값 이상 인 점이 처음 나오는 지점을 찾아 준다.
    • Python에서는 bisect를 import 하여 사용할 수 있다.
    • Example
    1
    2
    3
    4
    5
    6
    7
    8
    9
    def lower_bound(array, target, start, end):
      while start <= end:
        mid = (start + end) // 2
        if array[mid] >= target:
          end = mid - 1
        else:
          start = mid + 1

      return start

The try-with-resource Statement

The try-with-resource statement is try statement that declares one or more resources.
A resource is an object that must be closed after the program is finished with it.
The try-with-resources statement ensures that each resource is closed at the end of the statement.
Any object that implements java.lang.AutoCloseable, which includes all objects which implement java.io.Closeable, can be used as resource.