[알고리즘] 버블 정렬, 선택 정렬, 삽입 정렬

1. 정렬 알고리즘이란

 

2. 버블 정렬

• 정의
• 오름차순/내림차순 구현

3. 선택 정렬

• 정의
• 오름차순/내림차순 구현

4. 삽입 정렬

• 정의
• 오름차순/내림차순 구현

5.random 데이터를 생성하여 성능 비교

---

1. 정렬 알고리즘  Sorting Algorithm

• 졍렬 : 데이터를 어떤 기준(오름차순, 내림차순 등)에 따라 순서대로 나열
• 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능
• 종류
  • 비교 기반 정렬 : 데이터를 서로 비교하여 정렬하는 정렬 ex.버블, 선택, 삽입, 병합, 퀵, 힙
  • 비비교 기반 정렬 : 데이터 간의 직접적인 비교없이 정렬 ex. 계수, 기수

---

2. 버블 정렬 Bubble Sort

1. 버블 정렬이란

• 인접한 두 원소를 비교하여 자리 교환
• 장점 : 구현이 매우 간단
• 단점 : 하나의 요소가 왼쪽에서 가장 오른쪽으로 이동하기 위해 배열의 모든 요소들과 교환되어야 함
• 시간복잡도 : O(n²)

2. 오름차순 구현

1. 매개변수로 배열을 받아온다
   
   
2. 바깥 루프는 (배열길이) - 1 만큼 돌면 된다
   - 마지막 남은 요소는 자동으로 위치가 정해지기 때문이다
   - 한 번 돌 때마다 가장 큰 수가 맨 뒤로 확정된다
   - 확정된 숫자 제외한만큼 안쪽 루프 수행하면 된다
   
   
3. 안쪽 루프는 j번째와 j+1번째를 비교하는데, j+1이 범위를 넘으면 안되므로 (배열길이) - i - 1 이 된다
   
   
4. j번째와 j+1번째의 데이터를 비교하여 왼쪽 데이터가 더 크면 자리를 swap
   
   
5. 정렬된 배열을 반환한다

