파이썬(Python) 선택정렬, 삽입정렬, 퀵정렬

1. 선택정렬

def select_sort(array):
  for i in range(len(array)):
    min_index = i
    for j in range(i + 1, len(array)):
      if array[min_index] > array[j]:
        min_index = j
    array[min_index], array[i] = array[i], array[min_index]

  return array
  
array = [3, 4, 7, 2, 1, 0, 8]

print(select_sort(array))

1 => 선택정렬 구현한 함수: 선택정렬 수행 후 정렬된 배열 반환

3 => 가장 작은 값의 인덱스 초기화

5 => 가장 작은 값의 인덱스 저장

7 => 가장 작은 값이 앞에 오도록 값 교체

9 => 선택정렬이 완료된 배열 반환

2. 삽입정렬

def insert_sort(array):
  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;
        
  return array
    
array = [3, 4, 7, 2, 1, 0, 8]

print(insert_sort(array))

1 => 삽입정렬 정의한 함수: 정렬된 배열을 반환

2 => 맨 처음 값은 정렬되었다고 가정

3 => 정렬하려는 요소보다 작은 값을 만날 때까지 값 교환

6 => 정렬하려는 요소보다 작은 값을 만나면 for문 돌지않는다.

6번줄 때문에 삽입정렬은 이미 정렬된 값이 많은 배열에서 효과적이다!

3. 퀵정렬

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

  pivot = start
  left = start + 1
  right = end

  while left <= right:
    while left <= end and array[left] <= array[pivot]:
      left += 1
    while right > start and array[right] >= array[pivot]:
      right -= 1

    if left > right:
      array[pivot], array[right] = array[right], array[pivot]
    else: 
      array[left], array[right] = array[right], array[left]

  quick_sort1(array, start, right -1)
  quick_sort1(array, right + 1, end)
    
  
array = [3, 4, 7, 2, 1, 0, 8]
quick_sort1(array, 0, len(array) - 1)
print(array)

1 => 퀵정렬을 정의한 함수: 반환값은 없음

4 => pivot은 항상 맨 처음 요소로 시작

8 => left와 right가 교차할 때까지 while문 수행

9 => left가 pivot 값보다 클 때까지 인덱스 증가

11 => right가 pivot 값보다 작을 때까지 인덱스 감소

14 => left와 right가 교차한 상태면 pivot과 right 값 교환

16 => left와 right가 교차한 상태가 아니면 left와 right 값 교환

이번에는 파이썬의 장점을 극대화한 퀵정렬 소스를 살펴보자.

def quick_sort(array):
  #condition for return
  if len(array) <= 1 : return array
  
  pivot = array[0]
  tail = array[1:]

  left_side = [x for x in tail if x < pivot]
  right_side = [x for x in tail if x > pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

1 => 퀵정렬을 정의한 함수: 인덱스가 한개일 때, 배열 반환

2 => 재귀 탈출 조건

5 => 퀵정렬의 첫번째 pivot은 항상 첫번째 요소

6 => 첫번째 요소를 제외한 나머지 값의 배열

8 => pivot보다 작은 값들을 모은 left_side 배열

9 => pivot보다 큰 값들을 모은 right_side 배열

11 => left_side와 right_side에 다시 퀵정렬을 수행하여 pivot과 연결한다.

너비우선탐색(BFS) 알고리즘 소개

위와 같은 그래프가 있을 때, 너비 우선 탐색(BFS)을 수행하는 코드를 파이썬으로 작성해보자.

BFS는 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다.

탐색 시작 노드를 큐에 삽입하고 방문처리를 합니다.
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 합니다.
더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

from collections import deque

def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True

  while queue:
    v = queue.popleft()
    print(v, end = ' ')

    for i in graph[v] :
      if not visited[i]:
        queue.append(i)
        visited[i] = True

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

Antwhale Development