자료구조 3주차

728x90

자료구조 3주차_정렬

버블정렬

바로 옆과 비교해서 자신보다 크면 swap

제일 큰 수가 오른쪽으로가고 고정!

📄 나의 코드

input = [4, 6, 2, 9, 1]


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


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

📄 코드

input = [100,56,-3,32,44]


def bubble_sort(array):
    for i in range(len(array) - 1):
        for j in range(len(array) - 1 - i):
            if array[j] > array[j + 1]:
                array[j], array[j+1] = array[j+1],array[j]
    return array


bubble_sort(input)
print(input)

📌 파이썬 swap

a,b = b,a

선택정렬

제일 작은게 제일 앞으로 오게 됨!

📄 나의 코드

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    for i in range(len(array) - 1):
        for j in range(len(array) - 1 - i):
            # print(i)
            # print('  '+str(i+j+1))
            if array[i] > array[i + j + 1]:
                array[i], array[i + j + 1] = array[i + j + 1], array[i]
    return array


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

📄 코드

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for i in range(n - 1):
        min_index = i
        for j in range(n - i):
            if array[i + j] < array[min_index]:
                min_index = i + j

        array[i], array[min_index] = array[min_index], array[i]
    return array


selection_sort(input)
print(input)

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))

삽입정렬

정렬된 상태를 유지하면서 정렬!

자기 자리를 찾아서 한칸씩 이동하는 형식

📄 나의 코드

input = [100,56,-3,32,44]


def insertion_sort(array):
    for i in range(1, len(array)):
        for j in reversed(range(i)):
            # print(i)
            # print('  ' + str(j))
            if array[i] < array[j]:
                array[i], array[j] = array[j], array[i]
                i -= 1
    return array


insertion_sort(input)
print(input)

📄 나의 코드 수정

input = [100,56,-3,32,44]


def insertion_sort(array):
    for i in range(1, len(array)):
        for j in reversed(range(i)):
            # print(i)
            # print('  ' + str(j))
            if array[i] < array[j]:
                array[i], array[j] = array[j], array[i]
                i -= 1
            else:
                break
    return array


insertion_sort(input)
print(input)

강의 보고 알았다! 더 이상 비교 할 필요 없을 때 break해서 시간 복잡도 줄어듦

시간복잡도를 줄이기 위해 더욱 더 깊이 생각해보는 습관을 길러야 겠다.

📄 코드

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array

insertion_sort(input)
print(input)

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

병합정렬(Merge)

배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬 후 병합하는 작업을 반복하는 알고리즘

[1, 2, 3, 5]  # 정렬된 배열 A
[4, 6, 7, 8]  # 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C


        ↓
1단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        1과 4를 비교합니다!
        1 < 4 이므로 1을 C 에 넣습니다.
     C:[1]

           ↓
2단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        2와 4를 비교합니다!
        2 < 4 이므로 2를 C 에 넣습니다.
     C:[1, 2]


              ↓
3단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        3과 4를 비교합니다!
        3 < 4 이므로 3을 C 에 넣습니다.
     C:[1, 2, 3]

                 ↓
3단계 : [1, 2, 3, 5] 
        ↓
       [4, 6, 7, 8] 
        5와 4를 비교합니다!
        5 > 4 이므로 4을 C 에 넣습니다.
     C:[1, 2, 3, 4]

                 ↓
3단계 : [1, 2, 3, 5] 
           ↓
       [4, 6, 7, 8] 
        5와 6을 비교합니다!
        5 < 6 이므로 5을 C 에 넣습니다.
     C:[1, 2, 3, 4, 5]

엇, 이렇게 되면 A 의 모든 원소는 끝났습니다!

그러면 B에서 안 들어간 원소인
       [6, 7, 8] 은 어떡할까요?
하나씩 C 에 추가해주면 됩니다.
     C:[1, 2, 3, 4, 5, 6, 7, 8] 이렇게요!

📄 나의 코드

스스로 한번 짜보려고 했는데 실패...

📄 코드

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]

