하루 코테 3개 풀기 - 7일차

1. [코드스니펫] 버블 정렬

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


def bubble_sort(array):
    # 이 부분을 채워보세요!
    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]))

 

정답

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


def bubble_sort(array):
    for i in range(len(input)) :
    # 이 부분을 채워보세요!
        if i -1 > i :
            i == i - 1
            i - 1 == i
        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]))

 

다른 풀이

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


def bubble_sort(array):
    n = len(array)
    for i in range(n - 1) :
    # 이 부분을 채워보세요!
        for j in range(n -i -1) :
            print(i, j)
            if array[j] > array[j + 1] :
                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]))

비교하는 길이는 배열이기 때문에 -1 해줘야한다. 

순서대로 오른쪽을 기반으로 비교하는데, 두개 씩 비교해가면서 자리를 이동한다.

처음 한바퀴를 다 돌면 맨 마지막의 인덱스는 완료되었을 거라 생각하고 나머지 인덱스를 비교해 나간다.

1. 배열의 크기만큼 반복한다.

2. 한개씩 죽어가면서 반복한다.

for i in range(5 - 1):
	for j in range(5 - i -1) :
    	print(j)

i 에서 range 가 5 - 1 인 이유 :
배열 전체 길이의 -1 만큼 만 진행하기 때문이다 (2개씩 묶어가면서 비교를 진행하기 때문에)

i =0 일 때, j = 4 이다.
예시)

i =0  j = 4 

[4, 6, 2 ,9 ,1 ] 일 때, (0번째 인덱스와 1번째 인덱스 비교) , ( 1번째 인덱스와 2번째 인덱스 비교 ) , ( 2번째 인덱스와 3번째 인덱스 비교 ) , ( 3번째 인덱스와 4번째 인덱스 비교 )  총 4번을 비교 한다.

i =1 j = 3 
(0번째 인덱스와 1번째 인덱스 비교) , ( 1번째 인덱스와 2번째 인덱스 비교 ) , ( 2번째 인덱스와 3번째 인덱스 비교 )

i =2 j = 2

(0번째 인덱스와 1번째 인덱스 비교) , ( 1번째 인덱스와 2번째 인덱스 비교 )

 

i =3 j = 1

(0번째 인덱스와 1번째 인덱스 비교) 

 

즉 i = 모든 배열을 보는 인덱스

j  배열을 비교하는 횟수

 

2. [코드스니펫] 선택 정렬

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


def selection_sort(array):
    # 이 부분을 채워보세요!
    return


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]))

 

풀이

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[j + i] < array[min_index] :
                min_index = j + i 
        array[i] , array[min_index] = array[min_index], array[i]
    # 이 부분을 채워보세요!
    return array


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]))

 

 

3. [코드스니펫] 삽입 정렬

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


def insertion_sort(array):
    # 이 부분을 채워보세요!
    return


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]))

 

1번째 인덱스 부터 비교를 시작한다.(0번째 x)

비교 인덱스는 

1 --> 2,1 -->  3,2,1 -->

range(1,5) 로 설정하여 1번째 인덱스부터 진행한다.

for i in range(1,5) 
로 설정하여 1번째 인덱스부터 진행한다.
	for j in range(i + j) 
비교 하는 것이 인덱스가 증가할 수 록 1,2,...,4,,5 로 증가하기 때문에 j+1범위이다.

그리고 처음 1번째 인덱스를 시작해서 
1 --> 2,1 -->  3,2,1 --> 
인덱스가 점점 줄어들고 있는 것이 보이는데, 이를 활용해서 i - j 로 인덱스를 잡도록 한다.

for i in range(1, n) :
	for j in range(i):
    if array[i - j] < array[i - j - 1] : 
    	array[i - j], array[i - j - 1] = array[i - j - 1], array[i - j] 
   else :
   	break