[알고리즘1] 기본 정렬 (버블/삽입/선택)

---

정렬1 : 버블 정렬 (bubble sort)

버블정렬이란, 

인접한 두개의 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 알고리즘이다.

참고: https://visualgo.net/en/sorting

 

bubble sort 함수 생성

이중 반복문으로 큰 순서대로 값을 하나씩 오른쪽으로 이동시켜나감

중간에 swap 변수가 있는 이유는, 이미 정렬이 되었는데도 불필요한 반복문을 수행하는 것을 막기 위함.

두번째 반복문에서 -i 만큼 덜 반복하는 이유는, i회차일 땐 큰 수들 i개가 이미 정렬 완료 됐기 떄문임.

def bubblesort(data):
    for i in range(len(data)-1):
        swap = False
        for j in range(len(data)-i-1):
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j] # swap
                swap = True
                
            print(data)
        if swap == False: 
            break
        print()
    return data

data = [22,4,7,3,8,9,4,2,9,6]
print(data,"\n")
print(bubblesort(data))

수행되는 과정

원래 배열 10개 
[22, 4, 7, 3, 8, 9, 4, 2, 9, 6] 

i=0 인 경우, 가장 큰 수(22)가 맨 오른쪽으로 정렬된다.
총 9번 반복
[4, 22, 7, 3, 8, 9, 4, 2, 9, 6]
[4, 7, 22, 3, 8, 9, 4, 2, 9, 6]
[4, 7, 3, 22, 8, 9, 4, 2, 9, 6]
[4, 7, 3, 8, 22, 9, 4, 2, 9, 6]
[4, 7, 3, 8, 9, 22, 4, 2, 9, 6]
[4, 7, 3, 8, 9, 4, 22, 2, 9, 6]
[4, 7, 3, 8, 9, 4, 2, 22, 9, 6]
[4, 7, 3, 8, 9, 4, 2, 9, 22, 6]
[4, 7, 3, 8, 9, 4, 2, 9, 6, 22]

i=1인 경우, 두번째 큰수(9)가 오른쪽으로 정렬된다.
마지막22를 제외한 총 8번 반복
[4, 7, 3, 8, 9, 4, 2, 9, 6, 22]
[4, 3, 7, 8, 9, 4, 2, 9, 6, 22]
[4, 3, 7, 8, 9, 4, 2, 9, 6, 22]
[4, 3, 7, 8, 9, 4, 2, 9, 6, 22]
[4, 3, 7, 8, 4, 9, 2, 9, 6, 22]
[4, 3, 7, 8, 4, 2, 9, 9, 6, 22]
[4, 3, 7, 8, 4, 2, 9, 9, 6, 22]
[4, 3, 7, 8, 4, 2, 9, 6, 9, 22]

22,9를 제외한 총 7번 반복
[3, 4, 7, 8, 4, 2, 9, 6, 9, 22]
[3, 4, 7, 8, 4, 2, 9, 6, 9, 22]
[3, 4, 7, 8, 4, 2, 9, 6, 9, 22]
[3, 4, 7, 4, 8, 2, 9, 6, 9, 22]
[3, 4, 7, 4, 2, 8, 9, 6, 9, 22]
[3, 4, 7, 4, 2, 8, 9, 6, 9, 22]
[3, 4, 7, 4, 2, 8, 6, 9, 9, 22]

총 6번 반복
[3, 4, 7, 4, 2, 8, 6, 9, 9, 22]
[3, 4, 7, 4, 2, 8, 6, 9, 9, 22]
[3, 4, 4, 7, 2, 8, 6, 9, 9, 22]
[3, 4, 4, 2, 7, 8, 6, 9, 9, 22]
[3, 4, 4, 2, 7, 8, 6, 9, 9, 22]
[3, 4, 4, 2, 7, 6, 8, 9, 9, 22]

총 5번 반복
[3, 4, 4, 2, 7, 6, 8, 9, 9, 22]
[3, 4, 4, 2, 7, 6, 8, 9, 9, 22]
[3, 4, 2, 4, 7, 6, 8, 9, 9, 22]
[3, 4, 2, 4, 7, 6, 8, 9, 9, 22]
[3, 4, 2, 4, 6, 7, 8, 9, 9, 22]

총 4번 반복
[3, 4, 2, 4, 6, 7, 8, 9, 9, 22]
[3, 2, 4, 4, 6, 7, 8, 9, 9, 22]
[3, 2, 4, 4, 6, 7, 8, 9, 9, 22]
[3, 2, 4, 4, 6, 7, 8, 9, 9, 22]

총 3번 반복
[2, 3, 4, 4, 6, 7, 8, 9, 9, 22]
[2, 3, 4, 4, 6, 7, 8, 9, 9, 22]
[2, 3, 4, 4, 6, 7, 8, 9, 9, 22]

