정렬 알고리즘 - 파이썬 (선택정렬, 버블정렬, 삽입정렬, 병합정렬, 퀵정렬, 계수정렬)

 

 

 

1. 선택정렬

제일 앞에서부터 작은 것 부터 채워서 정렬

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[i], array[min_index] = array[min_index], array[i]

print(array)

 

 

 

2. 버블정렬

인접한 두개끼리 비교하며 작은것을 앞으로 보내어 제일 뒤가 가장 큰 값으로 남게.

그러고 다시 남은 배열끼리 비교 반복

for i in range(len(array) - 1, 0, -1): # 정렬 범위 줄여 나가기
  for j in range(i):
            if array[j] > array[j + 1]: # 앞 뒤 값 비교
                array[j], array[j + 1] = array[j + 1], array[j]

print(array)

 

 

3. 삽입정렬

앞에서부터 정렬 범위를 증가시켜나가며 idx+1 시킬 때 뒷 자리 숫자를 앞의 정렬에 맞는 위치에 삽입하는 정렬

for i in range(1, len(array)):
  for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복
    if array[j] < array[j - 1]:
      array[j], array[j - 1] = array[j - 1], array[j]
    else:
      break
print(array)

 

 

4. 병합정렬

def merge_sort(array):
  if len(array) < 2:
    return array

  mid = len(array) // 2
  left = merge_sort(array[:mid])
  right = merge_sort(array[mid:]) 
  return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right): # 둘 중 하나가 끝날 때까지
      if left[i] <= right[j]:
        result.append(left[i])
        i += 1
      else:
        result.append(right[j])
        j += 1

    if i == len(left): # 왼쪽 배열이 끝났다면 오른쪽 배열의 나머지 모두 담음
      result += right[j:]

    else:                   # 오른쪽 배열이 끝났다면 왼쪽 배열의 나머지 모두 담음
      result += left[i:]

    return result

array = merge_sort(array)
print(array)

 

 

5. 퀵정렬

통상적으로 재귀를 이용한 정렬이라고 생각하면 되겠다.

def quick_sort(array, start, end):
  if start >= end: # 원소가 1개인 경우 종료
    return

  pivot = start # 첫 번째 원소를 pivot으로 설정
  left = pivot + 1
  right = end

  while left <= right:
    # pivot 보다 큰 데이터를 찾을 때 까지 반복
    while left <= end and array[left] <= array[pivot]:
      left += 1
    # pivot 보다 작은 데이터를 찾을 때 까지 반복
    while right > start and array[right] >= array[pivot]:
      right -= 1

    if left > right: # 엇갈렸다면 작은 데이터와 pivot을 교체
      array[right], array[pivot] = array[pivot], array[right]
    else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
      array[left], array[right] = array[right], array[left]

    quick_sort(array, start, right - 1) # 왼쪽 부분 정렬
    quick_sort(array, right + 1, end) # 오른쪽 부분 정렬

quick_sort(array, 0, len(array) - 1)
print(array)

 

 

 

 

6. 계수정렬

계수 정렬은 중복된 값이 많이 분포되어 있는 배열을 정렬할 때 효과적인 정렬 알고리즘으로

인덱스의 값은 해당 데이터, 배열의 값은 개수 라고 생각하면 되겠다.

count = [0] * (max(array) + 1)

for i in range(len(array)):
  count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)):
  for j in range(count[i]):
    print(i, end = ' ')