19_알고리즘(2)

선택정렬

선택정렬이란?

• 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘

  nums = [4, 2, 5, 1, 3]
  
  for i in range(len(nums)-1):
    	minIdx = 1
      
      for j in range(i+1, len(nums)):
        	if nums[minIdx] > nums[j]:
            	minIdx = j
              
      tempNum = nums[i]
      nums[i] = nums[minIdx]
      nums[minIdx] = tempNum

최댓값

• 자료구조에서 가장 큰 값을 찾음
• 순차적으로 조회하면서 최대값을 갱신하는 방법
• max()

최소값

• 최대값과 같은 방식
• min()

최빈값

• 데이터에서 빈도수가 가장 많은 데이터를 최빈값이라고 함

근삿값

• 특정 값(참값)에 가장 가까운 값을 근삿값이라고 함

평균

• 여러 수의 양의 중간값을 갖는 수

재귀

• 자기 자신을 다시 호출하는 것

하노이의 탑

• 퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되는 게임
• 한 번에 한 개의 원 판만 옮길 수 있으며, 큰 원 판이 작은 원판 위에 있어서는 안된다는 제약조건이 있음

병합정렬

병합정렬이란?

• 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬

  def msSort(ns):
    	
      if len(ns) < 2:
        	return ns
        
     	midIdx = len(ns) // 2
      leftNums = mSort(ns[0:midIdx])
      rightNums = mSort(ns[midIdx:len(ns)])
      
      mergeNums = []
      leftIdx = 0; rightIdx = 0
      while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        
        	if leftNums[leftIdx] < rightNums[rightIdx]:
            	mergeNums.append(leftNums[leftIdx])
              leftIdx += 1
              
          else:
              mergeNums.append(rightNums[rightIdx])
              rightIdx += 1
              
      mergeNums = mergeNums + leftNums[leftIdx:]
      mergeNums = mergeNums + rightNums[rightIdx:]
      
      return mergeNums

퀵 정렬

퀵정렬이란?

• 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합침

구현

def qSort(ns):
  
  	if len(ns) < 2:
      	return ns
      
    midIdx = len(ns) // 2
    midVal = ns[midIdx]
    
    smallNums = []; sameNums = []; bigNums = []
    
    for n in ns:
      	if n < midVal:
          	smallNums.append(n)
        elif n == midVal:
          	sameNums.append(n)
        else:
          	bigNums.append(n)
    
    return qSort(smallNums) + sameNums + qSort(bigNums)