Study Log

정렬(1)

Bubble Sort

  • 시간복잡도 O(n2), 공간복잡도 O(1)
  • 현재 처리되는 원소와 다음 인덱스의 원소를 비교하여 현재 원소가 더 크면 서로 교체
def bubbleSort(iter):
  for i in range(len(iter)-1): # 끝까지 안돌고 마지막 전 까지만
    for j in range(len(iter)-1):
      if iter[j] > iter[j+1]:
        iter[j], iter[j+1] = iter[j+1], iter[j]
  return iter

Selection Sort

  • (worst, best, average ) 시간복잡도 O(n2)
  1. 인자로 받은 배열의 첫번째 원소를 minum value로 설정
  2. 두번째 원소부터 배열의 끝 까지 반복문을 순회하며 minum value와 크기 비교
  3. 만약 minus value보다 원소의 크기가 작다면 minum value를 해당 원소로 교체
  4. 배열의 끝까지 순회한 뒤 첫번째 원소와 minum value가 다르다면 두 원소를 서로 교체
  5. 두번째 원소부터 배열의 마지막 원소 전 까지 1,2,3,4 과정 반복
def selectionSort(iter):
    for i in range(len(iter) - 1):
        idx_min = i
        j = i + 1

        while j < len(iter):
            if(iter[j] < iter[idx_min]):
                idx_min = j
            j = j + 1
            
        if idx_min is not i:
            iter[idx_min], iter[i] = iter[i], iter[idx_min]

    return iter

InSertion Sort

  1. 배열의 첫번째 원소를 정렬된 배열에 넣음
  2. 배열의 두번째 원소를 정렬된 배열의 끝에 있는 원소 ( 현재는 정렬된 배열의 길이는 1 ) 와 비교
  3. 만약 두번째 원소가 크다면 그대로 두번째 원소를 정렬된 배열의 끝에 삽입
  4. 만약 두번째 원소가 작다면 정렬된 배열의 첫번째 자리에 삽입
  5. 세번째 원소도 같은 방법으로 정렬된 배열과 비교하여 자신이 있어야할 위치에 삽입
def insertion_sort(iter):
    for idx, valueToInsert in enumerate(iter):
        p = idx # 원소가 삽입 되어야할 위치

        while p > 0 and iter[p-1] > valueToInsert:
            iter[p - 1], iter[p] = iter[p], iter[p-1] # 배열을 뒤로 밀어(?) 느낌을 이렇게
            p = p - 1

    return iter

Merge Sort

  • 시간복잡도 O(nlogn), 공간복잡도 O(n)
  1. 배열을 반절로 재귀적으로 분리 ( 분리된 각 원소가 1개 남을 떄 까지 )
  2. 재귀적인 함수 호출로 인해 쌓인 스택 순서대로 왼쪽 배열과 오른쪽 배열의 값을 비교하면서 합침
def mergeSort(iter):
    print("Splitting ",iter)
    if len(iter)>1:
        mid = len(iter)//2 # //는 몫
        lefthalf = iter[:mid]
        righthalf = iter[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0 # leftHalf index
        j=0 # rightHalf index
        k=0 # iter index
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                iter[k]=lefthalf[i]
                i=i+1
            else:
                iter[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf): # 왼쪽 배열만 남으면 그대로 iter에 붙여줘
            iter[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf): # 오른쪽 배열만 남으면 그대로 iter에 붙여줘
            iter[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",iter)
  • 아이디어 참고
# 반절 나눌 때
mid = len(list) // 2
leftHalf = list[:mid]
rightHalf = list[mid:]
# reculsive
def mergeSort(iter):
  ...
  leftHalf = iter[:mid]
  print('leftHalf id', id(leftHalf))
  mergeSort(leftHalf)
  
def mergeSort(iter): #mergetSort(leftHalf)에 의해 호출된 함수
  print('iterId', id(iter))
  ...
  lefthalf = iter[:mid]
  mergeSort(leftHalf)

객체 참조에 의해 두 프린트문 에서 출력된 id 값은 같다. 따라서 안에서 호출된 재귀함수로 값을 수정하면 외부 함수의 값이 변경된다!

Written by@[HongDongUk]
공부한 것을 소소하게 적는 블로그.

GitHubFacebook