def merge(array1, array2):
    array_c = [] #정렬된 요소 들어갈 새로운 배열

    array1_index = 0
    array2_index = 0

    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            array_c.append(array1[array1_index])
            array1_index += 1
        else:
            array_c.append(array2[array2_index])
            array2_index += 1

    #비교 후, 남는 요소 모두 넣어주기
    # array2가 남아 있을 경우
    if array1_index == len(array1):
        while array2_index < len(array2):
            array_c.append(array2[array2_index])
            array2_index += 1

    #array1가 남아 있는 경우
    if array2_index == len(array2):
        while array1_index < len(array1):
            array_c.append(array1[array1_index])
            array1_index += 1

    return array_c


print(merge(array_a, array_b))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

정렬된 배열을 합치지 말고

정렬되지 않은 배열을 합치면서 정렬할 수 있을까?

병합정렬 (merge Sort)

📌 분할 정복(Divide and Conquer)

[5, 4]를 [5]와 [4]로 분리!

이 둘을 합치면서 정렬한다면? 결국 전체 정렬된 리스트가 될 수 있다.

[5, 3, 2, 1, 6, 8, 7,  4] 이라는 배열이 있다고 하겠습니다. 이 배열을 반으로 쪼개면
[5, 3, 2, 1] [6, 8, 7, 4] 이 됩니다. 또 반으로 쪼개면
[5, 3] [2, 1] [6, 8]  [7, 4] 이 됩니다. 또 반으로 쪼개면
[5] [3] [2] [1] [6] [8] [7] [4] 이 됩니다.

이 배열들을 두개씩 병합을 하면 어떻게 될까요?
[5] [3] 을 병합하면 [3, 5] 로
[2] [1] 을 병합하면 [1, 2] 로
[6] [8] 을 병합하면 [6, 8] 로
[7] [4] 을 병합하면 [4, 7] 로
그러면 다시! 
[3, 5] 과 [1, 2]을 병합하면 [1, 2, 3, 5] 로
[6, 8] 와 [4, 7]을 병합하면 [4, 6, 7, 8] 로
그러면 다시!
[1, 2, 3, 5] 과 [4, 6, 7, 8] 를 병합하면 [1, 2, 3, 4, 5, 6, 7, 8] 이 됩니다.

MergeSort(0,N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N)

0부터 N까지 정렬한 걸 보기 위해 0부터 N/2까지 정렬한 것과 N/2부터 N까지 정렬한 걸 합치면 된다.

재귀적인 코드!!

📄 merge Sort 재귀코드

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid])   # 왼쪽 부분을 정렬하고
    right_array = merge_sort(array[mid:])  # 오른쪽 부분을 정렬한 다음에
    merge(left_array, right_array)         # 합치면서 정렬하면 됩니다!

문자열의 길이가 1보다 작거나 같을 때 탈출 시키도록 조건을 추가해 줘야 한다.

📄 코드

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


def merge_sort(array):
    # 더이상 정렬할 필요 없으니깐! 탈출조건
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])
    # print(array)
    # print('left_array', left_array)
    # print('right_array', right_array)
    return merge(left_array, right_array)


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

📌 merge Sort 시간복잡도

1단계 [3, 5]

2단계 [6, 8]

k단계 [6] [8]

N/2^k = 1 → k 를 log₂N로 표현 가능

즉, k단계 만큼 반복하는데 각각 단계는 O(N) 시간복잡도를 가진다.

log₂N * O(N)이 최종 시간복잡도 이다. O(NlogN) 만큼의 시간복잡도를 가진다.

저작자표시

'알고리즘' 카테고리의 다른 글

자료구조 2주차 복습&숙제 (0)	2022.11.28
자료구조 3주차_스택 (0)	2022.11.25
자료구조 2주차_이진탐색과 재귀함수 (0)	2022.11.24
자료구조 2주차_어레이와 링크드리스트 (0)	2022.11.24
자료구조 1주차_시간복잡도 & 공간복잡도 (0)	2022.11.23

팽이의 개발일기

자료구조 3주차_정렬