정렬 알고리즘 개요

• 정렬Sorting이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

선택정렬

• 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복
• 매번 가장 작은 데이터를 선택한다는 의미에서 선택정렬Selection Sort 알고리즘이라고 함

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)): # len(array) -> 전체 array 탐색
  min_index = i # 제일 작은 원소의 index
  for j in range(i+1, len(array)): # 제일 작은 원소의 index 다음 값부터 끝까지 탐색
    if array[j] < array[min_index]: # index가 j일 때 값이 index가 min_index일 때 보다 작다면
      min_index = j # min_index는 j로
  array[i], array[min_index] = array[min_index], array[i] # 스와프 (순서바꿔주기)

print(array)  

삽입정렬

• 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하는 것
• 구현 난이도 : 삽입정렬 > 선택정렬
• 시간 효율성 : 삽입정렬 > 선택정렬
• 선택정렬은 무조건 모든 원소를 비교하고 위치를 바꿈
• 삽입정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적
• 특정한 데이터를 적절한 위치에 삽입한다고 하여 삽입정렬Insertion Sort라고 함
• 삽입정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)): # 1부터 시작하는 이유는 j-1 때문,
							   #0부터 시작하면 하단의 반복문에서 array[-1] 생성
  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
print(array)

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 것
• 퀵 정렬에서는 피벗pivot이 사용
• 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 '피벗'이라 함
• 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 함
• 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵 정렬을 구분
• 해당 내용에선 '호어분할'방식을 기준으로
• '호어분할'방식 : 리스트에서 첫 번째 데이터를 피벗으로 정함
• 퀵 정렬을 3개의 파트로 살펴보자
  1. 리스트의 첫 번째 데이터를 피벗으로 설정 -> 왼쪽(피벗 다음 원소)에서부터 피벗보다 큰 데이터를 선택 -> 오른쪽(리스트 제일 마지막 원소)에서부터 피벗보다 작은 데이터를 선택 -> 두 데이터의 위치를 변경
  2. 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 엇갈린 경우 -> 작은 데이터와 피벗의 위치를 변경
  3. 1번과 2번의 과정을 완료한 후, 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치함
• '재귀함수'와 동작원리가 같음
• 따라서, 종료조건도 있어야 함. 퀵 정렬의 종료조건은 현재 리스트의 데이터 개수가 1인 경우

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
  if len(array) <= 1: # 리스트가 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))

계수정렬

• 계수정렬Count Sort알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
• 특정조건 : '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'
• ex) 0이상 100이하 성적 데이터, 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때
• 이러한 특징을 가지는 이유는, 계수정렬은 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야하기 때문
• 주어진 리스트가 "7 5 9 0 3 1 6 2 9 1 4 8 0 5 2"라고 할 때,
• 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성
• 현재 예시에서는 가장 큰 데이터가 '9', 가장 작은 데이터가 '0'
• 따라서 정렬할 데이터의 범위는 0부터 9까지이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 크기가 10인(0~9) 리스트를 선언
• 그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

count = [0] * (max(array) + 1) # 모든 범위 포함하는 리스트 선언 0으로 초기화

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=' ')

파이썬의 정렬 라이브러리

• sorted() : 변환되는 결과는 리스트 자료형

array = [7,5,9,0,3,1,6,2,4,8]

result = sorted(array)
print(result)

• sort() : 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬

array = [7,5,9,0,3,1,6,2,4,8]

array.sort()
print(array)

• key 매개변수를 입력으로 받을 수 있음
• key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 됨

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
  return data[1]

result = sorted(array, key = setting)
print(result)