13. 정렬 알고리즘 : 문제 풀이 전략

정렬

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

프로그램을 작성할 때 가장 많이 사용되는 알고리즘.

정렬을 하면 이진 탐색이 가능하다! 정렬 알고리즘은 이진탐색의 전처리 과정이기도 하다.

여기서는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 다루어 보겠다.

 

알고리즘의 효용성을 보여주는 대표적인 것들이 바로 정렬이다.

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

이곳에서 다루는 정렬은 오름차순 정렬이다. 내림차순 정렬을 하려면 정렬 할 때 사용하는 크기 비교를 반대로 하면 된다. 혹은 파이선의 메소드로 단순하게 뒤집을 수 있다.

 

선택 정렬

가장 작은 데이터만 골라서 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 골라서 두 번째 데이터와 바꾼다.

가장 원시적인 방법이지만 이 과정을 반복하면 정렬을 할 수 있다.

매번 가장 작은 것을 선택한다는 의미에서 선택 정렬이라고 한다.

 

코드로 구현하는 방법은 우선 가장 첫번째 인덱스의 데이터를 선택하고 나머지 데이터의

가장 작은 데이터의 인덱스를 찾아서 바꿔주는 역할을 한다.

 

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

def select_sort(lis):
  for i in range(len(lis)):
    min_index = i
    for j in range(i+1,len(lis)):
      if lis[min_index] > lis[j]:
        min_index = j
    lis[i], lis[min_index] = lis[min_index], lis[i]
    
  return lis

print(select_sort(select_list))

 

시간 복잡도 : O(N**2) 직관적으로 이해하면 이중반복문이 사용되었기 때문.

데이터를 앞으로 보내는 과정을 N-1 번 반복하면 정렬이 완료된다.

매우 비효율적이지만 가장 작은 데이터를 찾는 일이 코딩 테스트에 잦으므로 이 것을 자주 작성해보아야 한다.

 

 

 

삽입 정렬

데이터를 하나씩 확인하며 적절한 위치에 삽입. 선택 정렬에 비해 더 효율적임.

삽입정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 훨씬 효율적.

선택정렬은 데이터의 상태와 상관없이 모든 원소를 비교하고 위치를 바꾼다.

특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

이미 앞서 정렬이 이루어진 원소는 모두 오름차순의 형태이기 때문에 삽입될 데이터보다 작은 데이터를 만나면 그위치에서 멈추면 됨.

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

def insertion_list (lis):
 for i in range(1,len(lis)):
   for j in range(i,0,-1):
     if lis[j-1] > lis[j]:
       lis[j-1],lis[j] = lis[j],lis[j-1]
     else:
        break
 return lis
print(insertion_list(insert_list))

정렬이 거의 되어 있는 상황이라면 퀵정렬보다 빠름. 자신보다 작은 데이터를 만나면 그자리에 '삽입'한다.

 

퀵 정렬

퀵정렬은 대부분 정렬 라이브러리의 근간이 됨.

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

 

퀵정렬에서는 피벗이 사용된다. 큰 숫자와 작은 숫자를 교환할 때 교환하기 위한 기준을 피버이라고 함.

피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵정렬을 구분하는데,

가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 설명을 하겠다.

 

호어 분할 이용 (첫 번째 데이터를 피벗으로 설정.)

1. 피벗에서 오른쪽으로는 피벗보다 큰 숫자, 왼쪽으로부터 피벗 보다 작은 숫자를 찾는다.

2. 찾으면 두 요소의 순서를 바꿔줌. 못 찾고 크로스 되면 크로스 되는 지점에서 작은 데이터와 피벗의 위치를 바꿔준다.

3. 피벗을 제외하고 1번을 반복해준다. 더이상 정렬될 원소가 없으면 종료.

 

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

def quick_sort (array, start, end):
  if start >= end:
    return
  pivot = start
  left = start+1
  right = end

  while left <= right:
    while left <= end and array[pivot] >= array [left]:
      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(insert_list, 0 , len(insert_list) - 1)
print(insert_list)

 파이썬으로 개량된 퀵솔트 (대박이당)

insert_list = [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:0]

  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)

퀵 정렬의 시간 복잡도는 O(NlogN)이다. 데이터가 1000개일 때 10,000번 정도 연산. (선택 정렬, 삽입 정렬은 1,000,000)

하지만 최악의 경우 O(N**2) 

 

퀵솔트는 데이터가 아예 정렬되지 않았을 때 빠르다. 삽입 정렬은 어느 정도 정렬이 되어 있으면 빠르다. 두 개는 반대.

파이썬의 기본 정렬 라이브러리는 O(NlogN)을 보장.

 

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘.

모든 데이터가 양의 정수일 때, 최악의 경우에도 O(N+K) 보장.

일반 적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘기지 않을 때 효과적으로 사용.

 

계수정렬은 직접 데이터 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식이 아니다.

 

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

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

현존하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠르다.

기수 정렬은 계수 정렬에 비해서 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다.

공간 복잡도에 있어서 때에 따라서 비효율 적일 수 있음. 0과 999,999만 값이 존재한다면 리스트의 크기가 100만개가 되도록 선언해야하기 때문에 항상 사용할 순 없다. 동일한 값을 가지는 데이터가 여러개 등장할 때 적합하다.

데이터의 특성을 파악하기 어렵다면 퀵정렬을 이용하는 것이 유리하다.

공간 복잡도 또한 O(N+K)이다.