파이썬(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과 연결한다.

Antwhale Development