[2. 정렬] 기본적인 정렬 알고리즘

정렬 알고리즘 종류

• Bubble Sort, Selection Sort, Insertion Sort(간단하지만 느림)
• Merge Sort, Quick Sort, Heap Sort(빠름)
• Radix Sort(매우 빠름)

 

1. Selection Sort(선택 정렬)

1) 정렬 과정

⓪하나의 원소만 남을 때 까지 아래 루프를 실행한다.($O(n-1)$)

- ①최대값 원소를 찾는다($O(n-1), O(n-2) \cdots O(1)$)

- ②맨 오른쪽 원소를 최대값 원소로 교체한다($O(1)$)

- ③정렬 대상인 배열에서 맨 오른쪽 원소를 제한다

 

Selection Sort 흐름

2) 실행시간

⓪루프는 $n-1$번 실행하며 ①최대값 원소를 찾는 과정은 $n-1, n-2,,, 1$번 실행한다.

시간복잡도: $T(n) = (n-1) + (n-2) + \cdots + 1 = O(n^{2})$

 

3) Selection Sort Python 코드

def selection_sort(array):
	assert type(array) == list
    n = len(array)
	for last_idx in reversed(range(1, n)):  # reversed를 사용하여 iteraion 횟수 및 맨 오른쪽 index 한꺼번에 처리
    	max_idx = array[:last_idx+1].index(max(array[:last_idx+1]))  # 각 스텝마다 맨 오른쪽 제하여 정렬
        array[last_idx], array[max_idx] = array[max_idx], array[last_idx]  # python은 내장으로 swap 기능 제공함
        
    return array

 

 

2. Bubble Sort(거품 정렬)

1) 정렬 과정

⓪배열길이-1 만큼의 횟수 만큼 아래 루프를 실행한다.($O(n-1)$)

- ①인접한 원소를 두개씩 비교하여 큰 수를 오른쪽으로 옮긴다(window) ($O(1)$)

- ②위 window를 배열의 처음부터 끝까지 이동시킨다($O(n-1),O(n-2) \cdots O(1)$)

 

Bubble Sort 흐름

2) 실행시간

⓪루프는 $n-1$번 실행하며 ①,②인접한 두 원소끼리 비교하는 과정은 $n-1, n-2,,, 1$번 실행한다.

시간복잡도: $T(n) = (n-1) + (n-2) + \cdots + 1 = O(n^{2})$

 

3) Bubble Sort Python 코드

def bubble_sort(array):
	assert type(array) == list
    n = len(array)
	for last_idx in reversed(range(1,n)):  # n-1번 실행
    	for i in range(last_idx):  # n-1, n-2, ... 1번 실행
        	if array[i] > array[i+1]
            	array[i], array[i+1] = array[i+1], array[i]
     
    return array

 

 

3. Insertion Sort(삽입 정렬)

1) 정렬 과정

⓪ 배열의 2번째 원소부터 마지막 원소까지 아래 루프를 실행한다.($O(n-1)$)

- ①$i$번째 원소를 $i$번째 까지의 배열에서 정렬순서상 알맞은 위치에 삽입한다($O(n-1), O(n-2) \cdots $)

- (각 loop에서 보는 item 앞쪽의 배열은 정렬된 상태임)

 

Insertion Sort 흐름도

2) 실행시간

⓪루프는 $n-1$번 실행하며 ①알맞은 위치를 찾는 과정은  $1, 2 \cdots n-1, n-2$번 실행한다.

 

3) Insertion Sort Python 코드

def insertion_sort(array):
	assert type(array) == list
    n = len(array)
    for look_idx in range(1, n):  # n-1번 실행
    	current_element = array[look_idx]
        for i in reversed(range(look_idx)):
        	if array[i] > current_element:  # look_idx 이전까지의 원소들은 정렬이 되어있는 상태임
            	array[i], array[i+1] = array[i+1], array[i]
    
    return array

 

 

 

[References]

• 권오흠 교수, 알고리즘(강의 링크)