정렬은 작업의 효율성을 극대화한다. 우리의 일상에서도 효율성과 정렬은 쉽게 찾아볼 수 있다. 접시를 크기에 맞춰서 진열하고, 대중교통을 줄을 서서 기다리며, 식탁에 숟가락과 젓가락을 구분해서 넣는 것 까지. 우리는 알게 모르게 많은 곳에서 정렬을 한다.
정렬이 일상생활에서도 큰 역할을 하지만, 수많은 계산을 하는 알고리즘에서의 중요성은 말하지 않아도 모두가 공감할 것이다.
정렬 알고리즘은 정말 수없이도 많고, 또 도대체 어떻게 이런 발상을 했는지 신기할 따름이다. 하지만 우리는 새로운 알고리즘을 구현할 게 아니라 이미 만들어진 효율적인 알고리즘을 사용하면 그만이다. 이미 정렬은 충분히 연구가 진행되었을뿐더러 그런 건 우리보다 더 대단한 사람이 해줄 테니까.
소개하고자 하는 정렬 알고리즘은 총 4가지로 [선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬]이다.
오늘은 우선 앞의 두 가지 단순정렬의 카테고리에 속하는 "선택정렬" 과 "삽입정렬" 을 소개하고자 한다.
사실 이 두가지 알고리즘은 처음 보는 사람이라도 그리 기발하진 않다. 마치 사람이 카드를 오름차순으로 정렬하는 것과 크게 다르지 않기 때문이다. 선택 정렬은 [ 매번 가장 작은 것을 선택한다 ]라는 키워드를 가지며 그리디 알고리즘의 그것과 같다.
선택 정렬의 알고리즘은 다음과 같다.
1. 전체 데이터를 순회하여 데이터 중 가장 작은 데이터 값을 가장 앞의 인덱스 데이터와 교환한다.( index = 0 )
2. index 값에 1을 더해준다 ( index += 1 )
3. 현재 index부터 끝까지의 데이터를 순회하여 데이터 중 가장 작은 데이터 값을 찾아 현재 index에 위치한 값과 교환한다.
4. 정렬이 끝날 때까지 step 2와 step 3을 반복한다.
데이터 테이블을 [ 7,5,9,0,3,1,6,2,4,8 ]을 "선택 정렬"로 정렬한다면 밑의 그림과 같이 진행된다.
첫 번째에서 데이터를 모두 순회하여 가장 작은 데이터 0 을 가장 앞으로, 두번째에서 남은 데이터를 모두 순회하여 첫번째에 이동한 데이터의 오른쪽에 위치시키는 것을 정렬이 끝날 때까지 반복적으로 수행한다.
앞서 알고리즘으로 데이터를 순회하고 인덱스를 교환한다고 얘기하면 바로 이해가 안 가지만 이렇게 그림으로 본다면 단번에 이해가 될 것이라고 생각한다. 어린아이에게도 시킬 수 있을법한 아주 원시적이고 단순한 방법이다. 하지만 이 또한 컴퓨터는 굉장히 빠른 속도로 수행해낸다. 다른 알고리즘들이 괴물 같은 것이지 이 알고리즘이 비효율적인 것은 아니지 싶다.
위의 알고리즘을 코드로 옮긴다면 대략 다음과 같다.
array = [5,7,9,0,3,1,6,2,4,8]
n = len(array)
for i in range(n):
for j in range(i+1 , n):
if array[i]>array[j]:
array[i], array[j] = array[j],array[i]
print(array)데이터 전체를 2번 순회해야 하므로 만약 데이터의 수가 조금만 많아져도 이 알고리즘은 사용하기 어렵다.
다음으로 삽입 정렬의 알고리즘은 먼저 소개한 선택정렬과 같이 직관적으로 이해하기 쉽지만 보다 더 효율적인 알고리즘이다. 삽입정렬의 알고리즘은 다음과 같다.
1. index = 0 // 현재 데이터의 0 번째 인덱스는 이미 정렬되어있다고 판단한다.
2. index += 1 // 다음 값과 그 전 값을 비교하여 작다면 왼쪽으로 이동하고 크다면 현재 자리에 위치시킨다.
3. 만약 왼쪽으로 이동했다면 다시 현재 위치의 왼쪽 값과 비교하여 2의 프로세스를 따른다. 더 이상 왼쪽에 값이 없다면 그 자리에 위치시킨다
4. 정렬이 완료될 때까지 2와 3을 반복한다.
데이터 테이블을 [ 7,5,9,0,3,1,6,2,4,8 ]을 "삽입 정렬"로 정렬한다면 밑의 그림과 같이 진행된다.
삽입 정렬은 모든 데이터를 순회해서 최솟값을 정하는 것이 아닌, 현재 정렬하고자 하는 값을 정렬되어있는 리스트에 "삽입" 하는 방식으로 항상 이미 정렬되어있는 데이터를 바탕으로 하므로, 확실히 선택 정렬보다 효율적이라고 할 수 있으며, 또한 만약 대다수가 이미 정렬되어있는 데이터라면 삽입 정렬의 효율성은 극대화된다.
위의 알고리즘을 코드로 옮긴다면 대략 다음과 같다.
array = [5,7,9,0,3,1,6,2,4,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]
print(array)코드에서 확인할 수 있다시피 선택 정렬과의 가장 큰 차이점은 두 번째 for 문의 range가 i에서 0 으로의 역순이다.
굳이 시간 복잡도로 표현한다면 O(N^2)로 선택 정렬과 같지만, 대다수의 경우에서 선택 정렬보다 더욱 좋은 퍼포먼스를 보여준다.
[[ 마무리 ]]
위의 코드들은 전부 Python 코드를 사용한 것으로 대략적인 알고리즘만 이해한다면 좋을 듯하다. 원시적인 정렬 알고리즘이 언제나 비효율적인 것만은 아니다. 그 구현이 매우 쉽고 또 앞서 말한 대로 만약 거의 정렬이 완료된 데이터라면 삽입 정렬의 시간 소요는 O(N)에 가까워진다. 하지만 대다수의 경우가 뒤이어 소개할 정렬 알고리즘들보다는 매우 비효율적인 것이 사실이다. 원시적인 정렬 알고리즘을 우선적으로 이해하고 더욱 정제된 정렬 알고리즘을 알아가는 것이 더욱 효율적인 공부 과정이 아닐까 싶다.
최근댓글