Python x 알고리즘 : 정렬

🍃 정렬(Sorting)

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
• 프로그램에서 데이터를 가공할 때, 오름차순 or 내림차순 등 정렬해서 사용하는 경우가 많기에  많이 사용되는 알고리즘이다.
• 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)가 가능해진다.
• 정렬 알고리즘에는 종류가 많은데, 그 중 대표적으로 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬이 있다.

 

🍃 선택 정렬(Selection Sorting)

• 원시적인 방법으로 "가장 작은 것을 선택"한다는 것을 선택 정렬이라 한다.
• 가장 작은 데이터를 선택해 첫번째 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두 번째 데이터와 바꾸는 작업을 말한다.
• 이 과정을 N-1번 반복하면 정렬이 완료된다.

array = [7,5,9,0,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[i], array[min_index] = array[min_index], array[i] #스와프


print(array)

# 스와프란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 말한다.

선택 정렬의 시간 복잡도

• O(N^2)
• 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이다.
• 선택 정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율 적이다.
• 하지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태를 자주 접해봐야 한다.

 

🍃 삽입 정렬(Insertion Sort)

• 특정한 "데이터를 적정한 위치에 삽입"한다는 의미에서 삽입 정렬이라고 한다.
• 삽입 정렬은 동작 원리를 직관적으로 이해하기 쉽고, 선택 정렬에 비해 실행 시간 측면에서 더 효율 적이지만, 선택 정렬에 비해 구현 난이도가 높다.
• 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 훨씬 효율적이다.
• 삽입 정렬의 특징은 정렬이 이루어진 원소는 항상 "오름차순"으로 정렬되어 있다.

-> 따라서 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

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부터 1까지 감소하며 반복하는 문법
    if array[j] < array[j -1]:  #한 칸씩 왼쪽으로 이동
        array[j], array[j -1] = array[j -1], array[j]
    else: #  자기보다 작은 데이터를 만나면 그 위치에서 멈춤
      break
print(array)

삽입 정렬의 시간 복잡도

• O(N^2)
• 2중 반복문이 사용되었다.
• 선택 정렬과 다른 점은 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하다는 점이다.
• 최선의 경우 O(N)의 시간 복잡도를 가지고, 데이터가 거의 정렬되어 있다고 가정하면 삽입 정렬은 매우 효율적이다.

 

🍃 퀵 정렬

• 정렬 알고리즘 중 가장 많이 사용되는 알고리즘이다. 다른 말로 "빠른 정렬"알고리즘 이라고도 한다.
• 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 "병합 정렬"알고리즘이 있다. 
• 퀵 정렬의 작동 방식은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
• 기준을 피벗(Pivot)이라고 한다.

동작 방식 

예시
리스트 : [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
피벗(기준) : 5

7과 4를 비교 교환
[5, 4, 9, 0, 3, 1, 6, 2, 7, 8]

9와 2를 비교 교환
[5, 4, 2, 0, 3, 1, 6, 9, 7, 8]

비교 교환
[1, 4, 2, 0, 3 / 5 / 6, 9, 7, 8]

이렇게 되면 왼쪽 오른쪽에는 피벗 기준으로 나뉘게 된다. 
이런 것을 파티션 이라고 하고 나뉜 왼쪽 부분, 오른쪽 부분에도 같은 작업을 진행해주면 정렬이 완료된다.

 

퀵 정렬 소스

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)

 

파이썬의 장점을 살린 퀵 정렬 소스

- 피벗과 데이터를 비교하는 비교 연산 횟수가 증가하는 대신 직관적이고 기억하기 쉽다는 장점이 있다.

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


def quick_sort(array):
  # 리스트가 하나 이하의 원소만을 담고 있다면 종료
  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))

 

퀵 정렬의 시간 복잡도

• O(NlogN)
• 앞서 다루었던 정렬 알고리즘에 비해 매우 빠르다.
• 일반적으로 컴퓨터 과학에서 log는 밑이 2인 로그를 의미한다. 따라서 N = 1000이라고 가정했을 때 logN은 10이 된다.
• 하지만 최악의 경우 시간 복잡도는 O(N^2)가 된다.
• 삽입 정렬과 다르게 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.

 

 

🍃 계수 정렬(Count Sort)

• 특정한 조건이 부합해야 사용할 수 있지만, 매우 빠르면서 원리 또한 매우 간단한 정렬 알고리즘이다.
• 모든 데이터가 양의 정수인 상황에서 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 최악의 경우에도 수행시간 O(N+K)를 보장한다.
• 하지만 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다.
• 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
•  데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기가 어렵다.

- 위 세 개의 알고리즘과 다르게 비교 기반 정렬 알고리즘이 아니다.

- 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다.

 

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

#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)

print(max(array))

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 =' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

계수 정렬의 시간 복잡도

• O(N+K) - 데이터의 개수 N, 최대값의 크기 K
• 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1 증가시키고, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야하기 때문이다.
• 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. 기수 정렬과 더불어 가장 빠르다고 볼 수 있다.

계수 정렬의 공간 복잡도

• O(N+K) 
• 계수정렬은 때에 따라 심각한 비효율성을 초례할 수 있다.
• 예를 들어 데이터가 0과 999,999만 존재한다고 가정하면 리스트의 크기가 100만개가 되도록 선언해야 하기 때문이다.
• 따라서 동일한 값을 가지는 데이터가 여러개 등장하고 데이터의 크기가 한정되어 있을 때 적합하다.

 

🍃 파이썬의 정렬 라이브러리

• 미리 만들어진 라이브러리를 활용하는 것이 더 효과적일 경우가 있다.
• 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.
• 이는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.

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를 활용한 소스

array_1 = [("바나나", 2), ("사과", 5), ("당근", 3)]

def setting(data):
  return data[1]

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

정렬 라이브러리의 시간 복잡도

• O(NlogN)
• 정렬 라이브러리는 항상 최악의 경우라도 시간 복잡도 O(NlogN)을 보장한다.
• 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬을 구현할 때보다 더욱더 효과적이다.
• 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 경우에는 계수 정렬을 이용하는 것이 효율적이다.

 

🍃 코딩테스트에서 정렬 알고리즘이 사용되는 경우

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.