📊 정렬 알고리즘 정리

1. 버블 정렬 (Bubble Sort)

📌 개념

버블 정렬은 처음부터 끝까지 인접한 원소를 비교하며 큰 값을 뒤로 보내는 방
마치 "큰 값이 거품처럼 위(뒤)로 올라간다" 하여 버블 정렬이라함

• 시간 복잡도: O(n²)
• 구현은 단순하지만 비효율적

💻 예제 코드

nums = [10, 2, 7, 21, 0]

print("정렬 전:", nums)

for i in range(len(nums) - 1):
    for j in range(len(nums) - i - 1):
        if nums[j] > nums[j+1]:
            nums[j], nums[j+1] = nums[j+1], nums[j]

print("정렬 후:", nums)

정렬 전: [10, 2, 7, 21, 0]
정렬 후: [0, 2, 7, 10, 21]

💻 실습 코드

새 학년이 되어 20명의 학생이 모였다. 키(170~185cm) 를 난수로 생성하고, 키 순서(오름차순) 로 줄세워라.

-> 인접한 두 값을 비교해 큰 값을 뒤로 밀면서 끝까지 반복

import random

# 데이터 생성 : 170~185 랜덤 20명
heights = [random.randint(170,185) for _ in range(20)]
print(f'before:{heights}')

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

print(f'after:{heights}')

before:[182, 173, 170, 180, 178, 183, 184, 176, 181, 176, 175, 185, 174, 171, 171, 182, 179, 172, 180, 179]
after:[170, 171, 171, 172, 173, 174, 175, 176, 176, 178, 179, 179, 180, 180, 181, 182, 182, 183, 184, 185]

2. 삽입 정렬 (Insertion Sort)

📌 개념

정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 방식
새로운 카드를 손에 쥘 때 알맞은 위치에 꽂는 것과 비슷

• 시간 복잡도: O(n²)
• 거의 정렬된 데이터일 경우 효율적

💻 예제 코드

nums = [5, 10, 2, 1, 0]

print("정렬 전:", nums)

for i in range(1, len(nums)):
    key = nums[i]
    j = i - 1
    while j >= 0 and nums[j] > key:
        nums[j+1] = nums[j]
        j -= 1
    nums[j+1] = key

print("정렬 후:", nums)

정렬 전: [5, 10, 2, 1, 0]
정렬 후: [0, 1, 2, 5, 10]

---

💻 실습 코드

과제: 1~1000 사이 난수 100개 생성 후

(1) 오름차순 또는 내림차순 정렬 알고리즘 구현
(2) 최솟값·최댓값을 반환하는 함수 구현
-> 왼쪽부터 정렬된 부분을 유지하면서, 새 원소를 알맞은 위치에 삽입

import random

# 1) 데이터 생성: 1 ~ 1000 사이에서 100개
nums = [random.randint(1, 1000) for _ in range(100)]
print("정렬 전:", nums)

# 2) 삽입 정렬 (order='asc' 또는 'desc')
def insertion_sort(arr, order='asc'):
    a = arr[:]  # 원본 보존
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        if order == 'asc':
            while j >= 0 and a[j] > key:
                a[j + 1] = a[j]
                j -= 1
        else:  # desc
            while j >= 0 and a[j] < key:
                a[j + 1] = a[j]
                j -= 1
        a[j + 1] = key
    return a

# 3) 최솟값 / 최댓값 함수 (내장 min/max 미사용, O(n))
def get_min(arr):
    m = arr[0]
    for x in arr[1:]:
        if x < m:
            m = x
    return m

def get_max(arr):
    M = arr[0]
    for x in arr[1:]:
        if x > M:
            M = x
    return M

sorted_asc = insertion_sort(nums, 'asc')
sorted_desc = insertion_sort(nums, 'desc')

print("오름차순:", sorted_asc)
print("내림차순:", sorted_desc)
print("최솟값:", get_min(nums))
print("최댓값:", get_max(nums))

