스파르타코딩 - 알고리즘 강의 3 주차 (ft.정렬)

버블정렬

  • 바로 앞에 배열과 비교

    input = [4, 6, 2, 9, 1]
    
    def bubble_sort(array):
        n = len(array)
        for i in range(n - 1): # 배열의 크기 - 1  까지
            for j in range(n - i - 1): # 0123,012,01,0 순으로 검사함
                if array[j] > array[j + 1]: # 바로 앞에 배열과 비교해서 변경
                    # 파이썬 치환 문법은 a, b = b, a
                    array[j], array[j + 1] = array[j + 1], array[j] 
    
        return array
    
    bubble_sort(input)
    print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!
    
    print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
    print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
    print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))

선택정렬

  • 최소값을 찾아 변경 : array(min_index)
    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): # 01234, 1234, 234, 34 순으로 검사 (ft.i + j)
                if array[i + j] < array[min_index]:
                    min_index = i + j
    
            array[i], array[min_index] = array[min_index], array[i]
    
        return array
    
    # 버블 정렬하고 다른 건 바로 "최솟값"을 찾아 변경하는 것입니다.
    # 따라서, min_index 라는 변수를 통해 각각의 인덱스들과 비교합니다.
    # 그리고 내부의 반복문이 끝나면, 최소 값의 인덱스와 i의 값들을 교체해주면 됩니다!
    
    selection_sort(input)
    print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!
    
    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]))

삽입정렬

  • 1부터 n까지
    input = [4, 6, 2, 9, 1]
    
    def insertion_sort(array):
        n = len(array)
        for i in range(1, n):
            for j in range(i): # 1, 21, 321, 4321 순임 (ft. i - j)
                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) # [1, 2, 4, 6, 9] 가 되어야 합니다!
    
    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]))

keyword

# 버블정렬 - 바로 앞에 것과 비교
n = array
* for i in range(n - 1):
* 	for j in range(n - i - 1):
*			if array[j] > array[j + 1]:

* i 의 범위 : n-i
* j 의 범위 : n-i-1
* 조건 : arr[j] > arr[j+1}

# 선택정렬 - 최소값을 찾아 비교
n = array
* for i in range(n - 1):
* 	for j in range(n - i):
*			if array[i + j] < array[min_index]:
					min_index = i + j

* i 의 범위 : n-1
* j 의 범위 : n-i
* 조건 : arr[i+j] < arr[min_idx]

# 삽입정렬 - 1부터 시작
n = array
* for i in range(1, n):
* 	for j in range(i):
*			if array[i - j - 1] > array[i - j]:

* i 의 범위 : 1, n
* j 의 범위 : i
* 조건 : arr[i-j-1] > arr[i-j]

1번째 : [4,6,2,9,1]
         ← 비교!
2번째 : [4,6,2,9,1]
         ← ← 비교!
3번째 : [2,4,6,9,1]
         ← ← ← 비교!
4번째 : [2,4,6,9,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 = array[:mid]
        right_array = array[mid:]
        return merge(merge_sort(left_array), merge_sort(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] 가 되어야 합니다!
    
    print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge_sort([-7, -1, 9, 40, 5, 6, 10, 11]))
    print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge_sort([-1, 2, 3, 5, 40, 10, 78, 100]))
    print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge_sort([-1, -1, 0, 1, 6, 9, 10]))

좋은 웹페이지 즐겨찾기