총 2번 반복
[2, 3, 4, 4, 6, 7, 8, 9, 9, 22]
[2, 3, 4, 4, 6, 7, 8, 9, 9, 22]
[2, 3, 4, 4, 6, 7, 8, 9, 9, 22]

정렬이 완료되어 swap = False이므로 더이상 정렬 진행 필요 없음.

 

 

 

 

 

 

---

정렬2 : 삽입 정렬 (insertion sort)

삽입정렬이란,

해당 인덱스 앞에 있는 데이터부터 비교해서 key값이 더 작으면 데이터를 뒤의 인덱스로 복사한다.

버블정렬은 데이터 swap 수준을 수십번 반복했다면, 삽입정렬은 교환할때 한번에 제 자리에 도착할때까지 swap해준다고 보면 된다.

def insertion_sort(data):
    for i in range(len(data)-1):
        for j in range(i+1,0,-1):
            if data[j] < data[j-1]:
                data[j], data[j-1] = data[j-1], data[j]
            else:
                break
            print(data)
        print()
    return data

data = [33,1,7,3,8,3,7,8,4,66]
print(data,'\n')
print(insertion_sort(data))​

수행 되는 과정

초기 데이터
[33, 1, 7, 3, 8, 3, 7, 8, 4, 66] 

두번째 값(33)의 위치 찾아주기. swap 필요없음
[1, 33, 7, 3, 8, 3, 7, 8, 4, 66]

세번째값(7)의 위치를 찾아 swap 1회
[1, 7, 33, 3, 8, 3, 7, 8, 4, 66]

네번째값(3)의 위치를 찾아 swap 2회
[1, 7, 3, 33, 8, 3, 7, 8, 4, 66]
[1, 3, 7, 33, 8, 3, 7, 8, 4, 66]

다섯번째값(8)의 위치를 찾아 swap 1회
[1, 3, 7, 8, 33, 3, 7, 8, 4, 66]

여섯번째값(3)의 위치를 찾아 swap 3회
[1, 3, 7, 8, 3, 33, 7, 8, 4, 66]
[1, 3, 7, 3, 8, 33, 7, 8, 4, 66]
[1, 3, 3, 7, 8, 33, 7, 8, 4, 66]

일곱번째값(7)의 위치를 찾아 swap 2회
[1, 3, 3, 7, 8, 7, 33, 8, 4, 66]
[1, 3, 3, 7, 7, 8, 33, 8, 4, 66]

여덟번째값(8)의 위치를 찾아 swap 1회
[1, 3, 3, 7, 7, 8, 8, 33, 4, 66]

아홉번째값(4)의 위치를 찾아 swap 5회
[1, 3, 3, 7, 7, 8, 8, 4, 33, 66]
[1, 3, 3, 7, 7, 8, 4, 8, 33, 66]
[1, 3, 3, 7, 7, 4, 8, 8, 33, 66]
[1, 3, 3, 7, 4, 7, 8, 8, 33, 66]
[1, 3, 3, 4, 7, 7, 8, 8, 33, 66]

마지막값(66)은 swap 필요없음
[1, 3, 3, 4, 7, 7, 8, 8, 33, 66]

 

 

 

---

정렬3 : 선택 정렬 (selection sort)

 

선택정렬이란,

데이터 중 최소값을 찾아 맨 앞에 배치

두번째로 작은 값을 찾아 앞에서 두번쨰 자리에 배치

이를 반복하며 정렬을 완료한다.

 

가장 작은 값의 인덱스를 min_val 이라는 변수에 저장하여 사용함.

def selection_sort(data):
    for i in range(len(data)-1):
        min_val = i
        for j in range(i+1,len(data)):
            if data[min_val] > data[j]:
                min_val = j
        data[i], data[min_val] = data[min_val], data[i]
        print(data,data[i],',',data[min_val],' swap')
    return data

data = [9,5,7,6,8,3,2,1,4,0]
print(data,'\n')
print(selection_sort(data))

수행 되는 과정

[9, 5, 7, 6, 8, 3, 2, 1, 4, 0] 

[0, 5, 7, 6, 8, 3, 2, 1, 4, 9] 0 과 9  swap
[0, 1, 7, 6, 8, 3, 2, 5, 4, 9] 1 과 5  swap
[0, 1, 2, 6, 8, 3, 7, 5, 4, 9] 2 과 7  swap
[0, 1, 2, 3, 8, 6, 7, 5, 4, 9] 3 과 6  swap
[0, 1, 2, 3, 4, 6, 7, 5, 8, 9] 4 과 8  swap
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9] 5 과 6  swap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 6 과 7  swap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 7 과 7  swap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 8 과 8  swap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]