정렬 - 버블정렬, 삽입정렬, 병렬 정렬

⭐들어가면서⭐

내가 왜 열심히 살지..?

🎯 목표

📌 버블 정렬
📌 삽입 정렬
📌 병렬 정렬

📌 버블 정렬

버블 정렬이란

숫자 리스트를 순회하면서 각 숫자를 다음 숫자와 비교하고, 순서가 틀렸으면 다음 숫자와 바꾸는 정렬 방법이다.

[3 1 5 9 6] 버블 정렬 시작
[(1 3) 5 9 6] -> [1 (3 5) 9 6] -> [1 3 (5 9) 6] -> [1 3 5 (6 9)] 

버블 정렬의 첫번째 순회 결과 : 가장 큰 숫자가 리스트의 마지막으로 온다.
즉, 가장 큰 숫자를 뒤로 보낸다.

🤔 그러면 가장 작은 숫자는...?

[9 6 5 3 1] 버블 정렬 시작
[(6 9) 5 3 1] -> [6 (5 9) 3 1] -> [6 5 (3 9) 1] -> [6 5 3 (1 9)] 

👍 안정적이다.

버블 정렬 구현 코드

def bubble_sort(a_list):
    temp = 0
    for i in range(len(a_list)-1):
        for j in range(len(a_list)-1):
            if a_list[j] > a_list[j+1]:
                temp = a_list[j]
                a_list[j] = a_list[j+1]
                a_list[j+1] = temp

    return a_list

a_list = [9,5,3,1,6]
bubble_sort(a_list)
print(a_list)

➕ temp 변수없이?

a_list[j],a_list[j+1] = a_list[j+1],a_list[j]

알고리즘의 효율을 더 높이기 : 맨 뒤의 숫자는 비교 🙅‍

어처피 맨 뒤 숫자는 가장 큰 숫자이고 이미 정렬이 되어있기 때문에 비교 할 필요 없다.

def bubble_sort_1(a_list):
    temp = 0
    for i in range(len(a_list)-1):
        for j in range((len(a_list)-1) - i):  # 한번 실행될때마다 비교하는 횟수가 비례해서 줄어든다.
            if a_list[j] > a_list[j+1]:
                a_list[j],a_list[j+1] = a_list[j+1],a_list[j]

    return a_list

🔍 실제 과정 살펴보기

[9 6 5 3 1] 버블 정렬 시작

1단계) # 총 네번의 과정
[(6 9) 5 3 1] -> [6 (5 9) 3 1] -> [6 5 (3 9) 1] -> [6 5 3 (1 9)] 
2단계) # 총 세번의 과정
[(5 6) 3 1 9] -> [5 (3 6) 1 9] -> [5 3 (1 6) 9]
3단계) # 총 두번의 과정
[(3 5) 1 6 9] -> [3 (1 5) 6 9]
4단계) # 총 한번의 과정
[1 3 5 6 9]

한번 더 최적화하기

만약에 단계를 거쳤는데 한번도 숫자를 바꾸지 않았다면...? -> 정렬할거리가 없다!!

🔍 성능 비교

(500개의 리스트 비교)

(5천개의 리스트 비교)

오 재밌다...

📌 삽입 정렬

삽입 정렬이란

리스트를 둘로 나누고, 정렬된 카드에 정렬되지 않은 카드를 적절한 위치에 삽입한다.
오른쪽에 있는 카드를 하나씩 꺼내 정렬 규칙에 따라 왼쪽에 정렬된 카드들 사이에 삽입한다.

[6 5 8 2] 정렬
1) 맨 왼쪽 정렬 : [(5 6) 8 2] -> 왼쪽 절반 정렬, 오른쪽 절반 정렬 x
2) 오른쪽 숫자 중 첫번째 삽입 : 이전 숫자와 비교
[5 6 (8) 2] -> [5 6 8 2]
3) 오른쪽 숫자 중 첫번째 삽입 : 이전 숫자와 하나씩 비교
[5 6 8 (2)] -> [2 5 6 8]

