파이썬 버블정렬, 선택정렬, 삽입정렬

정렬이라고 검색하면 무조건 나오는 이 세가지를 배워보겠다!!!

 

버블 정렬

버블정렬이란 가장 원초적인 방법이다.

앞 숫자와 뒷 숫자를 비교하면서 앞의 숫자가 크다면 순서를 바꾸고 작다면 pass

이걸 첫 인덱스부터 마지막 인덱스까지 차례로하면 마지막에는 제일 큰 숫자가 있을 것이다.

이런 일련의 반복을 거쳐 정렬하는 방법을 버블 정렬이라고 한다. 

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


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


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

 

이제부터 for문을 돌 것인데. range의 범위를 len(array)이 아닌 len(array)  -1을 해주었다. 그 이유는 마지막 0번째 인덱스 하나만으로는 비교가 안되기 때문이다. 아래 표를 참고하자, 

1번째 for문	2번째 for문	3번째 for문	4번째 for문
0번째, 1번째 인덱스를 비교	0번째, 1번째 인덱스를 비교	0번째, 1번째 인덱스를 비교	0번째, 1번째 인덱스를 비교
1번째, 2번째 인덱스를 비교,	1번째, 2번째 인덱스를 비교,	1번째, 2번째 인덱스를 비교,
2번째, 3번째 인덱스를 비교,	2번째, 3번째 인덱스를 비교,
3번째, 4번째 인덱스를 비교,

 

그리고 안 쪽 for문도 array는 5칸의 요소가 있지만 그 사이사이의 공간은 4칸이기때문에 최대 4번만 비교가 될 것이다. 즉 인접 인덱스와 비교하기 때문에, 숫자를 하나 줄여주어야 한다. 뿐만아니라 여기서 len(array) -1 -i로 i역시 빼주었는데 그 이유는 이미 바깥 for문이 돌았다는 뜻은 제일 큰 숫자들이 맨 뒤에서 정렬이 되어있기 때문에 숫자를 하나씩 줄여주는 것이 효율 적이다.

 

 

선택 정렬

def selection_sort(array):
    num = len(array)

    for i in range(num-1):
        min_idx = i
        for j in range(i, num):
            if array[min_idx] > array[j]:
                min_idx = j
        array[i],array[min_idx] = array[min_idx], array[i]

    return


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

선택정렬은 누가 제일 작은지 for문을 통해서 다 훑어보고 제일 작은녀석을 처음 인덱스에 집어넣는 방식이다.

그 다음 for문이 돈다면 제일 작은 녀석은 0번째에 있을 것이니 남은 녀석들 중에 제일 작은 놈을 1번째 인덱스에 집어넣는 방식으로 갈 것이다. 이 역시 마지막 -1번째 인덱스에 있는 비교 대상이 없으므로 바깥 for문에서 1만큼 빼주었다.

 

먼저 시작index를 min_idx에 넣고 for문을 돌면서 그 자리에 최소 값의 index를 넣는다. 

안쪽 for문이 마치고나면 시작 index와 min_idx의 자리의 있는 값을 서로 바꿔줌으로써 정렬해나가는 방식이다.

만약 min_idx를 사용하지 않고 min이라는 변수를 만들어에 최소값을 넣는방식으로는 안될까?

이 경우 최소값은 얼만지 알겟지만 우리는 최소값이 있던 자리에 다른 값을 넣어줄 수가 없기 때문에 idx로 찾아주어야 한다.

 

삽입 정렬

버블정렬은 나와 내 뒤에 있는 값을 비교해서 작으면 바꾸고 ,크면 패스하는 방식으로 제일 마지막에 큰 값을 두는 것

선택정렬은 가장 작은 값을 골라서 0번째 인덱스 부터 차례로 두는 것인데

 

나는 이 두 방법은 솔직히 내가 실생활에서 정렬을 해야 할때에는 잘 안 쓸 것같다. 근데 삽입정렬은 내가 알게 모르게 정렬을 해왔을 때 가장 많이 사용해 왔었던 것 같다.

 

먼저 1년치 영수증(100개)을 날짜별로 차례로 두라고 지시를 받았다.

버블정렬을 쓴따면 100개를 나란히 두고 앞 뒤로 하나하나 비교해가면서 해야되고

선택정렬도 100개를 다 보고 제일 작은걸 찾아 앞에 두고.. 비효율적이지 않은가?

 

나라면 일단 손에 집히는거 하나를 기준으로 삼겠다.

그리고 그걸 가운데 두고 그 다음 아무거나 집고 그게 첫번째보다 크면 뒤에두고 작으면 앞에두는 방식으로 할 것같다.

말이 길었지만 이 방법이 삽입 정렬이라고 생각한다.

 

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

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


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

먼저 num에 배열의 길이를 담는다. 이번엔 바깥 for문에 온전히 num 전체가 들어온다. 그 이유는 마지막 인덱스또한 정렬을 해나가야하기 때문이다. 안쪽 for문은 조금 특이한데 일단 로직을 살펴보자

 

먼저 첫 번째 for는 그냥 아무 것도 안하고 넘어간다. 그럼 4라는 것이 기준이 되는 것이다. (따라서 range(1,num)으로 줘도됨)

그리고 두 번째 for문에서는 1번째 인덱스 6과 4를 비교해서 만약 6이 더 작으면 순서를 바꾸는 식이다. 여기서는 4가 더 작으니 바꾸지 않았다.

 

그리고 3번째 for문에서는 2와 6을 비교하고 2가더 작으니 6과 바꿔주고 또 4와 2를 비교하여 2가 더 작으니 2를 맨 앞으로 둔다. 그럼 [2,4,6,9,1] 여기까지 온 것이다. 근데 9는 이미 6보다 크니까 앞에 있는 것들과 비교해줄 필요가 없다. 따라서 else문으로 빠져 바로 break를 타도록 하였다. 마지막 1은 앞의 숫자들과 비교하여 첫번째 자리로 이동할 것이다.

 

앞서 말한 정렬은 모두 이중 for문을 돌아야한다. 따라서 전부 시간복잡도는 O(N*2)이다. 하지만 삽입정렬은 최고의 조건일 때는 N으로 바뀐다.  그 이유는 [1,2,3,4,5,6] 이라는 이미 정렬이 된 배열에 3가지 정렬방법을 사용한다고 하면 버블정렬과 선택정렬은 이중 for문을 다 돌테지만 삽입정렬은 안쪽 for문은 break로 바로 빠져나올 것이기 때문이다.