07 - 버블 정렬,선택정렬,삽입정렬

Bubble Sort

버블 정렬은 첫번째 자료와 두번째 자료를, 두번째자료와 세번째자료를, 세번째와 네번째를 ...

이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식이다.

 

작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경하시면 된다.

 

bubble sort의 정렬방식

 

Bubble Sort방식으로 알고리즘을 풀어보았다.

Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 버블 정렬을 이용해서 정렬하시오.

시작전 어떻게 구현할지 고민해봤다.

 

def bubble_sort(array):
    n = len(array) # 배열의 길이를 N에 담아두겠다

    for i in range(n - 1): # 배열의 길이에 - 1만큼 반복할거다 왜 N-1만큼 반복하느냐? # O(N)
        for j in range(n - i - 1):
            print(i,j) #코드가 이해가 안된다면 프린트로 찍어보면 된다
            if array[j] > array[j + 1]: # j번째 인덱스가 j+1보다 크다면 둘의 값을 바꿔버리겠다
                array[j], array[j + 1] = array[j + 1], array[j]
    return array


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9]

Selection Sort

이름에서 알수있듯이 선택해서 정렬한다 라고해서 선택정렬이다.

다음과 같이 사람들이 일렬로 쭉~ 서 있는데, 한번 쓱 둘러보면서 가장 키 작은 사람을 찾는 방식이라 생각하면 간단하다.

 

 

Selection Sort방식으로 알고리즘을 풀어보았다.

Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 선택 정렬을 이용해서 정렬하시오.

 

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

def selection_sort(array):

    n = len(array)
    for i in range(n - 1): # n - 1 만큼의 범위에서 i를 뽑은 다음에
        min_index = i # 최솟값을 가지고 있다는 인덱스를 i로 초기화를 시켜둡니다  ex : ) i = 0
        for j in range(n - i): # 그다음에 n - i 의 범위만큼 j를 뽑은 다음에 # ex : ) j = 0 ~ 4
            if array[i + j] < array[min_index]: # 그상태에서 i + j의 값들을 하나하나 보면서
                min_index = i + j # 그리고 만약 최솟값이라면 min_index를 i+j로 업데이트 한 다음에
        array[i], array[min_index] = array[min_index], array[i] # 최종적으로 뽑아진 최소값과 i번째 원소를 자리변경 해줍니다.
    return array


selection_sort(input)
print(input) # [1, 2, 4, 6, 9]

 

Insertion Sort

선택 정렬이 전체에서 최솟값을 "선택"하는거 였다면, 삽입정렬은 전체에서 하나씩 올바른 위치에 "삽입"하는 방식이다.

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만, 삽입정렬은 필요할때만 위치를 변경하므로 더 효율적인 방식이다.

 

이미 키 순으로 정렬된 사람들이 일렬로 쭉~ 서 있는데, 다음 원소가 정렬된 사람들 사이를 비집고 들어가면서 다음원소가

그 정렬된 사람들 사이를 비집고 들어가는 방식이라 생각하면 된다.

 

Insertion Sort방식으로 알고리즘을 풀어보았다.

input = [4, 6, 2, 9, 1] #가장 앞에 있는것을 기준으로 이미 정렬된 상태다
# 선택 정렬의 경우에는 중간에 멈춰도 되는 정렬이다

# 1.
# [4,6,2,9,1]

# 2.
# [2,4,6,9,1]

# 3.
# [4,6,2,9,1]


def insertion_sort(array):
    # 이 부분을 채워보세요!
    n = len(array)
    for i in range(1, n): # 5는 n일태고
        for j in range(i):
            if array[i - j] < array[i - j - 1]: # 이 i - j 의 인덱스 값을 뽑아서
                array[i - j], array[i - j - 1] = array[i - j - 1], array[i - j - 1] # 두값을 변경해줘야된다
            else:
                break #앞으로 만난놈이 숫자가 더크면 반복문을 중단하라
    return array