삽입정렬을 코드로 나타내기

def insertion_sort(a_list):
    left = 0
    for right in range(1,len(a_list)):
        left = right-1
        while a_list[right] < a_list[right] and right > 0:
            a_list[right],a_list[left] = a_list[left],a_list[right]
            right -= 1
            left -= 1
    return a_list

삽입 정렬의 쓰임

거의 정렬된 리스트에서는 O(N)으로 버블 정렬 보다는 효율적이다.

📌 병렬 정렬

병렬 정렬이란

재귀를 이용한 정렬 방법!
리스트를 가장 작은 단위로 나누는 if문과 리스트를 정렬하는 문으로 구성이 되어있다.
요소가 한개인 리스트와 또 다른 요소가 한개인 리스트를 병합한다.
요소가 두개인 정렬된 리스트와 요소가 두개인 정렬된 리스트를 병합한다.
각 리스트의 첫번째만을 비교한다. 🤔 각 리스트의 가장 적은 요소는 맨 앞인 것을 보장!!

[3] [6] [9] [2]
[3 6]   [2 9]
======================
[(3) 6] [(2) 9]
[2]
======================
[(3) 6] [(9)]
[2 3]
======================
[(6)] [(9)]
[2 3 6]
======================
[2 3 6 9]

병렬 정렬의 코드

# 병합 정렬:
def merge_sort(a_list):
    if len(a_list) > 1:
        # 파이썬의 //는 정수 몫을 구하는 연산자
        mid = len(a_list) // 2
        left_half = a_list[:mid]
        right_half = a_list[mid:]
        merge_sort(left_half)
        merge_sort(right_half)


        left_ind = 0
        right_ind = 0
        alist_ind = 0

        while left_ind < len(left_half) and right_ind < len(right_half):
            if left_half[left_ind] <= right_half[right_ind]:
                a_list[alist_ind] = left_half[left_ind]
                left_ind += 1
            else: #오른쪽 첫번째 요소가 더 작은 경우
                a_list[alist_ind] = right_half[right_ind]
                right_ind += 1

            alist_ind += 1

        while left_ind < len(left_half):
            a_list[alist_ind] = left_half[left_ind]
            left_ind += 1
            alist_ind += 1

        while right_ind < len(right_half):
            a_list[alist_ind] = right_half[right_ind]
            right_ind += 1
            alist_ind += 1
    return a_list


a_list = [6,3,2,10,-10]
merge_sort(a_list)
print(a_list)

while문의 구성을 기억하자

while left_ind < len(left_half) and right_ind < len(right_half):
	...
while left_ind < len(left_half):
	...
while right_ind < len(right_half):
	...

병합 정렬의 쓰임

• 시간 복잡도 : O(n log n)로 효율적이다.
• 분할 정복 알고리즘에 사용할 수 있다.

➕ 파이썬의 정렬 알고리즘

sorted 함수

• 매개변수를 통해, 리스트를 길이 별로, 혹은 내림차순으로 반환한다.
• 새로운 리스트를 반환한다
  ⭐ 따라서 반환값을 저장할 변수가 꼭 필요하다.

list_1 = [1,4,7,2,3,7]
list_1 = sorted(list_1)
print(list_1)   #[1, 2, 3, 4, 7, 7]
list_1 = sorted(list_1, reverse=True)
print(list_1)   #[7, 7, 4, 3, 2, 1]

list_2 = ["안녕","바보냐?","가격얼마에요?"]
list_2 = sorted(list_2)
print(list_2)   #['가격얼마에요?', '바보냐?', '안녕']
list_2 = sorted(list_2,key=len)
print(list_2)   #['안녕', '바보냐?', '가격얼마에요?']

sort 함수

• 반환값이 없다.

list_3 = [5,7,3,8,1,4]
list_3.sort()
print(list_3)   #[1, 3, 4, 5, 7, 8]
list_3 = list_3.sort()
print(list_3)   #None

역으로도 가능하다.

a_list = [1,2,3,4]
a_list.sort(reverse=True)
print(a_list)