정렬(sort)

 

버블정렬(bubble sort)

* 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

 

 

데이터가 네 개일때 [1,9,3,2]

• 1차 순회
  • 1과 9비교, 자리바꿈없음 [1,9,3,2]
  • 9와 3비교, 자리바꿈 [1,3,9,2]
  • 9와 2비교, 자리바꿈 [1,3,2,9]
• 2차 순회
  • 1과 3비교, 자리바꿈 없음 [1,3,2,9]
  • 3과 2비교, 자리바꿈 [1,2,3,9]
  • 3와 9 비교, 자리바꿈 없음 [1,2,3,9]
• 3차 순회
  • 1과 2비교, 자리바꿈 없음 [1,2,3,9]
  • 2와 3비교, 자리바꿈 없음 [1,2,3,9]
  • 3과 9비교, 자리바꿈 없음 [1,2,3,9]

 

* n개의 리스트가 있는 경우 최대 n-1번의 로직을 적용

* 로직을 1번 적용할때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정

* 한 번도 데이터가 교환된적이 없다면 이미 정렬된 상태

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data

 

• 반복문이 2개 최악의 경우 n(n-1)/2 
• 완전 정렬이 되어있는 경우 최선은 O(n)

 

---

삽입정렬(insertion sort)

 

• 삽입 정렬은 두번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(b)부터 비교해서 key 값이 더 작으면 b값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 그 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

데이터가 4개일때 [9,3,2,5]

- 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: [9, 3, 2, 5]
- 두 번째 실행하면, key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: [3, 9, 2, 5]

- 세 번째 실행하면, key값은 2, 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: [2, 3, 9, 5]
- 네 번째 실행하면, key값은 5, 9보다 5이 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝: [2, 3, 5, 9]  

 

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

• 반복문이 2개 최악의 경우 n(n-1)/2 
• 완전 정렬이 되어있는 경우 최선은 O(n)

 

---

병합정렬(merge sort)

• 분할 정복(Divide and Conquer), 시간복잡도 O(nlogn)
• 재귀용법을 활용한 정렬 알고리즘
• 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

• 예: data_list = [1, 9, 3, 2]
  • 먼저 [1, 9], [3, 2] 로 나누고
  • 다시 앞 부분은 [1], [9] 로 나누고
  • 다시 정렬해서 합친다. [1, 9]
  • 다음 [3, 2] 는 [3], [2] 로 나누고
  • 다시 정렬해서 합친다 [2, 3]
  • 이제 [1, 9] 와 [2, 3]을 합친다.
  • 1 < 2 이니 [1]
  • 9 > 2 이니 [1, 2]
  • 9 > 3 이니 [1, 2, 3]
  • 9 밖에 없으니, [1, 2, 3, 9]
    • •  

def merge_sort(unsorted_list):
    # 크기가 1이하면 반환
    if len(unsorted_list) <= 1:
    	return unsorted_list
     
    # 리스트를 2분할
    mid = len(unsorted_list)//2
    left = unsorted_list[:mid]
    right = unsorted_list[mid:]
    
    # 2분할한 리스트를 각각 merge sort진행
    left_ = merge_sort(left)
    right_ = merge_sort(right)
    return merge(left_, right_)

def merge(left, right):
    i, j = 0,0
    sorted_list = []
    
    while i < len(left) and j < len(right):
    	if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    while i < len(left):
    	sorted_list.append(left[i])
        i += 1
    while j < len(right):
    	sorted_list.append(right[j])
        j += 1
    return sorted_list