알고리즘 정리 <정렬>

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

프로그램을 작성할 때 보통 오름차순, 내림차순 등 어떤 방식으로든 정렬해서 사용하는 경우가 많다.

 

일반적인 코딩 테스트 문제에서는 요구하는 조건에 따라서 적절한 정렬 알고리즘이 사용되어야 한다.

상황에 적절하지 못한 정렬 알고리즘을 이용하면 프로그램은 비효율적으로 동작하며 필요 이상으로 시간을 많이 소모한다.

 

정렬 알고리즘에는 대표적으로 [선택 정렬, 삽입 정렬, 퀵 정렬]이 있다.

 

1. 선택 정렬

쉽게말해 데이터가 무작위로 여러 개 있을 때,

이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,

그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것.

 

이 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬 알고리즘이라고 한다.

 

데이터 예시)

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

 

1) 전체 데이터 중 가장 작은 데이터를 선택한다.  -> 0

2) 선택한 데이터와 첫 번째 데이터와 바꾼다. -> [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]

3) 첫 번째 데이터를 제외하고 이후 데이터 중에서 가장 데이터를 선택한다 -> 1

4) 선택한 데이터와 정렬되지 않은 데이터 중 가장 앞에 있는 데이터와 바꾼다. -> [0, 1, 9, 7, 3, 5, 6, 2, 4, 8]

5) 이 과정을 반복한다.. -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

[소스 코드]

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

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] #가장 작은 원소와 정렬되지 않은 원소 중 가장 앞에 있는 원소와 바꿈
  
 
 print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 완료된다.

 

2. 삽입 정렬

선택 정렬은 현재 데이터와 상관없이 무조건 모든 원소들을 비교해 위치를 바꾸는 알고리즘이였다.

반면, 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입하는 알고리즘이다.

 

데이터 예시)

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

 

1) 가장 앞에 있는 데이터는 그 자체로 정렬이 되어있다고 판단한다.

2) 두 번째 데이터('5')부터 첫 번째 데이터('5') 왼쪽, 오른쪽 중 삽입할 위치를 판단해 삽입한다. -> [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

3) 이어서 '9'가 어떤 위치에 들어갈지 판단하여 삽입한다. -> [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

4) 이어서 '0'이 어떤 위치에 들어갈지 판단하여 삽입한다. -> [0, 5, 7, 9, 3, 1, 6, 2, 4, 8]

5) 이 과정을 반복한다.. -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

[소스 코드]

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

for i in range(1, len(array)):
  for j in range(i, 0, -1): # i ~ 0까지 1씩 감소하여 반복
    if array[j] < array[j - 1]:
      array[j], array[j - 1] = array[j - 1], array[j]
    else:
      break

print(array)

 

3. 퀵 정렬

퀵 정렬은 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다.

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.따라서 큰 수와 작은 수를 교환하기 위한 기준을 피벗이라고 표현하고 퀵 정렬에서는 피벗이 사용된다.

 

피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데 가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 퀵 정렬을 구성하도록 했다.

 

데이터 예시)

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

 

1) 리스트에서 첫 번째 데이터를 피벗으로 설정한다. -> '5'

2) 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터는 피벗보다 작은 데이터를 찾는다. -> '7', '4'

3) 찾은 큰 데이터와 작은 데이터를 교환해준다. -> [5, 4, 9, 0, 3, 1, 6, 2, 7, 8]

4) 반복한다. -> [5, 4, 2, 0, 3, 1, 6, 9, 7, 8] -> [5, 4, 2, 0, 3, 1, 6, 9, 7, 8]

5) 반복하다 왼쪽에서 부터 찾는 큰 데이터와, 오른쪽에서 찾는 작은 데이터가 엇갈리면 작은 데이터와 피벗 데이터를 교환해준다. -> [1, 4, 2, 0, 3, 5, 6, 9, 7, 8]

6) 피벗이 이동한 상태에서 피벗을 기준으로 왼쪽 리스트와, 오른쪽 리스트로 분할이 됐다. ->[1, 4, 2, 0, 3], 5, [6, 9, 7, 8]

7) 왼쪽 리스트와 오른쪽 리스트도 1~6과 같은 방식을 반복해준다.

8) 정렬 완료 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

[소스 코드]

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

def quick_sort(array, start, end):
  if start >= end: # 원소가 1개인 경우 종료
    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[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)