알고리즘 - 선택정렬, 버블정렬, 삽입정렬 (Selection sort, Bubble sort, Insertion sort)

정렬은 알고리즘 문제는 물론 실제 코드에서도 상당히 사용도가 높은 기능이다. 또한 구현할 수 있는 방법도 상당히 

다양하며 그에 따라 수행시간 역시 상이해, 실력있는 개발자는 각 상황에 적합한 정렬 알고리즘을 사용할 수 있어야한다.

 

정렬 알고리즘들은 간단한 정렬 알고리즘인 선택정렬, 버블정렬, 삽입정렬과

고급 정렬 알고리즘인 병합 정렬, 퀵 정렬, 계수 정렬, 기수 정렬 등이 존재한다

오늘은 간단한 알고리즘에 속하는 선택정렬, 버블정렬, 삽입정렬을 정리해 보겠다.

 

1) 선택 정렬

 

원리:

1. 각 루프마다 최대(혹은 최소) 원소를 찾는다

2. 최대(혹은 최소) 원소와 마지막 원소를 교환한다

3. 탐색 범위를 1 줄인다

이를 범위가 1이 될 때까지 반복한다

 

코드(파이썬):

def Selectionsort(a,n):
	for i in range(n-1,1,-1):
    	index = 0
        for j in range(i):
        	if a[index] < a[j]:
            	index = j
        a[index],a[i] = a[i],a[index]

 

시간 복잡도:

최악의 경우 - O(n^2)

평균적인 경우 - O(n^2)

최선의 경우 - O(n^2)

 

 

2) 버블 정렬

 

원리:

1. 각 루프마다 범위 내 모든 원소를 순회하며 인접한 두 원소 중 앞의 원소가 더 작은 경우 두 원소를 교환한다

2. 탐색 범위를 1 줄인다

3. 한 루프를 돌며 한번도 교환이 일어나지 않았을 경우, 정렬된 상태이기에 알고리즘을 종료한다

 

코드(파이썬):

def Bubblesort(a,n):
	for i in range(n-1,1,-1):
    	sorted = True
        for j in range(i-1):
        	if a[j] > a[j+1]:
            		a[j],a[j+1] = a[j+1],a[j]
                	sorted = False
	if sorted:
    		break

 

시간 복잡도:

최악의 경우 - O(n^2)

평균적인 경우 - O(n^2)

최선의 경우 - O(n)

 

3) 삽입 정렬

 

원리:

1. n번째 루프에서 a[0]부터 a[n-1]까지는 정렬되어 있으며 그 이후부터는 정렬되어 있지 않다

2. a[0]부터 a[n-1]를 순회하며 a[n]을 적절한 위치에 삽입한다

3. n을 1 증가시킨다

 

코드(파이썬):

def Insertionsort(a,n):
	for i in range(1,n-1):
    	temp = a[i]
        for j in range(i-1,0,-1):
        	if a[j] > temp:
            		a[j+1] = a[j]
		else:
            		break
        
        a[j+1] = temp

 

시간복잡도:

최악의 경우 - O(n^2)

평균적인 경우 - O(n^2)

최선의 경우 - O(n)