알고리즘(3) - 탐색, 정렬

안녕하세요.

 

오늘은 대표적인 알고리즘인 탐색 알고리즘과 정렬 알고리즘에 대해서 정리해보려고 합니다.

 

 

탐색 알고리즘

 

탐색 알고리즘 이란

: 원하는 데이터를 찾아내는 알고리즘 입니다.

 

linear search (선형 탐색)

 

• 앞에서 부터 차례대로 탐색하는 알고리즘
• 반복문을 사용하여 데이터만큼 검색을 진행합니다.

 

Binary search (이분 탐색)

 

• 범위를 반씩 줄여나가면서 탐색하는 알고리즘 ( 시간 복잡도 = logn )
• 이미 데이터가 정렬된 상태에서만 적용 가능하다.
• 복잡한 계산을 할때에는 반복이 많이 필요하기 때문에 시간과 메모리를 크게 잡아먹는다.

 

 

 

반복 정렬 알고리즘 ( lterative sorting )

 

Selection Sort ( 선택 정렬 )

• 전체 배열을 한번 반복하면서 가장 작은 수를 비교하여 가장 왼쪽 인덱스부터 값을 교환하면서 채워나가는 방식
• 서로 이웃하지 않은 노드를 교환함으로 불안정적입니다.
• 시간 복잡도 : O(n^2)

코드 구현

# 선택 정렬 구현
for i in range(0,len(li)-1):

        cur_idx = i
        smallest_idx = cur_idx

        for j in range(cur_idx+1,len(li)):
            smallest_idx = j
            if li[smallest_idx] > li[cur_idx]:
                continue
            else:
                li[smallest_idx], li[cur_idx] = li[cur_idx], li[smallest_idx]
return li

❄️ 코드를 쉽게 이해하기 어렵기 때문에 li = [ 10, 5, 7, 2, 8, 1 ] 과 같은 예시를 통해서 손으로 써보면서 작동해보면 어떻게 작용되는 원리인지 쉽게 이해할 수 있습니다. 

 

1) 첫번째 인덱스 10의 값과 두번째 인덱스 5의 값이 처음으로 비교됩니다.

2) 5가 10보다 작음으로 두 인덱스의 값이 교환됩니다.

3) 그러면 배열이 [5,10,7,2,8,1,] 가 되고 다시 첫번째 인덱스 5의 값과 세번째 인덱스값 7이 비교가 됩니다.

4) 첫번째 인덱스의 값이 더 적음으로 다음으로 넘어가 5와 2가 비교됩니다.

5) 첫번째 인덱스의 값이 큼으로 교환이 이루어져 [2,10,7,5,8,1,] 이런 배열로 정렬이 됩니다.

6) 계속해서 비교를 통해 교환을 하면 최종적으로 첫번재 루프가 지났을 때 [1,10,7,5,8,2]로 정렬이 됩니다.

 

이렇게 예시를 들어서 보면 전체적인 루프를 통해 전체 인덱스에 작은 값 순서대로 정렬이 되는 것을 확인 할 수 있습니다.

 

그러나 예시와 같이 여러번의 교환과 루프가 2번 사용됨에 따라 비효울적인 방법입니다.

 

 

Insertion Sort ( 삽입 정렬 )

• 선택 정렬과 달리 왼쪽부터 작은 수로 채워나가는 형식이 아닙니다.
• 특정한 수가 왼쪽의 인덱스와 비교하면서 자신보다 큰 수 일 경우 교환하고, 작은 수면 루프가 끝나는 형태입니다.
• 시간복잡도는 이미 정렬되어있는 경우에는 O(n), 반대로 정렬되어있던 경우에는 O(n^2)가 됩니다.

코드 구현

# 삽입정렬 구현
def insertion_sort(li) :
	for cur_idx in range(len(li)): #전체 배열울 반복하는 루프
        prev_idx = cur_idx -1
        cur_val = li[cur_idx]
        while prev_idx>=0 and li[prev_idx]> cur_val: # 이전 인덱스 값과 현재 값을 비교하는 루프
            li[prev_idx+1]= li[prev_idx] 
            prev_idx = prev_idx-1
        li[prev_idx+1] = cur_val  
    return li

❄️ li = [ 10, 5, 7, 2, 8, 1 ] 예시를 통해 살펴봅시다.

 

1) 첫번째 루프에서 첫번째 인덱스 10은 넘어가게 됩니다. ( 왼쪽에 비교할 인덱스가 0 보다 작습니다 )

2) 두번째 루프에서 두번째 인덱스 5는 첫번째 인덱스와 비교하여 교환이 이루어집니다. li = [5,10,7,2,8,1]

3) 교환 후 왼쪽에 비교할 인덱스가 없기에 다음 루프로 넘어갑니다.

4) 세번째 루프에서 세번째 인덱스 7은 두번째 인덱스 10과 비교를 통해 교환을 하게 되고 다시 첫번재 인덱스와 비교를  해봅니다.

5) 첫번째 인덱스보단 큰 수 이기 때문에 li = [5,7,10,2,8,1]  가 됩니다.

 

삽입정렬은 소량의 데이터를 정렬하기위한 효율적인 알고리즘 입니다. 

 

 

Bubble Sort ( 버블 정렬 )

• 서로 이웃한 원소의 크기를 비교하여 교환을 반복하는 알고리즘 입니다.
• 시간 복잡도는 O(n^2)로 매우 비효율적이다.
• 그러나 이웃노드만 교환을 함으로 안정적인 방식이다.
• 삽입 정렬과 선택정렬과 다르게 마지막 인덱스를 최대값을 채워넣는 방식입니다.

코드 구현

# 버블 정렬 구현
def bubble_sort(li):
	length = len(li) -1
    for i in range(length): # 이웃한 노드를 비교함으로 마지막에서 두번째 인덱스까지만 해도 됩니다.
        for j in range(length-i): # 맨 오른쪽에 확정되는 수를 제외하는 루프
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
    return li

❄️ li = [ 10, 5, 7, 2, 8, 1 ] 예시를 통해 살펴봅시다.

 

1) 첫번째 루프가 0 일 때, 첫번째 인덱스와 두번째 인덱스의 값비교, 첫번재 인덱스 값이 더 큼으로 교환

2) 두번째, 세번째, 네번째 차례대로 비교해서 왼쪽의 인덱스 값이 더 큰경우 교환을 이룹니다.

3) 첫번째 루프를 통과하면 li = [5,7,2,8,1,10] 이 됩니다.

4) 두번째 루프를 들어가면 마지막 인덱스인 10은 비교되지 않습니다.

 

 

위의 코드 구현과 예시를 통해서 어떻게 정렬이 구동하고 작용되는 지 보았습니다.

 

이렇게 코드를 보고 원리를 파악하면 이해가 되지만 또 자신이 다시 코드를 구현하려고 보면 헷갈리기 쉽습니다.

 

그래서 다시 한번 코드 부분을 보지 않고 자신이 직접 만들어보는 시간도 가져보세요.