정렬(1) - 버블, 선택, 삽입

버블 정렬

버블 정렬은 정렬되는 모양이 버블 같다고 해서 지어진 이름이다

버블 정렬은 바로 옆과 비교하고 (오름차순일 때) 오른쪽이 더 작으면 바꾼다 이 과정을 N^2번 반복한다

 

42713 배열 버블 정렬해 보기

위 과정을 거치고 나면 7(가장 큰 값)은 이제 제대로 된 자리에 도착했다 16번 단계에서 1과 2를 비교하고 교환할 필요가 없어 정렬이 끝나게 된다

 

 

파이썬 버블 정렬

a = [4,2,7,1,3]
k=0 //단계를 세기 위한것

for i in range(len(a)):
    for j in range(0,len(a)-i-1):
        k += 1
        if a[j] > a[j+1]:
            k += 1 //단계를 세기 위한것
            t = a[j]
            a[j] = a[j+1]
            a[j+1] = t

print(a) //[1, 2, 3, 4, 7]
print(k) //16

위 풀이와 같이 코드를 실행시키면 비교 + 교환은 총 16번 이뤄진 것을 확인할 수 있다

 

 

버블 정렬의 효율성

버블 정렬은 비교와 교환을 통해서 이뤄진다 먼저 비교를 보자면 크기 5인 배열에서 비교는 처음 4번 두 번째 3번

세 번째 2번 네 번째 1번으로 총 4+3+2+1 = 10 번의 비교가 이뤄졌다

원소가 N 개 있으면 비교는 (N-1) + (N-2) + (N-3) + ··· + 1 번 비교가 이뤄진다

 

교환은 배열이 내림차순으로 있다고 하면 비교할 때마다 교환이 일어난다 그럼 총 10 + 10 = 20단계가 필요

N 개의 데이터	버블 정렬 최대 단계	N^2
5	20	25
10	90	100
20	380	400
40	1560	1600
80	6320	6400

버블 정렬은 대략 N^2만큼 늘어난다 따라서 O(N^2)이라고 부른다

 

 

 

---

선택정렬

선택 정렬은 각 셀 왼쪽부터 오른쪽 방향으로 값을 확인하면서 어떤 값이 최솟값인지 결정한다 한 셀씩 이동하면서 가장 작은 값을 변수에 저장한다 오른쪽 끝까지 이동하면 나온 최솟값을 맨 앞에 숫자와 교환한다 그러면 배열의 맨 앞은 정렬되었다 맨 앞을 제외하고 다시 최솟값을 찾은 뒤에 2번째 자리의 값과 교환한다 반복해서 정렬을 완료

위 과정으로 최솟값과 교환을 계속하면 배열이 정렬된다 버블 정렬과는 다르게 앞부터 정렬된다

 

선택 정렬 파이썬 코드

# 선택 정렬은 배열중 최솟값을 찾아서 위치를 앞으로 바꾼다 (앞부터 정렬)
# 배열이 입력된다 

list1 = [4,2,7,1,3]
time=0 # 단계 확인을 위한것

for i in range(len(list1)):
    min = i #최솟값의 인덱스 저장
    for j in range(i+1,len(list1)):
        time += 1
        if list1[min] > list1[j]:
            min = j

    if list1[min] < list1[i]:
        k = list1[min]
        list1[min] = list1[i]
        list1[i] = k
        time += 1

print(list1) #[1, 2, 3, 4, 7]
print(time) #12

 

 

선택 정렬 효율성

선택 정렬 안에는 비교와 교환 두 종류를 포함한다 만약 5개의 원소를 선택 정렬하면 처음 패스스루 비교 4번 두 번째 패스스루 비교 3번 세 번째 패스스루 비교 2번 마지막은 1번 비교한다 총 4+3+2+1= 10번의 비교

교환은 한 패스스루당 최대 한 번이므로 4번의 교환이 이루어진다

N 개의 원소	버블 정렬 최대 단계	선택 정렬 최대 단계
5	20	14
10	90	54
20	380	199
40	1560	819
80	6320	3239

위 표를 보면 버블 정렬보다 약 2배 정도 빠르다고 볼 수 있다 버블 정렬의 빅 오 표현은 O(N^2)이다 따라서 선택 정렬의 빅 오 표현은 O(N^2)/2가 되어야 할 것 같지만 빅 오 표현은 상수를 무시하기 때문에 둘 다 똑같이 O(N^2)으로 표시한다

 

 

 

---

삽입 정렬

삽입 정렬은 정렬된 왼쪽과 정렬되지 않은 오른쪽에서 오른쪽 값을 하나 꺼내어 왼쪽과 하나하나 비교하면서 올바른 위치에 넣는다 이러면 오른쪽 값들이 왼쪽으로 이동하면서 정렬되게 된다 시작은 인덱스 1번 부터 시작

삽입 정렬은 시프트(이동)과 변수 하나를 이용한다

인덱스 1인 2부터 시작한다 원소가 5개이므로 총 4번의 패스스루를 통과한다

 

 

삽입 정렬 파이썬 코드

list1= [4,2,7,1,3]

for i in range(1, len(list1)):
    j = i
    # 이전의 수 보다 타겟이 작아지는 것이 한 번 이라도 나타날 대 까지 루프
    while j > 0 and list1[j - 1] > list1[j]:
        list1[j - 1], list1[j] = list1[j], list1[j - 1]
        j -= 1
      
print(list1)