[알고리즘] 정렬 알고리즘① - 버블정렬(Bubble), 선택정렬(Selection), 삽입정렬(Insertion)

 

[파이썬 자료구조와 알고리즘] 시간 복잡도, 빅오 표기법(자료구조, 정렬 알고리즘의 시간 복잡

---

정렬 알고리즘(Sorting Algorithm)이란?

정렬 알고리즘은 무작위로 나열되어 있는 데이터를
특정 기준(오름차순 또는 내림차순)에 따라 순서대로 재배열하는 알고리즘을 말한다.
정렬 알고리즘을 사용하여
데이터를 효율적으로 탐색하고 관리할 수 있다.
 
정렬 알고리즘엔 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬이 있고
이는 비교 정렬에 포함되며, 비교하지 않는 정렬에는 계수 정렬이 있다.

※ 비교하지않는 정렬 : 계수 정렬, 기수 정렬, 버킷 정렬

 
이번 글에서는 버블 정렬, 선택 정렬, 삽입 정렬에 대해 소개할예정이다.

---

1) 버블 정렬(Bubble Sort)

버블 정렬은 사실 가장 무식하게 정렬하는 방법으로
인접한 두 값을 비교하면서 계속 교환하며 정렬하는 방식이다.
큰 값이 뒤로 버블처럼 떠올라간다 라고 생각하면 쉽다.

---

1_1) 버블 정렬의 정렬과정

1. 맨 앞부터 시작해 인접한 값과 비교하면서 큰 값은 뒤로, 작은 값은 앞으로 보낸다.
2. 해당 과정을 거쳐 맨 뒤에는 가장 큰 값이 위치하게 된다.
3. 정렬된 가장 큰 값을 제외하고 나머지값들에 대해 같은 과정을 반복하며 전체 배열에 대한 정렬을 진행한다.

# 버블정렬 예시 리스트
[5, 3, 8, 4, 2] 

# 1회전
# 1) 5와 3 비교 → 3 앞으로
# 2) 5와 8 비교 → 5 유지
# 3) 8과 4 비교 → 4 앞으로
# 4) 8과 2 비교 → 2 앞으로
[3, 5, 4, 2] + [8] → 8 정렬

# 2회전
# 1) 5와 3 비교 → 3 유지
# 2) 5와 4 비교 → 4 앞으로
# 3) 5과 2 비교 → 2 앞으로
[3, 4, 2] + [5, 8] → 5 정렬

# 3회전
# 1) 3와 4 비교 → 3 유지
# 2) 4와 2 비교 → 2 앞으로
[3, 2] + [4, 5, 8] → 4 정렬

# 4회전
# 1) 3와 2 비교 → 2 앞으로
[2] + [3, 4, 5, 8] → 3 정렬

# 최종결과
[2, 3, 4, 5, 8]

---

1_2) 버블 정렬의 시간복잡도

인접한 두 요소를 비교하여 큰 값을 뒤로 보내는 과정을 반복하며 정렬을 수행한다.
이미 정렬이 되어있는 배열일 경우 교환이 발생하지 않아 정렬이 종료되기때문에 O(n)의 시간복잡도를 갖는다.
 
하지만 배열이 역순으로 정렬이 되어있는 경우
모든 요소를 반복적으로 비교하고 교환을 진행해야하기 때문에
최악의 경우 O(n²)의 시간복잡도를 가지게 된다.

• 평균 / 최악 : O(n²)
• 최선 : O(n) → 이미 정렬된 경우

---

1_3) 버블 정렬의 장단점

👍 버블정렬 장점

• 추가 메모리가 필요없는 제자리 정렬이다.
• 이미 정렬이 되어있는 경우 교환이 발생하지않아 O(n)의 시간복잡도를 가진다.

👎 버블정렬 단점

• 비교와 교환이 많이 발생한다.
• 데이터 갯수가 많아질수록 성능이 저하된다.
• 최악의 경우 O(n²)의 시간복잡도를 가진다.

---

1_4) 버블 정렬 파이썬 코드로 구현하기

✅ 기능 1) 바깥 반복문 : 전체 반복

바깥쪽 반복문은 전체를 총 몇 바퀴 반복할지 결정한다. (전체 회전 수)

len(array) - 1

 

✅ 기능 2) 안쪽 반복문 : 비교 반복

안쪽 반복문은 실제로 옆에 숫자와 비교하는 부분이다.
이때 전체 배열 길이에서 i만큼 빼주는 이유는 
이미 정렬된 뒤쪽 부분은 정렬이 되어 비교할 필요가 없기 때문에 빼준다.

※ 총 회전수가 늘어날수록 비교횟수는 1씩 줄이는 역할

len(array) - 1 - i

 

