[Algorithm] 정렬(1) - 선택정렬, 삽입 정렬

! 계속해서 이것이 코딩 테스트다 with 파이썬 공부 중

1.정렬?

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

정렬 알고리즘이 중요한 이유는 이진 탐색의 전처리 과정이기도 하고, 정렬 알고리즘의 종류가 많은데 상황에 적절하지 못한 정렬 알고리즘을 이용할 경우 프로그램이 비효율적으로 동작하며 이에 따라 필요 이상으로 시간을 많이 소요되게 된다. 그래서 정렬 알고리즘들을 공부하다보면 알고리즘 효율의 중요성에 대해 많이 깨닫게 된다고 한다.

2. 선택정렬

선택 정렬은 간단하게 매번 '가장 작은 것을 선택'하여 정렬하는 방식 이라고 생각하면 된다.

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하면, 전체 데이터의 정렬이 이루어진다.

그림을 통해 자세하게 알아보도록 하자.

• 1단계
  
  위의 그림에서 제일 작은 데이터를 선택한다. 여기서는 '1'이 선택되며, 이 1을 맨 앞에 있는 데이터 '7'과 바꾼다.

• 2단계
  
  정렬된 1을 제외하고 이후 데이터 중 가장 작은 데이터인 '2'를 선택하여 처리되지 않은 데이터 중 가장 앞에 있는 '5'와 바꾼다.

• 3단계
  
  2단계와 마찬가지로 처리되지 않은 데이터 중 가장 작은 데이터인 '3'을
  '4'와 바꿔준다.

• 결과
  

계속해서 단계를 진행해 나가면 다음과 같이 정렬이 이루어진다.

즉 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 맨 마지막 데이터를 제외하고 이루어지기 때문에 N-1번 반복하여 정렬을 완료한다.

• 소스코드

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

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] #위치를 바꿔준다.(스와프)

맨 앞의 데이터를 가장 작은 원소의 인덱스로 놓고, for 반복문을 통해 계속해서 뒤에 있는 데이터와 비교하여 제일 작은 데이터의 인덱스를 min_index 변수의 값으로 넣는다.
그 뒤 제일 작은 데이터와 맨 앞에 데이터를 바꿔주는 작업을 반복하는 것이다.

선택 정렬 시간 복잡도

선택 정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하며, 연산은 N + (N-1) + (N-2) + ... + 2 이다. 따라서 O(N^2)으로 표현할 수 있다.

3. 삽입 정렬

위에 공부했던 선택 정렬의 경우 알고리즘 문제 풀기에는 시간 복잡도가 O(N^2)이기 때문에 느린 편이다. 그러면 삽입 정렬에 대해 한번 알아보자

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'하는 것

삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다. 그 이유는 필요할 때만 위치를 바꾸기 때문이다. 또한 삽입 정렬은 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문에 두 번째 데이터부터 정렬을 시작한다!

그림을 통해 자세하게 알아보자

• 1단계
  

위에서 말한대로 선택 정렬은 두 번째 데이터부터 정렬을 시작한다. 첫 번째 데이터인 '7'은 정렬되어 있다고 판단 하고, 두 번째 데이터인 '5'가 어디로 들어가야 할지 판단한다. 우리는 오름차순 정렬을 하고 있으므로 '5'의 경우 '7'보다 작기 때문에 '7'의 왼쪽으로 들어가게 된다.

• 2단계
  

다음으로 '4'가 어떤 위치에 들어갈지 판단한다. '4'의 경우 '5'와 '7'보다 작기 때문에 '5'의 왼쪽으로 들어가게 된다.

• 3단계
  

다음으로 '6'이 어떤 위치에 들어갈지 판단한다. '6'의 경우 '4'와 '5'보다 크고 '7'보다 작기 때문에 '5'와 '7' 사이에 삽입한다.

• 결론
  

위와 같은 과정을 N-1번 계속해서 반복할 경우 다음과 같이 모든 데이터가 정렬된다. 이때 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 특징이 있다.

• 소스코드

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

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

삽입 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 O(N^2)이다. 하지만 현재 리스트의 데이터가 거의 정렬되어 있는 최선의 상태인 경우 O(N)의 시간 복잡도를 가진다.

다음은 퀵 정렬과 계수 정렬에 대해 공부해 보겠다!