정렬알고리즘 - Insertion Sort (삽입 정렬) | C, Python 코드 구현

 

계속해서 정렬알고리즘에 대하여 공부하고 있다. 오늘은 정렬 알고리즘 중 삽입정렬 insertion sort에 대하여 알아보겠다. 삽입정렬을 두 번째 인덱스부터 기준점으로 잡고 기준점에서 앞 데이터들과 비교하며 기준점 데이터를 삽입할 위치를 정하여 정렬하는 알고리즘이다.

출처: wikipedia

📌삽입정렬이란

1. 삽입정렬은 두 번째 index부터 시작하고, 이를 기준점으로 잡는다.
2. 해당 인덱스 앞에 있는 데이터들과 비교하여 기준점의 데이터의 값이 앞 데이터들보다 더 작으면, 기준점을 그 앞 데이터의 뒤 인덱스로 복사한다. (기준점 바로 앞에 있는 값들부터 하나하나 비교하며 기준점이 더 크면 swap한다고 볼 수도 있겠다.)
3. 기준점이 앞 데이터들 중에서 자신보다 더 큰 데이터를 만날 때까지 이를 반복하고, 큰 데이터를 만난 위치 바로 뒤에 기준점을 이동시킨다.

• 데이터 길이가 n이라면 기준점을 잡는 것은 n-1번 필요하다. 즉, n-1번의 turn을 돌아야한다.
• 그리고 각 turn에서 기준점과 그 앞 데이터들의 대소비교는 기준점의 index 번호의 값만큼 반복해주어야 한다. (기준점index-1부터 1까지)
• 대소비교를 맨 앞 index까지 끝까지 하지 않더라도, 기준점보다 큰 데이터를 만났다면 멈춘다.

 

pseudo code 구현

1. for index in range(len(data_list)-1) #n-1번의 기준점 잡기 (n-1번의 turn 필요)
2. ​ for index2 in range(index+1, 0, -1) #앞으로 하나씩 옮겨가며 기준점과 대소비교!
3. 반복문 안에서 data_list[index2]가 data_list[index2-1]보다 작으면 swap, 크면 두번째 for문 탈출 (앞으로의 조건체크를 더이상 진행할 필요 x)

📌알고리즘 구현 (C)

void insertion_sort(int *num_arr, int arr_len){

	int i, j, key;

	if (arr_len == 1)
		return;

	for (i = 1; i <= arr_len; i++){
		key = num_arr[i];
		for (j = i-1; j >= 0 && num_arr[j]>key; j--){
			num_arr[j + 1] = num_arr[j];
		}
		num_arr[j + 1] = key;
	}
}

 

📌알고리즘 구현 (Python)

def selection_sort(num_list):
    for i in range(1, len(num_list)):
        for j in range(i):
            if num_list[j] > num_list[i]:
                num_list[i], num_list[j] = num_list[j], num_list[i]
            else:
                break
    return num_list

 

📌알고리즘 분석

반복문이 2개이고, 각각의 반복문이 n 즉, len(data_list) 의 영향을 받으므로 시간복잡도는 $$O(n^2)$$이라고 할 수 있다.

완전정렬이 되어 있는 경우 두번째 for문은 돌지 않으므로 시간복잡도는 $$O(n)$$이다.