정렬 알고리즘에 대하여

정렬 알고리즘에 대하여

 

 

정렬

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

문제를 풀거나, 무언가를 구현할 때 가장 중요한 것은 "수행시간"이다. 이 수행시간은 상황에 맞는 알고리즘을 사용함으로써 줄어든다. 이에 있어 "정렬"은 아주 중요한 요소가 된다.

 

 

이 글에서는 대표적인 정렬 3가지. 선택 정렬, 삽입 정렬, 퀵 정렬만을 알아볼 것이다.

 

선택 정렬

-가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두번째 데이터와 바꾸는 알고리즘

 

바로 예시로 넘어가보자.

a = [3, 7, 0, 6] 라는 리스트가 있다고 가정하자.

1. 0을 선택해서 3과 바꾼다 -> [0, 7, 3 ,6]

2. 3을 선택해서 7과 바꾼다 -> [0, 3, 7, 6]

3. 7을 선택해서 6과 바꾼다 -> [0, 3, 6, 7]

 

이와같이 n개의 수가 있을 때 n + n-1 + n-2---- +2가 되고, 이는 시간 복잡도 O(N^2)로 볼 수 있다.

데이터가 100개라면 수행 시간은 10,000배 늘어나는 것이다. 정렬 알고리즘 중에서 구현하기는 쉽지만, 상당히 비효율적인 알고리즘이라고 볼 수 있다. 

 

선택 정렬 소스코드

array = [0,5,2,7,4]

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)이다.

-삽입정렬에서 첫번째는 정렬되어 있다고 판단하기 때문에 두번째부터 시작.

 

예시

a = [7 5 9 3]

1. 5는 7보다 작기에 둘을 swap한다.-->[5 7 9 3]

2. 9는 7보다 크게에 가만히 둔다.

3. 3은 9부터 작기에 swap 한다--> [5 7 3 9] --> 이를 한 번 더 수행한다 -->[5 3 7 9] --> 한 번 더 수행 -->[3 5 7 9]

 

j를 탐색하는 수라고 놓았을 때, j-1보다 작다면 swap을 진행하고 크다면 break를 넣어주면 된다.

 

삽입 정렬 소스코드

array = [1,4,2,5,3,8]

for i in range(1,len(array)):
  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)

 

퀵 정렬

-기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘

 

이 글에서는 대표적인 분할 방식으로 퀵 정렬을 소개할 것이다. 방법을 천천히 살펴보자

1. 피벗(리스트의 첫번째 숫자)를 설정한다.

2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 이를 swap해준다. 

3. 왼쪽에서 찾는 값이 오른쪽에서 찾는값과 엇갈렸을 때 오른쪽에 있는 값을 피벗과 바꿔준다면 피벗을 기준으로 왼쪽은 피벗보다 작은 값들, 오른쪽은 피벗보다 큰 값들로 정렬이 된다.

 

퀵 정렬 소스코드

array = [3,4,1,5,2,3,5,7]

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[left] <= array[pivot]:
      left+=1
    while right > start and array[right] >=array[pivot]:
      right-=1
    if left > right:
      array[pivot], array[right] = array[right], array[pivot]
    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 = [2,3,1,4,9]

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_sort)
  
  print(quick_sort(array))

퀵 정렬의 시간 복잡도는 N개의 데이터가 존재한다면, N번동안 작은 데이터와 큰 데이터를 바꾸고 이를 분할 logN번 한다는 것을 알 수 있다. 그렇기에 퀵 정렬은 N X logN의 시간복잡도를 따른다. 이를 직관적으로 이해하는 것은 넓이로 알 수 있는데, N개가 가로, logN이 세로라고 봤을 때 두개가 곱한 것만큼 연산횟수가 생긴다. 이는 선택정렬과 삽입정렬에 비해 극명한 속도차이가 있음을 알 수 있다. 퀵 정렬은 평균적으로 O(NlogN)을 따르지만 데이터가 정렬되어 있는 경우 매우 느리게 동작할 수 있다. 바꾸지 않아도 되는 수를 바꾸기 때문이다. 이는 선택정렬과 같이 O(N^2)인 경우이다.