✅ 기능 3) if문 : 위치 교환

if문은 앞숫자와 뒷숫자를 비교하여 서로의 위치를 교환하는 부분이다.
비교를 진핼 할 array[j]가 array[j+1]보다 클 경우 교환을 진행한다.

if array[j] > array[j + 1]:
    array[j], array[j + 1] = array[j + 1], array[j]

✅ 기능 4) 오름차순과 내림차순

내림차순 정렬은 if문의 부등호만 바꿔서 내림차순으로 변경할 수 있다.

# 오름차순
if array[j] > array[j+1]:
    array[j], array[j+1] = array[j+1], array[j]
                    
# 내림차순으로 변경
if array[j] < array[j+1]:
    array[j], array[j+1] = array[j+1], array[j]

 

💡 버블 정렬 최종코드 : 오름차순

# 오름차순 최종코드
import random

def bubble_asc(array):
    # 바깥 반복문
    for i in range(len(array)-1):
        # 안쪽 반복문
        for j in range(len(array)-1-i):
            # if문
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

# random.sample(뽑을대상, 개수)
random_bubble_data = random.sample(range(1, 101), 5)

print("버블 정렬 전:", random_bubble_data)
print("버블 정렬 후:", bubble_asc(random_bubble_data))

실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.

 

💡 버블 정렬 최종코드 : 내림차순

# 내림차순 최종코드
import random

def bubble_desc(array):
    # 바깥 반복문
    for i in range(len(array)-1):
        # 안쪽 반복문
        for j in range(len(array)-1-i):
            # if문 : 내림차순 변경!
            if array[j] < array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

# random.sample(뽑을대상, 개수)
random_bubble_data = random.sample(range(1, 101), 5)

print("버블 정렬 전:", random_bubble_data)
print("버블 정렬 후:", bubble_desc(random_bubble_data))

실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.

---

2) 선택 정렬(Selection Sort)

선택 정렬은 리스트에서 가장 작은 값을 선택하여 해당 값을 앞쪽으로 보내는 방식으로 정렬한다.
배열 전체를 순회하면서 가장 작은 값을 찾고 맨 앞 숫자와 교환하는 방식이다.
이름 그대로 가장 작은 값을 선택하여 앞으로 보내는 정렬이다.

---

2_1) 선택 정렬의 정렬과정

1. 배열 전체를 탐색하여 가장 작은 값을 찾는다.
2. 찾은 가장 작은 값을 정렬되지 않은 구간의 맨 앞과 교환한다.
3. 정렬된 앞쪽 구간을 제외하고 나머지 값들에서 과정을 반복하여 정렬

# 선택정렬 예시 리스트
[5, 3, 8, 4, 2] 

# 1회전
# 1) 전체에서 가장 작은값 2 선택
# 2) 맨 앞의 5와 위치 교환
[2] + [3, 8, 4, 5] → 2 정렬

# 2회전
# 1) 2를 제외한 나머지 범위에서 가장 작은값 3을 찾음
# 2) 현재 위치가 맞는 위치기에 교환없음
[2, 3] + [8, 4, 5] → 3 정렬

# 3회전
# 1) 나머지 범위에서 가장 작은 값 4를 찾음
# 2) 나머지 범위 안의 맨 앞에 8과 위치 교환
[2, 3, 4] + [8, 5] → 4 정렬

# 4회전
# 1) 나머지 범위에서 가장 작은 값 5를 찾음
# 2) 나머지 범위 안의 맨 앞에 8과 위치 교환
[2, 3, 4, 5] + [8] → 5 정렬

# 최종결과
[2, 3, 4, 5, 8]

---

2_2) 선택 정렬의 시간복잡도

배열의 각 위치에서 뒤쪽의 모든 요소를 탐색하며 최솟값을 찾는 방식으로
이미 정렬되어 있는 경우에도 최솟값을 찾기 위해 끝까지 탐색하기 때문에 불필요한 비교가 발생한다.
즉, 배열의 상태와 관계없이 항상 n개의 요소에 대해 n번의 비교를 수행하는 O(n²)의 시간복잡도를 가진다.

• O(n²)

---

2_3) 선택 정렬의 장단점

👍 선택정렬 장점

• 교환횟수가 적다.
• 추가 메모리가 필요없다.

👎 선택정렬 단점

• 비교 횟수가 많다.
• 데이터가 많아질수록 성능이 급격히 떨어진다.
• 이미 정렬된 데이터라도 최솟값을 찾기 위해 끝까지 탐색해야한다.

---

2_4) 선택 정렬 파이썬 코드로 구현하기

✅ 기능 1) 바깥 반복문 : 최솟값 지정

