버블 정렬, 삽입 정렬, 선택 정렬

버블 정렬

버블 정렬(Bubble Sort)은 간단하면서도 비효율적인 정렬 알고리즘 중 하나이다. 이 알고리즘은 인접한 두 원소의 값을 비교하여 정렬하는 방식으로 동작한다. 구체적으로는 인접한 두 원소를 비교하여 큰 값을 오른쪽으로 이동시키고, 이를 반복하여 정렬을 수행한다.

처음에는 첫 번째 원소와 두 번째 원소를 비교하여 큰 값을 뒤로 이동시키며, 이를 반복하면서 가장 큰 값이 맨 뒤로 이동한다. 이 과정을 반복하면서 정렬을 수행하는 것이 버블 정렬의 핵심이다.

버블 정렬의 특징

• 구현이 쉽다.
• 안정 정렬(Stable Sort)이다. 즉, 동일한 값을 가지는 원소들의 순서가 정렬 전과 동일하게 유지된다.
• 시간 복잡도는 O(n^2)으로 매우 비효율적이다.
• 버블 정렬은 구현이 쉬워서 가끔 사용되지만, 시간 복잡도가 매우 높기 때문에 대부분의 상황에서는 다른 정렬 알고리즘을 사용하는 것이 좋다.

def bubble_sort(arr):
    n = len(arr)
    
    # 모든 원소를 순회하면서 정렬 수행
    for i in range(n):
        
        # 인접한 두 원소 비교
        for j in range(n-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j] # Swap
                
    return arr

연습 문제

새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워 보자. 학생들의 키는 random 모듈을 이용해서 170 ~ 185사이로 생성한다.

import random

# 학생 클래스
class Student:
    def __init__(self, height):
        self.height = height
    
    def __repr__(self):
        return str(self.height)

# 학생들을 생성하는 함수
def generate_students(num_students):
    students = []
    for i in range(num_students):
        height = random.randint(170, 185)
        student = Student(height)
        students.append(student)
    return students

# 버블 정렬을 이용하여 학생들을 키 순서로 정렬하는 함수
def sort_students(students):
    n = len(students)
    for i in range(n-1):
        for j in range(n-i-1):
            if students[j].height > students[j+1].height:
                students[j], students[j+1] = students[j+1], students[j]
    return students

# 학생들을 생성하고 키 순서로 정렬하여 출력
if __name__ == '__main__':
    students = generate_students(20)
    print("Before sorting:", students)
    sorted_students = sort_students(students)
    print("After sorting:", sorted_students)
    
'''
Before sorting: [185, 176, 176, 179, 181, 173, 182, 172, 179, 178, 181, 176, 185, 184, 177, 172, 174, 170, 175, 177]
After sorting: [170, 172, 172, 173, 174, 175, 176, 176, 176, 177, 177, 178, 179, 179, 181, 181, 182, 184, 185, 185]
'''

---

삽입 정렬

삽입 정렬(Insertion Sort)은 간단하면서도 비교적 효율적인 정렬 알고리즘 중 하나이다. 이 알고리즘은 정렬되지 않은 원소를 하나씩 정렬된 원소들의 적절한 위치에 삽입하여 정렬하는 방식으로 동작한다. 구체적으로는 정렬되지 않은 원소를 하나씩 꺼내서, 이를 이미 정렬된 원소들과 비교하여 적절한 위치에 삽입한다.

처음에는 첫 번째 원소를 이미 정렬된 원소들과 비교하여 적절한 위치에 삽입한다. 그 다음에는 두 번째 원소를 삽입할 위치를 찾아 삽입한다. 이 과정을 반복하면서 정렬을 수행하는 것이 삽입 정렬의 핵심이다.

삽입 정렬의 특징

• 구현이 쉽다.
• 안정 정렬(Stable Sort)이다. 즉, 동일한 값을 가지는 원소들의 순서가 정렬 전과 동일하게 유지된다.
• 평균적인 시간 복잡도는 O(n^2)으로 비교적 느리지만, 최선의 경우 O(n)으로 매우 빠르다.

삽입 정렬은 평균적으로 O(n^2)의 시간 복잡도를 가지기 때문에 매우 느린 알고리즘이라고 생각할 수 있다. 하지만, 이미 정렬된 배열이나 거의 정렬된 배열에서는 매우 빠른 성능을 보이는 장점이 있다. 또한, 원소의 개수가 적은 경우에는 다른 정렬 알고리즘보다 효율적인 경우가 많다.

def insertion_sort(arr):
    n = len(arr)
    
    # 모든 원소를 순회하면서 정렬 수행
    for i in range(1, n):
        key = arr[i] # 현재 원소
        j = i - 1 # 이미 정렬된 부분의 마지막 인덱스
        
        # 현재 원소를 이미 정렬된 부분의 적절한 위치에 삽입
       

연습 문제

1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.

• 요구 사항1) 생성된 난수들을 오름 차순 또는 내림 차순으로 정렬하는 알고리즘 구현
• 요구 사항2) 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현

import random

# 1부터 1000까지의 난수 100개 생성
nums = [random.randint(1, 1000) for _ in range(100)]