정렬 전: [329, 232, 678, 204, 226, 171, 561, 112, 547, 153, 7, 406, 624, 572, 545, 274, 264, 631, 373, 912, 163, 165, 461, 255, 652, 278, 883, 7, 161, 441, 230, 264, 906, 932, 715, 13, 505, 652, 695, 839, 283, 776, 171, 920, 732, 749, 321, 182, 105, 309, 266, 602, 180, 351, 653, 6, 544, 698, 638, 466, 406, 460, 680, 210, 569, 373, 183, 293, 596, 277, 812, 366, 681, 611, 882, 344, 600, 703, 127, 542, 1, 853, 199, 649, 70, 761, 395, 375, 136, 462, 349, 361, 931, 981, 75, 130, 434, 801, 454, 368]
오름차순: [1, 6, 7, 7, 13, 70, 75, 105, 112, 127, 130, 136, 153, 161, 163, 165, 171, 171, 180, 182, 183, 199, 204, 210, 226, 230, 232, 255, 264, 264, 266, 274, 277, 278, 283, 293, 309, 321, 329, 344, 349, 351, 361, 366, 368, 373, 373, 375, 395, 406, 406, 434, 441, 454, 460, 461, 462, 466, 505, 542, 544, 545, 547, 561, 569, 572, 596, 600, 602, 611, 624, 631, 638, 649, 652, 652, 653, 678, 680, 681, 695, 698, 703, 715, 732, 749, 761, 776, 801, 812, 839, 853, 882, 883, 906, 912, 920, 931, 932, 981]
내림차순: [981, 932, 931, 920, 912, 906, 883, 882, 853, 839, 812, 801, 776, 761, 749, 732, 715, 703, 698, 695, 681, 680, 678, 653, 652, 652, 649, 638, 631, 624, 611, 602, 600, 596, 572, 569, 561, 547, 545, 544, 542, 505, 466, 462, 461, 460, 454, 441, 434, 406, 406, 395, 375, 373, 373, 368, 366, 361, 351, 349, 344, 329, 321, 309, 293, 283, 278, 277, 274, 266, 264, 264, 255, 232, 230, 226, 210, 204, 199, 183, 182, 180, 171, 171, 165, 163, 161, 153, 136, 130, 127, 112, 105, 75, 70, 13, 7, 7, 6, 1]
최솟값: 1
최댓값: 981

3. 선택 정렬 (Selection Sort)

📌 개념

리스트에서 가장 작은 값을 선택해 맨 앞으로 옮기며 정렬하는 방식

• 시간 복잡도: O(n²)
• 단순하지만 교환 횟수가 적음

💻 실습 코드

과제: 학생 20명의 시험 점수(50~100) 를 난수로 생성하고, 오름차순/내림차순으로 정렬하는 모듈만들기

-> 매 단계마다 가장 작은 혹은 큰 값의 위치를 찾아 현재 위치와 교환

import random

# 1) 데이터 생성: 50 ~ 100 사이 점수 20명
scores = [random.randint(50, 100) for _ in range(20)]
print("정렬 전(점수):", scores)

def selection_sort(arr, order='asc'):
    a = arr[:]
    n = len(a)
    for i in range(n):
        sel = i
        for j in range(i + 1, n):
            if (order == 'asc' and a[j] < a[sel]) or (order == 'desc' and a[j] > a[sel]):
                sel = j
        a[i], a[sel] = a[sel], a[i]
    return a

asc_scores = selection_sort(scores, 'asc')
desc_scores = selection_sort(scores, 'desc')

print("오름차순:", asc_scores)
print("내림차순:", desc_scores)

정렬 전(점수): [50, 65, 73, 84, 94, 97, 90, 51, 96, 52, 51, 82, 76, 80, 94, 56, 82, 90, 70, 56]
오름차순: [50, 51, 51, 52, 56, 56, 65, 70, 73, 76, 80, 82, 82, 84, 90, 90, 94, 94, 96, 97]
내림차순: [97, 96, 94, 94, 90, 90, 84, 82, 82, 80, 76, 73, 70, 65, 56, 56, 52, 51, 51, 50]

---

✅ 정리 & 팁

• 세 알고리즘 모두 시간복잡도 O(n²) → 데이터가 많아지면 느림.
• 실무/대용량 데이터에선 퀵/병합/힙 정렬과 같은 고급 알고리즘 또는 라이브러리 사용 추천.
• 버블: 인접 비교·스왑 → 가장 비효율적
• 삽입: 정렬된 부분 + 삽입 위치 찾기
• 선택: 최솟값(또는 최댓값) 위치 선정 + 교체