첫 번째 반복을 진행할 때(i=0) 0번째에 들어갈 가장 작은 값을 찾기위해
min_index = 0으로 최솟값을 가정하여 지정한다.

min_index = i

 

✅ 기능 2) 안쪽 반복문 :  최솟값 빼고 나머지 비교

안쪽 반복문은 가장 작다고 가정한 것의 나머지부분을 순회하며 비교를 진행한다.
j가 항상 i + 1에서부터 시작하는 이유는 min_index = i를 설정하여
i번째를 이미 바깥 반복문에서 최솟값으로 가정했기 때문에
자기 자신과는 비교할 필요가 없어 다음값부터 진행하기 위해 i + 1을 진행하는것이다.

 for j in range(i + 1, len(array))

 

✅ 기능 3) if문 : 위치 교환

if문은 첫번째 반복을 진행할 때 최솟값을 제외하고 나머지를 순회(인덱스 1부터 나머지)하면서
min_index보다 값이 작다면 min_index를 j로 업데이트해주는 기능을 가지고 있다.(인덱스 2로 업데이트)

if array[j] < array[min_index]:
    min_index = j

✅ 기능 3) 위치교환 (안쪽 반복문 종료 시 실행)

안쪽 반복문이 종료되면 최솟값이 min_index에 담겨있기 때문에
array[i]와 array[min_index]의 위치를 교환한다.

array[i], array[min_index] = array[min_index], array[i]

✅ 기능 4) 오름차순과 내림차순

내림차순 정렬은 min_index를 max_index로 바꾸고
if문의 부등호를 바꿔서 내림차순으로 변경할 수 있다.

# 오름차순
if array[j] < array[min_index]:
    min_index = j 
array[i], array[min_index] = array[min_index], array[i]

# 내림차순
if array[j] > array[max_index]:
    max_index = j 
array[i], array[max_index] = array[max_index], array[i]

 

💡 선택 정렬 최종코드 : 오름차순

# 오름차순 최종코드
import random

def selection_asc(array):
    # 바깥 반복문
    for i in range(len(array)-1):
        min_index = i
        # 안쪽 반복문
        for j in range(i+1, len(array)):
            # if문
            if array[j] < array[min_index]:
                min_index = j 
        # 위치교환
        array[i], array[min_index] = array[min_index], array[i]
    return array

# random.sample(뽑을대상, 개수)
random_selection_data = random.sample(range(1,101), 5)

print("선택정렬 랜덤 데이터", random_selection_data)
print("선택정렬 결과",selection_asc(random_selection_data))

실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.

💡 선택 정렬 최종코드 : 내림차순

# 내림차순 최종코드
import random

def selection_desc(array):
    # 바깥 반복문
    for i in range(len(array)-1):
        max_index = i
        # 안쪽 반복문
        for j in range(i+1, len(array)):
            if array[j] > array[max_index]:
                max_index = j
        # 위치 교환
        array[i], array[max_index] = array[max_index], array[i]
    return array

# random.sample(뽑을대상, 개수)
random_selection_data = random.sample(range(1,101), 5)

print("선택정렬 랜덤 데이터", random_selection_data)
print("선택정렬 결과", selection_desc(random_selection_data))

실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.

---

3) 삽입 정렬(Insertion Sort)

삽입 정렬은 카드를 정리하듯이 데이터를 하나씩 꺼내어 적절한 위치에 삽입하는 방식의 정렬 알고리즘이다.
앞쪽 구간은 항상 정렬되어 있다고 가정하고, 새로운 데이터를 알맞은 위치에 끼워 넣으며 정렬을 진행한다.
데이터가 거의 정렬되어 있는 경우 매우 빠르게 동작하는 특징이 있다.

---

3_1) 삽입 정렬의 정렬과정

1. 맨 앞의 값은 이미 정렬된것으로 가정한다.
2. 정렬되지 않은 구간에서 값을 하나 꺼내 정렬된 구간의 값과 비교한다.
3. 삽입할 위치를 찾을 때 까지 큰 값들은 한 칸씩 뒤로 이동시키면서 맞는 위치를 찾아 값을 삽입한다.
4. 정렬된 구간을 하나씩 확장해가며 정렬을 진행한다.

# 삽입 정렬 예시 리스트
# : 맨 앞의 5는 이미 정렬된것으로 본다.
[5, 3, 8, 4, 2] 

# 1회전
# 1) 3을 꺼내 5와 비교 → 5오른쪽으로 한 칸 이동
[3, 5] + [8, 4, 2] → 3 정렬

# 2회전
# 1) 8을 꺼내 5와 비교 → 8 유지
[3, 5, 8] + [4, 2] → 8 정렬

