알고리즘 Basic -2-

16. 단순 선택 정렬은 '정렬되지 않은 부분'안의 최소 값(또는 최대 값)을 선택해서 '정렬된 부분'의 끝으로 옮긴다. 시간 복잡도는 O(n^2).

nums = [35, 80, 21, 54, 11, 45, 92, 39]

def simpleSelect(idx, arr):
    if idx == (len(arr) - 1):
        # 정렬되지 않은 부분의 요소 수가 1이 되면 종료
        return arr
    else:
        # arr 의 idx 값과 최소값 위치 교환
        minNum = min(arr[idx:])
        temp = arr[idx]
        arr[arr.index(minNum)] = temp
        arr[idx] = minNum
        idx += 1
        return simpleSelect(idx, arr)

ans = simpleSelect(0, nums)

17. 단순 교환 정렬(버블 정렬)은 이웃한 데이터 두 개의 크고 작음을 비교한 뒤, 정렬조건에 맞추어 이동시킨다. 정렬할 배열은 "정렬되지 않은 부분(앞부분)"과 "정렬된 부분(뒷부분)"으로 나뉜다. "정렬되지 않은 부분"의 데이터가 두 개만 남을 때까지 비교 & 교환 을 반복한다.

arr = [19, 80, 77, 11, 54]

def BubbleSort(arr):
    for i in range(len(arr) - 1, 1, -1):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
            print(arr)
    return arr

ans = BubbleSort(arr)

18. 단순 삽입 정렬은 배열 안의 "정렬된 부분" 안에 "정렬되지 않은 부분"의 데이터를 정렬 조건에 맞추어 삽입해 나가는 알고리즘이다.

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

19. 셸 정렬은 정렬할 데이터 배열을 일정 길이의 그룹으로 나누고, 그 그룹 안에서 정렬조건에 맞추어 정렬한다.
    1단계: 그룹 간격 SPAN을 N/2(몫의 정수 부분)로 초기화한다.
    2단계: SPAN 이 1 이상이라면 다음 3~5 단계를 반복한다.
    3단계: 데이터 열을 SPAN 만큼의 길이로 나눈다.
    4단계: 나누어진 그룹들을 단순 삽입 정렬로 정렬한다.

def shellSort(arr):
    N = len(arr)
    gap = N // 2
    while gap > 0:
        for i in range(gap, N):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j + gap] = arr[j]
                j -= gap
            arr[j + gap] = temp
        gap = gap // 2

20. 오름차순으로 정렬된 여러 개의 데이터 열이 있을 때, 전체 열의 최소 값은 항상 각 데이터 열의 첫 번째에 있다.
21. 병합 정렬은 병합 알고리즘을 이용한 정렬이다. 병합 정렬은 두 개로 나누는 단계와 병합하는 단계로 구성된다. 분할 단계는 나뉜 데이터 열의 요소 개수가 하나가 될 때까지 반복한다.

def mergeSort(arr):
    if len(arr) > 1:
 
         # Finding the mid of the array
        mid = len(arr)//2
 
        # Dividing the array elements
        L = arr[:mid]
 
        # into 2 halves
        R = arr[mid:]
 
        # Sorting the first half
        mergeSort(L)
 
        # Sorting the second half
        mergeSort(R)
 
        i = j = k = 0
 
        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
 
        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
 
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
            
 # 출처: https://www.geeksforgeeks.org/merge-sort/           

22. 퀵 정렬은 고속 정렬 알고리즘으로 기준값보다 작은 그룹과 큰 그룹을 분류하는 작업을 반복해서 정렬한다. 먼저 기준값을 정하고, 나머지 데이터들을 정렬 기준에 맞추어 기준값의 왼쪽/오른쪽에 배치시키면 기준값의 위치가 고정된다.

def partition(array, start, end):
    pivot = array[start]
    low = start + 1
    high = end

    while True:
        while low <= high and array[high] >= pivot:
            high = high - 1

        while low <= high and array[low] <= pivot:
            low = low + 1

        if low <= high:
            array[low], array[high] = array[high], array[low]
            # The loop continues
        else:
            break

    array[start], array[high] = array[high], array[start]

    return high
    
def quick_sort(array, start, end):
    if start >= end:
    	return

p = partition(array, start, end)
quick_sort(array, start, p-1)
quick_sort(array, p+1, end)
    
# 출처: https://stackabuse.com/quicksort-in-python/

23. 힙 정렬은 힙의 특성을 이용한 정렬 알고리즘이다.

  def heapify(arr, n, i):
      # Find largest among root and children
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
  
      if l < n and arr[i] < arr[l]:
          largest = l
  
      if r < n and arr[largest] < arr[r]:
          largest = r
  
      # If root is not largest, swap with largest and continue heapifying
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
  
  def heapSort(arr):
      n = len(arr)
  
      # Build max heap
      for i in range(n//2, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          # Swap
          arr[i], arr[0] = arr[0], arr[i]
  
          # Heapify root element
          heapify(arr, i, 0)
  
  
  arr = [1, 12, 9, 5, 6, 10]
  heapSort(arr)
  n = len(arr)
  print("Sorted array is")
  for i in range(n):
      print("%d " % arr[i], end='')
  # 출처: https://www.programiz.com/dsa/heap-sort