# 버블 정렬 - 오름차순
def bubble_sort_asc(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

arr = [3, 6, 9, 2, 8, 6, 11, 10]
print(bubble_sort_asc(arr))		# [2, 3, 6, 6, 8, 9, 10, 11]

 

3. 내림차순 구현 : 오름차순에서 조건문만 변경해주면 쉽게 구현 가능

# 버블 정렬 - 내림차순
def bubble_sort_desc(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] < arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

arr = [3, 6, 9, 2, 8, 6, 11, 10]
print(bubble_sort_desc(arr))		# [11, 10, 9, 8, 6, 6, 3, 2]

---

3. 선택 정렬 Selection Sort

1. 선택 정렬이란

• 처리되지 않은 데이터 중, 가장 작은 데이터(또는 가장 큰 데이터)를 선택해 맨 앞에 있는 데이터와 바꾸는 것 반복
• 장점 : 알고리즘이 단순하고 구현이 쉬움
• 단점 : 배열이 길어질수록 시간이 지수적으로 증가하여 비효율
• 시간복잡도 : O(n²)

2. 오름차순 구현

1. 매개변수로 배열을 받아온다
2. 바깥 루프는 (배열길이) - 1 만큼 돈다
   - 마지막 남은 요소는 자동으로 위치가 정해지기 때문이다
3. 바깥 루프 내부에서 최솟값의 인덱스를 담을 변수(min)를 i로 초기화한다
4. 안쪽 루프는 이미 정렬된 i 까지의 요소를 제외하고 i+1부터 배열의 끝까지 돈다
5. 안쪽 루프를 돌면서 arr[j]가 arr[min]보다 작으면(오름차순) min을 j로 갱신한다
   
6. min 인덱스 갱신 후 안쪽 루프 밖에서 min 인덱스에 해당하는 요소와 현재 요소의 자리를 swap
   
   
7. 정렬된 배열을 반환한다

# 선택 정렬 - 오름차순
def selection_sort_asc(arr):
    for i in range(len(arr) - 1):
        min = i
        for j in range(i + 1, len(arr)):
            if arr[min] > arr[j]:
                min = j
        arr[min], arr[i] = arr[i], arr[min]
    return arr

arr = [3, 6, 9, 2, 8, 6, 11, 10]
print(selection_sort_asc(arr))      # [2, 3, 6, 6, 8, 9, 10, 11]

 

3. 내림차순 구현 : 오름차순에서 조건문만 변경해주면 쉽게 구현 가능

# 선택 정렬 - 내림차순
def selection_sort_desc(arr):
    for i in range(len(arr) - 1):
        min = i
        for j in range(i + 1, len(arr)):
            if arr[min] < arr[j]:
                min = j
        arr[min], arr[i] = arr[i], arr[min]
    return arr

arr = [3, 6, 9, 2, 8, 6, 11, 10]
print(selection_sort_desc(arr))      # [11, 10, 9, 8, 6, 6, 3, 2]

---

4. 삽입 정렬 Insertion Sort

1. 삽입 정렬이란

• 특정 데이터를 적절한 위치에 삽입
• 특정 데이터가 적절 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정
• 장점 : 실행 시간 측면에서 효율적
• 단점 : 선택 정렬에 비해 구현 난이도가 높음
• 시간복잡도 : O(n²)

2. 오름차순 구현

1. 매개변수로 배열을 받아온다
   
   
2. 외부 루프는 배열의 두번째 요소부터 마지막 요소까지 돈다
   - 두 번째 요소부터 바로 왼쪽 요소와 비교하며 자리를 바꿀 것이기 때문이다
   
   
3. 내부 루프는 현재 인덱스부터 맨 처음 인덱스까지 돈다
   
   
4. 현재 인덱스의 데이터와 바로 왼쪽 인덱스의 데이터를 비교하여 조건에 맞으면 swap
   
   
5. 정렬된 배열을 반환한다

# 삽입 정렬 - 오름차순
def insertion_sort_asc(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr
        
arr = [3, 6, 9, 2, 8, 6, 11, 10]
print(insertion_sort_asc(arr))      # [2, 3, 6, 6, 8, 9, 10, 11]

 

3. 내림차순 구현 : 오름차순에서 조건문만 변경해주면 쉽게 구현 가능

# 삽입 정렬 - 내림차순def insertion_sort_desc(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] > arr[j-1]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr

arr = [3, 6, 9, 2, 8, 6, 11, 10]
print(insertion_sort_desc(arr))     # [11, 10, 9, 8, 6, 6, 3, 2]

---

5. random 데이터를 생성하여 성능 비교

1. 랜덤값과 시간측정에 필요한 모듈 import
   
   
2. 버블, 선택, 삽입 정렬의 오름차순 구현한 코드들을 가져온다
3. random 배열 생성한다
   - 시드를 사용하여 같은 랜덤 배열로 사용할 수 있도록 한다
   - 정렬 함수마다 다른 배열을 정렬하여 비교하게 되면 정확한 성능 비교가 되지 않을 수 있기 때문이다
   
   
4. time 모듈로 시작과 끝을 담을 변수를 생성한다
   
   
5. 의미있는 결과를 위해 범위와 개수를 크게 지정하여 랜덤 배열을 생성
   - range(0, 10000) : 0부터 9999까지 숫자 범위
   - 5000 : 그중에서 5000개를 뽑기
   - sample : 중복없이 랜덤으로 뽑기
6. 각 정렬 함수들을 실행하여 시간 측정한 결과를 출력한다

• 결과 :
  • 버블 정렬과 삽입 정렬은 비슷한 성능이고, 선택 정렬이 조금 더 빠른 것을 확인 할 수 있다
  • 세 정렬 모두 시간복잡도가 O(n²)이지만 선택 정렬은 swap 횟수가 적기 때문이다
  • swap하는 코드의 위치를 보면
    선택 정렬은 바깥 루프 안에서 swap되고
    버블과 삽입 정렬은 안쪽 루프 안에서 swap되는 것을 확인할 수 있다

import random
import time

# 버블 정렬
def bubble_sort_asc(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 선택 정렬
def selection_sort_asc(arr):
    for i in range(len(arr) - 1):
        min = i
        for j in range(i + 1, len(arr)):
            if arr[min] > arr[j]:
                min = j
        arr[min], arr[i] = arr[i], arr[min]
    return arr

# 삽입 정렬
def insertion_sort_asc(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr

random.seed(10)
start = time.time()
arr1= random.sample(range(0, 10000), 5000)
bubble_sort_asc(arr1)
end = time.time()
print(f"버블 정렬 : {(end-start) * 10}")

random.seed(10)
start = time.time()
arr2= random.sample(range(0, 10000), 5000)
selection_sort_asc(arr2)
end = time.time()
print(f"선택 정렬 : {(end-start) * 10}")

random.seed(10)
start = time.time()
arr3= random.sample(range(0, 10000), 5000)
insertion_sort_asc(arr3)
end = time.time()
print(f"삽입 정렬 : {(end-start) * 10}")

---

[과제 후기]

* 조건문을 작성하는 과정에서 오름차순인지 내림차순인지에 따라 값을 비교하는 부분의 부등호를 정하는 것에서 헷갈렸다. 내가 어떤 기준에 의해 정렬할 것인지 (오름/내림) 생각하면서 작성할 필요가 있다. 필요없는 변수를 사용했다가 내부에서 필요가 없어 지운 변수도 있었다.  

 

* 시간복잡도가 같더라도 성능의 차이가 발생할 수 있다

 

* 파이썬 개념 강의에서 배운 random과 seed를 사용해볼 수 있었고, 시간을 측정하는 time 모듈도 사용해볼 수 있었다.