# 삽입정렬 알고리즘 구현
def insertion_sort(nums, reverse=False):
    n = len(nums)
    for i in range(1, n):
        key = nums[i]
        j = i-1
        if reverse:
            while j >= 0 and nums[j] < key:
                nums[j+1] = nums[j]
                j -= 1
        else:
            while j >= 0 and nums[j] > key:
                nums[j+1] = nums[j]
                j -= 1
        nums[j+1] = key
    return nums

# 최솟값과 최댓값 반환 함수 구현
def get_min_max(nums):
    min_val = min(nums)
    max_val = max(nums)
    return min_val, max_val

# 삽입정렬을 이용하여 오름차순으로 정렬 후 출력
sorted_nums = insertion_sort(nums)
print("Ascending order:", sorted_nums)

# 삽입정렬을 이용하여 내림차순으로 정렬 후 출력
reverse_sorted_nums = insertion_sort(nums, reverse=True)
print("Descending order:", reverse_sorted_nums)

# 최솟값과 최댓값 출력
min_val, max_val = get_min_max(nums)
print("Minimum value:", min_val)
print("Maximum value:", max_val)

'''
Ascending order: [12, 17, 18, 35, 39, 63, 66, 70, 88, 132, 144, 147, 150, 155, 180, 201, 202, 222, 223, 233, 234, 252, 280, 286, 295, 302, 304, 306, 312, 331, 340, 340, 342, 348, 368, 388, 426, 439, 441, 449, 452, 454, 459, 460, 464, 466, 472, 481, 499, 515, 520, 531, 536, 541, 561, 562, 575, 584, 585, 585, 600, 601, 602, 610, 629, 634, 645, 645, 645, 648, 648, 651, 669, 699, 700, 725, 727, 732, 739, 743, 747, 756, 763, 768, 788, 825, 838, 843, 853, 862, 862, 883, 888, 888, 897, 908, 911, 974, 981, 1000]
Descending order: [1000, 981, 974, 911, 908, 897, 888, 888, 883, 862, 862, 853, 843, 838, 825, 788, 768, 763, 756, 747, 743, 739, 732, 727, 725, 700, 699, 669, 651, 648, 648, 645, 645, 645, 634, 629, 610, 602, 601, 600, 585, 585, 584, 575, 562, 561, 541, 536, 531, 520, 515, 499, 481, 472, 466, 464, 460, 459, 454, 452, 449, 441, 439, 426, 388, 368, 348, 342, 340, 340, 331, 312, 306, 304, 302, 295, 286, 280, 252, 234, 233, 223, 222, 202, 201, 180, 155, 150, 147, 144, 132, 88, 70, 66, 63, 39, 35, 18, 17, 12]
Minimum value: 12
Maximum value: 1000
'''

---

선택 정렬

선택 정렬(Selection sort)은 배열 안에서 최소값을 찾아 맨 앞에 위치시키고, 그 다음으로 작은 값을 찾아 두 번째 위치에 놓는 작업을 반복하여 정렬하는 알고리즘이다.

선택 정렬은 배열의 길이가 길어질수록 성능이 저하되는 단점이 있지만, 구현이 간단하고 코드가 직관적이어서 가장 간단한 정렬 알고리즘 중 하나이다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

위 코드에서 arr은 정렬할 배열이며, n은 배열의 길이이다. 첫 번째 for 루프는 정렬할 범위를 정한다. 0번째 인덱스부터 n-1번째 인덱스까지 반복하면서 최소값을 찾아 해당 위치와 현재 위치를 교환한다.

내부 for 루프에서는 현재 인덱스(i)부터 마지막 인덱스(n-1)까지 반복하면서 최소값의 인덱스를 찾는다다. 최소값을 찾은 뒤, 현재 위치(i)와 최소값의 위치(min_idx)를 교환한다.

arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr)

# [11, 12, 22, 25, 64]

---

연습 문제

선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. 시험 점수는 50부터 100까지로 한다.

import random

def selection_sort_ascending(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

def selection_sort_descending(arr):
    n = len(arr)
    for i in range(n):
        max_idx = i
        for j in range(i+1, n):
            if arr[j] > arr[max_idx]:
                max_idx = j
        arr[i], arr[max_idx] = arr[max_idx], arr[i]
    return arr

# 시험 점수를 랜덤으로 생성
scores = [random.randint(50, 100) for _ in range(20)]
print("Original Scores:", scores)

# 오름차순으로 정렬
sorted_scores_ascending = selection_sort_ascending(scores)
print("Ascending Scores:", sorted_scores_ascending)

# 내림차순으로 정렬
sorted_scores_descending = selection_sort_descending(scores)
print("Descending Scores:", sorted_scores_descending)

'''
Original Scores: [82, 66, 68, 71, 71, 81, 60, 78, 98, 82, 70, 68, 64, 70, 78, 55, 88, 95, 71, 52]
Ascending Scores: [52, 55, 60, 64, 66, 68, 68, 70, 70, 71, 71, 71, 78, 78, 81, 82, 82, 88, 95, 98]
Descending Scores: [98, 95, 88, 82, 82, 81, 78, 78, 71, 71, 71, 70, 70, 68, 68, 66, 64, 60, 55, 52]
'''