태야

Python Code

def insert_sort(x):
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1] = x[j]  # 비교 값을 오른쪽으로 이동
            j = j - 1 # 앞쪽 값을 비교하기 위해 -1
        x[j+1] = key
    return x

삽입 정렬은 현재 값을 기준으로 앞쪽의 값들과 비교해 자기 자리에 삽입하는 정렬 알고리즘이다. 

삽입 정렬의 구체적인 알고리즘은 다음과 같다.

- 삽입 정렬은 두 번째 자료부터 알고리즘을 수행한다.

- 두 번째 자료(인덱스)부터 시작해 그 앞쪽의 값들과 비교해 삽입될 자리를 찾는다.

- 자리를 찾은 후 현재 값을 넣은 다음 나머지 값들은 한 칸씩 이동시킨다.(오른쪽)

- 세 번째 자료가 현재 값이 되고, 앞쪽 값인 첫 번째, 두 번째 값과 비교해 자리를 찾는다.

- 자리를 찾아 삽입되고 다른 값들은 옆으로 이동시킨다.

- 네 번째 값도 마찬가지로 왼쪽의 값들(1,2,3번째 값)과 비교해 삽입될 자리를 찾는다.

- 나머지 값들도 같은 방식으로 알고리즘이 수행된다.

위의 코드에서 보면 key가 선택된 값이 되고 j 인덱스가 왼쪽의 비교하는 값들이 된다.

j 번째 비교 값과 key 값을 비교했을 때 key가 작다면 j 번 값을 +1(즉 오른쪽으로 하나씩 이동) 시킨다. 계속 앞쪽의 값들과 비교해 비교 값들을 한 칸씩 오른쪽으로 이동시킨다.

만약 key 값이 더 크거나, 젤 앞의 값까지 비교가 끝나면 그 자리에 현재 값(key)을 넣어준다. 

삽입 정렬의 시간 복잡도

- 두 번째 값으로 시작 시 첫 번째 값과 비교 -- 1번

- 세 번째 값은 첫 번째, 두 번째랑 비교 -- 2번

- n-1 번째 값은 1, 2, 3,... , n-2 번째 비교 -- (n-2)번

- n 번째 값은 -- (n-1)번

즉, 1 + 2 + 3 + ... + n-2 + n-1 = n(n-1) /2 가 돼서, 시간 복잡도가 최악의 경우 O(n^2)가 된다. 최선의 경우는 자료가 다 정렬된 경우이고 이때는 시간 복잡도가 O(n)이 된다. 왜냐하면 각 자리의 값마다 왼쪽의 값 하나만 비교하면 되기 때문이다. 따라서 삽입 정렬은 n값이 커질수록 복잡도가 커져 알고리즘 성능이 떨어진다.

 알고리즘, 자료구조 - 순차 탐색(선형 탐색) 

순차 탐색이란?

리스트 또는 배열 안에 있는 첫 번째 자료부터 하나씩 비교하면서 원하는 데이터를 찾아가는 알고리즘이다. 데이터를 따로 조작할 필요가 없어 단순하지만 비효율적이라는 단점을 지니고 있다. 추가로 순차 탐색은 단방향으로 탐색을 수행하기 때문에 선형 탐색(Linear Search)라고도 부른다.

순차 탐색은 최악의 경우에 최대 n번의 비교를 필요로 하기에 시간 복잡도는 O(n)이 된다.

이는 데이터가 n개가 되면 그에 따른 연산 수도 n개를 따라가기 때문에 자료수가 많아질수록 연산의 속도가 느리다는 단점이 있다.

예제

# 리스트에서 특정 숫자의 위치 찾기

def search_num(a, x):
	n = len(a)
    for i in range(0, n): #리스트 a의 모든 값에 대해 반복
    	if x == a[i] : 	# 찾는 숫자와 값이 일치하면
        	return i	# 인덱스 값 반환
    
    return -1
    
a = [17, 92, 18, 33, 58]
print(search_num(a, 18)) # 2 출력
print(search_num(a, 900)) # -1 출력(해당 값이 없기에)

# 학생 번호를 입력시 해당하는 학생의 이름을 반환
def find_student(number, stuNo, stuName):
    num = len(stuNo)
    for i in range(0, num):
        if(stuNo[i] == number):
            return stuName[i]

    return "해당 학생은 없습니다."


stu_no = [39, 14, 67, 103]
stu_name = ["Justin", "John", "Mike", "Summer"]

print(find_student(39, stu_no, stu_name)) #출력 - "Justin"