[선택정렬, 삽입정렬] - Selection Sort, Insertion Sort (Python)

선택, 삽입 정렬

 

선택정렬, 삽입정렬

특정값 index를 찾는 알고리즘

• find_index() : List 안에 있는 값을 찾아서 해당 위치를 반환해주는 함수

def find_index(list_, var):
  res_index = -1
  for i in range(len(list_)):
    if list_[i] == var:
      res_index = i
      break

  return res_index

data = [24, 10, 3, 8, 33, 27, 46]
print(find_index(data, 8))

Selection Sort

• 시간복잡도는 Worst - O(N^2), Avgerage - O(N^2), Best - O(N^2)
• for문을 돌며 가장 작은 값을 찾아 0번째부터 바꿔나간다.
  • for문을 2번 돌아야 한다.
  • i==0부터 list의 길이만큼인 i==n-1까지
  • 그리고 각 for문마다 j==i+1(i 다음번과 비교한다)부터 i==n-1까지 비교하며 최소값을 찾는다.
  • i번째와 최솟값의 위치를 바꾼다.

def select(list_):
  # list_의 0번째부터 n-1번째까지 루프를 돌며 최소값찾음
  for i in range(len(list_)):
    min = list_[i]
    idx = i
    # i번째 작은 값 찾기
    for j in range(i+1, len(list_)):
      if min > list_[j]:
        min = list_[j]
        idx = j
    # i번째 작은 값을 i번째로 이동
    temp = list_[i]
    list_[i] = min
    list_[idx] = temp
  # 정렬된 list_를 return
  return list_

data = [5,3,2,1,4]
print(select(data))

Selection Sort - 1 과정

그림과 같이 주황색 박스는 i번째 박스이다. 0번째부터 i번째 작은 값과 자리를 바꿔가며 정렬한다.

Insertion Sort

• 시간복잡도는 Worst - O(N^2), Average - O(N^2), Best - O(N)
• 특정값이 들어갈 위치를 찾아 삽입하여 Insertion Sort를 구현
• select_idx(list_, var)함수를 통해 var이 list_안에 몇 번째 index에 들어가야 하는지 찾는다.
• insert(list_) 함수는 list_안에 있는 요소를 앞에서부터 하나씩 꺼낸다.
• 그리고 새로운 list인 result에 추가해나간다.
• 추가해 나갈 때, select_idx(list_, var)함수를 이용해 몇 번째 index에 넣어야 할지를 계산한다.

def select_idx(list_, var):
  if len(list_) == 0:
    return 0
  # 0번째부터 n-1번째까지 돌며 들어갈 자리 탐색
  for i in range(len(list_)):
    # var값보다 i번째 리스트값이 크면 i return
    if list_[i] > var:
      return i

  return len(list_)

def insert(list_):
  result = []
  while list_:
    tdata = list_.pop(0)
    idx = select_idx(result, tdata)
    print(idx,tdata)
    result.insert(idx, tdata)
    print('result = ',result)

  return result

data = [5,3,2,1,4]
result = insert(data)
print(result)

Insertion Sort - 2

• i는 1번째부터 n-1번째까지 돌며 순서대로 자기 자리를 찾아간다.
• j는 0번째부터 i전까지 돌며 i의 값과 비교한다.
• i가 j값보다 작을 경우 해당 위치에 삽입한다.

Insertion Sort 정렬 과정

def f_insert(list_):
  result = []
  for i in range(1, len(list_)):
    for j in range(0, i):
      if list_[i] < list_[j]:
        var = list_.pop(i)
        list_.insert(j, var)

  return list_

data = [5,3,2,1,4]
result = f_insert(data)
print(result)

참고 - https://yabmoons.tistory.com/250