[Algorithm] 정렬

이번 정리는 데이터를 특정한 기준에 따라서 순서대로 나열하는 법인 정렬에 관한 것이다. 정렬은 단독 문제로 나오기도 하지만, 보통 그리디 알고리즘과 연계되서 나오는 경향이 있다. 정렬 기법은 문제에 따라 달라지므로, 각각의 특징을 알아야만 한다.

선택정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택한 후, 맨 앞으로 이동하는 정렬

• 시간복잡도는 최선과 최악 모두 O(N²)

• 데이터 수가 10000을 넘어갈 경우에는 지양해야함

• 보통 특정 리스트에서 최소값을 찾을 때의 사용

  def select_sort():
      for i in range(len(array)):
      min_idx = i
      for j in range(i+1, len(array)):
          If array[j] < array[min_idx]:
              min_idx = j
      array[i], array[min_idx] = array[min_idx], array[i]
  

삽입정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치로 이동시키는 정렬

• 시간복잡도는 최악은 O(N²) 이나, 최선은 O(N) 으로 가장 빠름(이미 정렬되어 있을 경우)

• 거의 정렬된 상태라면 삽입정렬이 가장 빠르므로, 데이터를 많이 변경하지 않을 때 사용

  def insert_sort():
     for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j] < array[j-1]:
                array[j], array[j-1] = array[j-1], array[j]
            else:
                break
  

퀵정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 기법

• 시간복잡도는 최악은 O(N²) 이며, 최선은 O(logN). 평균적으로는 O(NlogN)

• 삽입 정렬과는 반대로 이미 정렬된 상황이라면 최악의 시간복잡도를 가짐

• 내장 라이브러리의 정렬 기법, 주로 사용됨.

  def quick_sort(a):
      if len(a) <= 1:
          return a
      pivot = a[0]
      tail = a[1:]
      left = []
      right = []
      for num in tail:
          if pivot < num:
              right.append(num)
          else:
              left.append(num)
  
      return quick_sort(left) + [pivot] + quick_sort(right)
  

계수정렬

• 특정 조건이 부할될 때만 사용 가능하지만 매우 빠른 정렬기법으로, 데이터의 범위가 적을 때만 사용 가능

• 시간복잡도는 O(N+K), 이때 K는 데이터의 범위의 최댓값을 의미한다.

• 조건으로는 데이터의 범위가 0을 포함한 양의 정수이어야 하며, 데이터의 범위로 인해 메모리 초과가 일어나지 않아야 한다.

• 데이터 처리량은 많으면서 데이터의 범위가 크지 않을 때 사용되는 기법

    def count_sort():
        matrix = [0] * 10
        for num in array:
            matrix[num] += 1
  
        answer = []
        for i in range(len(matrix)):
            for j in range(matrix[i]):
                answer.append(i)
     return answer