# 3회전
# 1) 4를 꺼내 8과 비교 → 8오른쪽으로 한 칸 이동
# 2) 4와 5비교 → 5오른쪽으로 한 칸 이동
# 3) 4와 3비교 → 3뒤에 4위치
[3, 4, 5, 8] + [2] → 4 정렬

# 4회전
# 1) 2를 꺼내 8과 비교 → 8오른쪽으로 한 칸 이동
# 2) 2와 5비교 → 5오른쪽으로 한 칸 이동
# 3) 4와 2비교 → 4오른쪽으로 한 칸 이동
# 3) 3와 2비교 → 3오른쪽으로 한 칸 이동
[2, 3, 4, 5, 8] → 2 정렬

# 최종결과
[2, 3, 4, 5, 8]

---

3_2) 삽입 정렬의 시간복잡도

초기 단계에선 이미 정렬이 되어 있는 배열일 경우 비교만 수행하고 이동이 발생하지 않기 때문에 O(n)의 시간복잡도를 가진다.
반대로 역순으로 정렬된 배열의 경우 모든 요소를 앞쪽으로 이동시켜야 하므로 O(n²)의 시간복잡도를 가지게 된다.

• 평균 / 최악 : O(n²)
• 최선 : O(n)

---

3_3) 삽입 정렬의 장단점

👍 삽입정렬 장점

• 거의 정렬된 데이터에선 빠르게 작동한다.
• 구현이 간단하고 추가 메모리가 필요없다.

👎 삽입정렬 단점

• 데이터가 많을 경우 최악의 O(n²) 시간복잡도를 가진다.
• 데이터 이동이 자주 발생한다.

---

3_4) 삽입 정렬 파이썬 코드로 구현하기

✅ 기능 1) 바깥 반복문 : 범위지정, 삽입값 변수지정, 비교할 값 지정

바깥 반복문은 2번째 값부터 시작해야하기 때문에(1번째 값은 이미 정렬된것으로 봄)
range(1, len(array))를 사용하여 인덱스 2번부터 끝까지로 범위를 지정한다.
 
key = array[i] 로 현재 삽입할 값을 key 변수에 저장해주고,
삽입할 값인 i 와 비교할 부분은 왼쪽이기때문에 i-1이 되어 j = i - 1이 된다.

for i in range(1,len(array)):
    key = array[i]        
    j = i - 1

 

✅ 기능 2) 안쪽 while문 : 비교 반복

배열의 왼쪽 끝을 벗어나지 않고 반복을 진행하기 위해 j >= 0 조건을 걸어주고,
왼쪽 값이 key보다 클 때 계속 반복하기 위해 array[j] > key 조건을 걸어 반복문을 실행한다.
 
두 조건이 만족하는 동안 반복을 진행할 때
array[j+1] = array[j]를 통해 왼쪽 값을 오른쪽으로 한 칸씩 밀어주고
비교위치를 한칸 더 왼쪽으로 이동시키기 위해 j -= 1을 추가한다.
 
반복이 종료되면 key가 들어갈 자리를 찾은 것으로
찾은 자리에 key를 넣어준다.

while j >= 0 and array[j] > key:
    array[j+1] = array[j] 
    j -= 1
array[j+1] = key

 

✅ 기능 3) 오름차순과 내림차순

내림차순 정렬은 while문의  array[j]와 key 사이의 부등호를 바꿔서 내림차순으로 변경할 수 있다.

# 오름차순
while j >= 0 and array[j] > key:

# 내림차순
while j >= 0 and array[j] < key:

 

💡 삽입 정렬 최종코드 : 오름차순

# 오름차순 최종코드
import random
def insertion_asc(array):
    # 바깥 반복문
    for i in range(1,len(array)):
        key = array[i]        
        j = i - 1           

        # 안쪽 while문
        while j >= 0 and array[j] > key:
            array[j+1] = array[j] 
            j -= 1           
        array[j+1] = key

    return array 

# random.sample(뽑을대상, 개수)
random_insertion_data = random.sample(range(1,100), 5)

print("삽입 정렬 데이터:", random_insertion_data)
print("삽입 정렬 결과",insertion_asc(random_insertion_data))

실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.

 

💡 삽입 정렬 최종코드 : 내림차순

# 내림차순 최종코드
import random
def insertion_desc(array):
    # 바깥 반복문
    for i in range(1,len(array)):
        key = array[i]        
        j = i - 1           

        # 안쪽 while문 : 내림차순 변경!
        while j >= 0 and array[j] < key:
            array[j+1] = array[j] 
            j -= 1           
        array[j+1] = key

    return array 

# random.sample(뽑을대상, 개수)
random_insertion_data = random.sample(range(1,100), 5)

print("삽입 정렬 데이터:", random_insertion_data)
print("삽입 정렬 결과",insertion_desc(random_insertion_data))

실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.