[Algorithm] 정렬 알고리즘 정리하기 (1)

정렬 알고리즘이 중요한 이유

• 많은 알고리즘에서 정렬은 필수 전처리 단계로 사용된다. 
• 정렬된 데이터는 이진 탐색처럼 빠른 탐색 알고리즘을 사용할 수 있다. 
• 사람이나 시스템이 데이터를 해석하기 더 쉬워진다. ex. 시간순 , 크기 순, 알파벳 순
• 정렬을 통해서 중복된 값들을 모아 놓을 수 있으므로, 효율적으로 중복 제거를 할 수 있으며 그룹 처리에 유리하다. 

 

버블 정렬 Bubble Sort

버블 정렬은 한번 순회할때 정렬되지 않은 값들중에서 가장 큰 값을 찾아서 맨 뒤로 보낸다. 맨 첫번째 정렬 시도에서는 가장 큰 값을 찾아서 배열의 맨 뒤로 보내고, 두번째 정렬시도에서는 두번째로 큰 값을 찾아서 맨 뒤에서 두번째로 보낸다. 

1. 공간 복잡도 : O(1)

• 별도의 추가 공간 없이 주어진 배열 안에서 크기 비교와 swap 이 일어난다. 

2. 시간 복잡도 : O(N**2)

모든 원소에 접근해야 하므로 O(N)이 걸리며, 한번의 루프에서 이웃 값들을 대소 비교하며 swap해 나가야 하므로 여기서 또 O(N)의 시간 복잡도가 걸리게 된다. 따라서 최종적으로는 O(N**2)의 시간복잡도가 걸리게 된다. 

arr = [6, 5, 1, 7, 2, 3, 9, 8, 4]

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i): # 0, 1, 2, 3 | 0, 1, 2 | 0, 1 | 0
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    
print("Unsorted numbers:", arr) # Unsorted numbers: [6, 5, 1, 7, 2, 3, 9, 8, 4]
bubble_sort(arr)
print("Sorted numbers", arr) # Sorted numbers [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

선택 정렬 

---

References 

• https://www.geeksforgeeks.org/python-program-for-bubble-sort/