바로 전 글에서 검색 알고리즘 설명을 하다가 끝났습니다. 아무래도 제일 편하고 확실하게 검색하는 방법은 하나하나씩 확인을 해서 처음부터 끝까지 검색을 하는 방법입니다. 하지만 이 알고리즘에 단점도 있습니다. 바로 시간이 오래 걸린 다는 것입니다. 확실하지만 오래 걸리는 단점 때문에 다른 방법을 이용해서 검색하는 알고리즘 몇 개를 설명하려고 합니다.
이진 검색 (Binary Search)
시간 복잡도 : O(log n)
이 알고리즘을 이용하면 일반적인 검색 (Linear Search) 보 다보다 빠릅니다. 생각보다 간단합니다. 처음에 중간 index로 이동을 해서 값을 확인하고 찾는 값이 작으면 왼쪽에 있는 배열로 이동, 더 큰 값을 찾아야 하면 오른쪽 배열로 이동을 하면서 찾아가는 방식입니다.
예를 들어서,
배열 [1,3,5,7,9,11,13]에서 3이라는 값을 찾고 싶을 때, 먼저, index가 3인 곳에 가서 찾고 싶은 Value값이 3보다 작은지 큰지 확인을 합니다. 지금 예시에서는 작기 때문에 오른쪽이 아니라 왼쪽으로 이동을 합니다. 그럼 왼쪽 배열은 [1,3,5]가 됩니다. 그 중간은 3의 값을 가지므로 찾을 수가 있는 것입니다.
여기까지 읽으면서 의문점을 가지시는 분들이 계실 겁니다. 배열이 오름차순 혹은 내림차순으로 잘 정리된 배열 혹은 리스트면 가능하겠지만, 그냥 무작위로 들어간 경우에는 안된다라는 의심을 가질 수 있습니다. 맞습니다. 이 알고리즘은 잘 정리가 된 오름 혹은 내림 차순으로 정리가 된 경우에만 가능합니다. (정말로 큰 단점이 이죠...) 그래도 배열과 리스트가 정렬되어서 들어오는 경우에는 일반적인 Linear Search보다는 빠르게 찾을 수가 있습니다.
아 그리고 시간 복잡도에 대해 설명을 깜빡했네요. 간단하게 설명을 하겠습니다. 알고리즘 설명을 할 때 시간 복잡도는 위에 본 것처럼 O(log n) 혹은 O(n) 등등 여러 가지로 설명을 합니다. 간단하게 설명해서 n은 입력 값들입니다. 입력하는 n이 증가하게 되면 시간은 당연히 늘어날 것입니다. 그래서 이것을 통해서 입력하는 데이터와 알고리즘이 걸리는 시간의 관계를 표현하는 방법으로 사용됩니다. 일반적인 Linear Search인 경우는 O(n) 시간 복잡도를 가지는데, 데이터 입력이 늘어나면 정확하게 늘어난 입력만큼 걸리는 시간이 늘어나겠죠? 그래서 O(n)으로 표현을 합니다. 자세한 내용은 구글로 찾으면 더 자세히 확인이 가능합니다. (저는 그냥 외우면서 하다 보니까 정확하게 이해는 못 했습니다. 죄송합니다. 학교에서 시험문제로 종종 나옵니다. 시간복잡도가 뭐니 하면서..)
이번에는 Sort 알고리즘을 설명하겠습니다. 내림차순 혹은 오름차순으로 배열 혹은 리스트를 정렬하는 알고리즘을 말합니다. 일단 제일 간단한 Bubble Sort Algorithm을 설명하겠습니다. 모든 예시는 오름차순으로 나오게 하는 방식으로 하겠습니다. 혹시나 내림차순을 원하시면 간단하게 조건문을 변경해서 사용하시면 됩니다.
버블 정렬 (Bubble Sort Algorithm)
바로 오른쪽 옆에 있는 Index와 비교를 해서 자기 자신보다 작으면 바꾸고, 크면 그대로 있는 알고리즘입니다. 짧게 설명하려니까 어려워서 그림을 그려서 설명을 하겠습니다.
예시
|
3 |
5 |
2 |
9 |
15 |
1 |
6 |
4 |
위에처럼 8의 숫자가 배열 혹은 리스트에 들어가 있다고 봅시다. 그러면 먼저 맨 처음 index와 그다음 index를 비교합니다. 3과 5가 있습니다. 3보다 5가 크기 때문에 그대로 놔둡니다. 그 다음에 5와 2를 비교합니다. 이 경우 5가 2보다 크기 때문에 위치를 바꿉니다.
|
3 |
2 |
5 |
9 |
15 |
1 |
6 |
4 |
그리고 이제 5와 9를 비교합니다. 5가 9보다 작기 때문에 그대로 놔둡니다. 이렇게 해서 일단 처음부터 끝까지 쭉 움직이면 아래와 같이 배열 혹은 리스트가 바뀝니다.
|
3 |
2 |
5 |
9 |
1 |
6 |
4 |
15 |
이렇게 배열 혹은 리스트를 한 바퀴 돌면서 바꾼 다음 다시 똑같이 반복을 하면 됩니다. 언제까지 하면 되냐면 배열이 정렬이 될 때까지 하면 됩니다. 최악의 경우, 위의 과정을 8번 해야 합니다.
Python 코드
def BubbleSortAlgorithm(item_list):
for i in range(0,len(item_list)):
for j in range(0,len(item_list)-1):
if item_list[j] > item_list[j+1]:
temp_item = item_list[j]
item_list[j] = item_list[j+1]
item_list[j+1] = temp_item
item_list = [3,5,2,9,15,1,6,4]
print(item_list)
BubbleSortAlgorithm(item_list)
print(item_list)
출력 결과
결과가 잘 나오는 것을 확인할 수 있습니다.
선택 정렬 (Selection Sort Algorithm)
선택 정렬 방식은 최솟값을 찾아서 가장 앞 Index로 이동시키는 방식으로 정렬을 하는 알고리즘입니다. 이것도 마찬가지로 예시로 설명을 하겠습니다.
예시
(버블 정렬과 같은 값들을 쓰겠습니다.)
|
3 |
5 |
2 |
9 |
15 |
1 |
6 |
4 |
처음부터 끝까지 Linear Search를 하면서 가장 작은 값을 찾습니다. 그러면 1이라는 값이 가장 작고 Index가 5인 것을 알 수 있습니다. 그러면 1을 제일 처음으로 옮기면 됩니다.
|
1 |
3 |
5 |
2 |
9 |
15 |
6 |
4 |
그다음에는 index 1부터 끝까지 Linear Search로 찾으면서 가장 작은 값을 찾습니다. 그러면 값이 2가 가장 작고 위치가 index 3인 것을 알 수가 있습니다.
|
1 |
2 |
3 |
5 |
9 |
15 |
6 |
4 |
그러면 2를 Index가 1인 곳으로 옮기면 됩니다.
이렇게 계속 반복을 하면 마지막에는 오름차순으로 정렬이 됩니다.
Python 코드
def SelectionSortAlgorithm(item_list):
for i in range(0,len(item_list)):
min_value = item_list[i]
min_index = i
for j in range(i,len(item_list)):
if min_value > item_list[j]:
min_value = item_list[j]
min_index = j
del item_list[min_index]
item_list.insert(i,min_value)
item_list = [3,5,2,9,15,1,6,4]
print(item_list)
SelectionSortAlgorithm(item_list)
print(item_list)
출력 결과
버블 정렬과 마찬가지로 잘 오름차순 정렬이 된 것을 확인할 수 있습니다.
삽입 정렬 (Insert Sort Algorithm)
삽입 정렬이라는 정렬 방식이 있습니다. 이 방식은 맨 처음 Index의 값을 기준으로 다음 Index를 하나하나씩 비교를 하면서 알맞은 위치에 넣는 방식입니다. 역시 이렇게 말하면 이해가 어렵죠? 저도 뭐라고 하는지 잘 모르겠습니다. 아까와 마찬가지로 그림으로 설명을 하겠습니다.
예시
아까와 똑같은 배열을 사용하겠습니다.
|
3 |
5 |
2 |
9 |
15 |
1 |
6 |
4 |
일단 제일 처음에 존재하는 3을 기준으로 합니다. 그리고 다음 index에 있는 5를 봅니다. 5가 3보다 크니 그대로 놔둡니다. 그리고 다음 Index인 2를 봅니다. 2는 3,5를 봤을 때 가장 작으므로 가장 앞으로 이동을 합니다.
|
2 |
3 |
5 |
9 |
15 |
1 |
6 |
4 |
그다음 Index에 존재하는 9를 확인했는데 2,3,5중에서 가장 크므로 그냥 놔두고 다음을 봅니다. 다음에는 15가 있는데 마찬가지로 2,3,5,9중에서 가장 크기 때문에 그대로 놔두고 다음을 봅니다.
그다음에는 1이 있는데 2,3,5,9,15중에서 가장 작은 값이므로 제일 앞으로 이동을 합니다.
|
1 |
2 |
3 |
5 |
9 |
15 |
6 |
4 |
위에처럼 배열 혹은 리스트가 바뀌게 됩니다. 그 다음 값인 6의 경우에는 1,2,3,5,9,15중에서 5와 9 사이에 존재하는 수이기 때문에 5와 9 사이로 이동시킵니다.
|
1 |
2 |
3 |
5 |
6 |
9 |
15 |
4 |
마지막으로 맨 마지막에 있는 값을 보면 4입니다. 이 숫자는 1,2,3,5,6,9,15에서 3과 5 사이에 들어가는 숫자이므로 3과 5 사이에 넣어 주시면 됩니다.
|
1 |
2 |
3 |
4 |
5 |
6 |
9 |
15 |
이렇게 해서 깔끔하게 오름차순으로 정렬이 되었습니다.
Python 코드
def InsertSortAlgorithm(item_list):
for i in range(0,len(item_list)-1):
if i == 0:
if item_list[i] > item_list[i+1]:
temp_item = item_list[i]
item_list[i] = item_list[i+1]
item_list[i+1] = temp_item
else:
temp_item = item_list[i+1]
for j in range(0,i):
if item_list[j] < temp_item and temp_item < item_list[j+1]:
del item_list[i+1]
item_list.insert(j+1,temp_item)
break
elif item_list[j] > temp_item:
del item_list[i+1]
item_list.insert(0,temp_item)
break
item_list = [3,5,2,9,15,1,6,4]
print(item_list)
InsertSortAlgorithm(item_list)
print(item_list)
출력 결과
이것도 마찬가지로 위에 2개의 정렬과 마찬가지로 오름차순으로 정렬이 잘 된 것을 확인했습니다.
구글로 찾아보시면 정렬하는 알고리즘은 위에 제가 설명한 것보다 더 좋고 유명한 알고리즘이 존재합니다. 하지만 여기서는 모든 정렬 알고리즘을 정리하지는 않겠습니다. (그냥 제가 귀찮아서 안 하는 게 가장 큰 이유이지만, 대충 여기까지 따라 하는데 문제가 없으면 나머지 정렬 알고리즘을 이해하고 구현하는데 큰 무리가 없을 것입니다.)
여기서 저는 위에 3가지 정렬 방식이 걸리는 시간을 계산해 보겠습니다.
Python 코드
start_bubble = time.time()
item_list = [3,5,2,9,15,1,6,4]
print(item_list)
BubbleSortAlgorithm(item_list)
print(item_list)
print("Bubble : ", time.time() - start_bubble)
start_select = time.time()
item_list = [3,5,2,9,15,1,6,4]
print(item_list)
SelectionSortAlgorithm(item_list)
print(item_list)
print("Select : ", time.time() - start_select)
start_insert = time.time()
item_list = [3,5,2,9,15,1,6,4]
print(item_list)
InsertSortAlgorithm(item_list)
print(item_list)
print("Insert : ", time.time() - start_insert)
출력 결과
이렇게 보면 Insert가 가장 적게 걸리는 것을 확인할 수 있습니다. 여기서 한 가지 집고 넘어가야 하는 게 있는데, 위에 나온 걸리는 시간은 변합니다. 상황이네 컴퓨터나 무슨 프로그램을 켜고 있는지 여러 가지 상황에 따라서 달라집니다.
바로 다시 프로그램을 돌렸는데, 바로 전에 돌렸을 때 걸리는 시간하고 값이 다르게 나오는 것을 확인할 수 있습니다. 만약에 걸리는 시간을 비교하는 경우에는 이런 상황도 알고 평균을 이용하든 위에 처럼 같이 돌리든 해서 걸리는 시간을 비교하시면 됩니다.
'Python' 카테고리의 다른 글
| 10. Python 기초이기 보다는 전반적인 알고리즘 (0) | 2019.06.26 |
|---|---|
| 09. Python 기초 유용한 라이브러리 (0) | 2019.06.25 |
| 08. Python 기초 기본 함수 (0) | 2019.06.24 |
| 07. Python 기초 간단한 문제들 (0) | 2019.06.23 |
| 06. Python기초 Draw Graph(그래프 그리기) (0) | 2019.06.22 |
