[이코테]정렬알고리즘의 개요

 정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다.

 숫자가 하나씩 적힌 카드가 10장 있다면, 이 카드를 오름차순으로 정렬해보자. 어떻게 이 카드들을 정렬할 수 있을까?

보통은 카드를 훑은 후 숫자를 0부터 0까지 구성된 걸 확인하고 순차적을 나열할 것이다. 하지만 컴퓨터에게는 쉬운 작업이 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.

 

정렬 알고리즘은 다음과 같은 기준으로 분류된다:

• 원소들의 크기 비교에 따른 계산 복잡도 (최선, 최악, 평균 동작). 직렬 정렬 알고리즘의 경우 최선 동작은 O(n log n), 최선 동작 중 병렬 정렬은 O(log2 n), 최악 동작은 O(n2)이다. (점근 표기법 참고.) 직렬 정렬의 이상적인 동작은 O(n)이지만 평균 케이스에는 가능치 않다. 최적의 병렬 정렬은 O(log n)이다. 비교 기반 정렬 알고리즘은 대부분의 입력에 대해 최소 Ω(n log n) 개의 비교가 필요하다.
• 원소들의 교환 횟수에 따른 계산 복잡도.
• 메모리 사용량 (및 다른 컴퓨터 자원의 사용량). 특히 일부 정렬 알고리즘들은 제자리(in-place, 인 플레이스)이다. 정확히 말해 제자리 정렬은 정렬되는 항목 외에 O(1) 개의 메모리만 필요하며 O(log(n))개의 추가적인 메모리를 인플레이스로 간주한다.
• 재귀. 일부 알고리즘들은 재귀성을 띄거나 재귀성을 띄지 않을 수 있으며 다른 알고리즘들은 그 둘의 특성을 지닐 수 있다. (예: 머지 소트)
• 안정성: 안정적인 정렬 알고리즘들은 동일 키(예: 값)의 레코드의 상대적인 순서를 관리한다.
• 비교 정렬인지 아닌지의 여부. 비교 정렬은 비교 연산자를 통해 2개의 요소만을 비교함으로써 데이터를 검사한다.
• 일반적인 방식: 삽입, 교환, 선택, 병합 등. 교환 정렬에는 거품 정렬과 퀵 소트가 있다. 선택 정렬에는 셰이커 소트와 힙 소트가 있다.
• 알고리즘이 직렬인지 정렬인지의 여부. 이 토론의 나머지 부분은 거의 예외적으로 직렬 알고리즘에 집중하며 직렬 조작을 다룬다.
• 순응성: 입력을 미리 정리하는 일이 실행 시간에 영향을 미치는지의 여부. 이를 고려사항에 넣는 알고리즘들은 순응적이다.

위키백과 참고.

정렬 알고리즘 - 위키백과, 우리 모두의 백과사전

 

정렬알고리즘에는 정말 다양한 알고리즘이 존재한다.

그 가운데 가장 원시적인 방법으로 매번 '가장 작은 것을 선택' 하는 선택 정렬(Selection Sort) 알고리즘을 공부하면서 점점 복잡한 알고리즘을 공부해보려고 한다. 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면 전체 데이터의 정렬이 이루어진다. 흔히 데이터의 개수를 N이라고 표현하는데, 예제에서도 N = 10인 경우를 가정하겠다. 

선택 정렬

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

 

파이썬으로 작성한 소스코드는 다음과 같다.

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

for i in range(len(arr)):
  min_index = i # 가장 작은 원소의 인덱스
  for j in range(i+1,len(arr)): # 다음 원소부터 비교
    if arr[min_index]> arr[j]: # arr[min_index]가 arr[j]보다 크다면 
      min_index = j #j가 최솟값
  arr[i],arr[min_index] = arr[min_index],arr[i] #서로 값을 바꿔줌.

print(arr)

파이썬에서는 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 지원한다. 다른 프로그래밍 언어에서는 명시적으로 임시 저장용 변수를 만들어 두 원소의 값을 변경해야 하는 걸 알아두자.

 

선택 정렬의 시간 복잡도를 계산해보자.

선택 정렬은 N-1번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 비교 연산이 필요하다. 구현 방식에 따라서 사소한 오차는 있을 수 있지만 코드대로 구현했을 경우 연산 횟수는 N+(N-1)+(N-2)+.....+2로 볼 수 있다. 따라서 근사치로

N X(N+2) /2번의 연상을 수행한다고 가정한다. 빅오 표기법으로 간다히 O(N^2)이라고 표현할 수 있다. 

 

선택 정렬은 전과하고 처음으로 배운 정렬이었는데 이렇게 졸업 후 다시 하나하나 집어가면서 풀어보니 꽤나 새로웠던 것 같다. 라이브러리를 못쓰는 경우에 구현하는 일이 있겠지만.. 대부분의 코딩 테스트에서 sort 라이브러리를 지원하기 때문에 기억 속에서 잊힐뻔했다. 정말 매우 비효율적인 알고리즘이지만 가장 작은 데이터를 찾는 일이 있을 수도 있으므로.. 기억해두도록 하자.