Chapter 11 - 정렬 기본 (Basic Sorting)

Chapter 11

정렬 기본

Basic Sorting

Part 1  정렬의 개념과 선택 정렬 · Sorting Concept & Selection Sort
Part 2  삽입 정렬 · Insertion Sort
Part 3  정렬의 응용 · Sorting Applications

01

Part 1

정렬의 개념과 선택 정렬

Sorting Concept & Selection Sort

정렬의 기본 개념, 정렬 알고리즘의 종류, 선택 정렬의 원리와 구현을 학습합니다.

정렬이란?

What is Sorting?

한국어

정렬의 개념

정렬(Sort)이란 자료들을 일정한 순서대로 나열하는 것입니다. 컴퓨터 과학에서 가장 기본이 되는 알고리즘 중 하나입니다.

🃏 생활 속 비유 — 카드 정리

카드 게임을 할 때, 받은 카드를 손에 들고 작은 숫자부터 큰 숫자 순서로 정리하지 않나요? 이것이 바로 정렬입니다!

또 다른 예: 학교 출석부(학번 순), 사전(가나다 순), 칼 정리(크기 순)

        정렬의 두 가지 방향

        · 오름차순(Ascending) : 작은 값 → 큰 값 (1, 2, 3, 4, 5)

          예) 키 순서로 줄 서기: 작은 사람 → 큰 사람

        · 내림차순(Descending) : 큰 값 → 작은 값 (5, 4, 3, 2, 1)

          예) 성적 순위: 1등 → 꼴등

정렬 알고리즘의 종류

알고리즘	방식 (쉬운 설명)	성능
선택 정렬	제일 작은 것을 골라 앞으로	O(n²)
삽입 정렬	알맞은 자리에 끼워넣기	O(n²)
버블 정렬	옆끼리 비교해서 교환	O(n²)
퀵 정렬	반씩 나누어 정복	O(n log n)

이번 장에서 배울 것: 선택 정렬과 삽입 정렬. 둘 다 원리가 간단하여 초보자가 정렬을 이해하기에 좋습니다!

English

Concept of Sorting

Sorting is arranging data in a specific order. It is one of the most fundamental algorithms in computer science.

🃏 Real-life Analogy — Organizing Cards

When playing card games, don't you arrange your cards from smallest to largest? That's exactly sorting!

More examples: school roster (by student ID), dictionary (alphabetical), organizing knives (by size)

        Two Directions of Sorting

        · Ascending : small → large (1, 2, 3, 4, 5)

          e.g.) Lining up by height: shortest → tallest

        · Descending : large → small (5, 4, 3, 2, 1)

          e.g.) Ranking by grade: 1st → last

Types of Sorting Algorithms

Algorithm	Method (Simple)	Performance
Selection Sort	Pick smallest, move to front	O(n²)
Insertion Sort	Insert at the right spot	O(n²)
Bubble Sort	Compare neighbors & swap	O(n²)
Quick Sort	Divide in half & conquer	O(n log n)

What we'll learn: Selection Sort and Insertion Sort. Both are simple in principle and great for beginners!

최솟값 찾기와 기본 선택 정렬

Finding Minimum & Basic Selection Sort

한국어

선택 정렬의 핵심 — 최솟값 찾기

선택 정렬(Selection Sort)은 배열에서 가장 작은 값을 선택하여 앞으로 보내는 과정을 반복합니다.

🏫 비유 — 키 순서로 줄 세우기

체육시간에 키 순서로 줄을 세울 때: ① 전체 중 키가 가장 작은 학생을 찾아서 맨 앞에 세우고 ② 나머지 중에서 또 가장 작은 학생을 찾아 두 번째에 세우고... 이걸 반복합니다. 이것이 선택 정렬입니다!

        최솟값 찾기 알고리즘 (단계별)

        ① 배열의 첫 번째 값을 "현재 최솟값"으로 지정

        ② 다음 값과 비교하여 더 작으면 "현재 최솟값" 교체

        ③ 마지막까지 비교 완료 후 최솟값 위치 확정

Code11-01 : 최솟값 위치 찾기

def findMinIdx(ary):
    minIdx = 0           # ① 첫 번째를 최소로 가정
    for i in range(1, len(ary)):  # ② 두 번째부터 끝까지
        if (ary[minIdx] > ary[i]):  # ③ 더 작은 값 발견?
            minIdx = i          # ④ 최소 위치 갱신!
    return minIdx              # ⑤ 최솟값의 위치 반환

testAry = [55, 88, 33, 77]
minPos = findMinIdx(testAry)
print('최솟값 -->', testAry[minPos])

코드 핵심 이해:
· minIdx = 0 : "일단 [0]번이 제일 작다고 치자"
· if ary[minIdx] > ary[i] : "지금 최소보다 더 작은 값이 있니?"
· minIdx = i : "더 작은 걸 찾았으니 갱신!"
· 반환값은 값이 아니라 위치(인덱스)입니다!

Code11-02 : 기본 선택 정렬 (배열 2개)

def findMinIdx(ary):
    minIdx = 0
    for i in range(1, len(ary)):
        if (ary[minIdx] > ary[i]):
            minIdx = i
    return minIdx

before = [188,162,168,120,50,150,177,105]
after = []              # 정렬 결과를 담을 빈 배열

print('정렬 전 -->', before)
for _ in range(len(before)):
    minPos = findMinIdx(before) # 최솟값 위치 찾기
    after.append(before[minPos]) # 결과 배열에 추가
    del(before[minPos])     # 원본에서 삭제
print('정렬 후 -->', after)

⚠️ 이 방법의 단점: 배열 2개(before, after)를 사용하므로 메모리가 2배 필요합니다. 다음 슬라이드에서 배열 1개만 쓰는 개선된 방식을 배웁니다!

English

Selection Sort Core — Finding Minimum

Selection Sort repeatedly selects the smallest value from the array and moves it to the front.

🏫 Analogy — Lining Up by Height

During PE class, lining up by height: ① Find the shortest student and place them first ② Find the next shortest and place them second... Repeat. This is Selection Sort!

        Find-Minimum Algorithm (Step by Step)

        ① Set the first value as "current minimum"

        ② Compare with next value; if smaller, update "current minimum"

        ③ After all comparisons, minimum position is confirmed

Code11-01 : Find Minimum Index

def findMinIdx(ary):
    minIdx = 0           # ① Assume first is minimum
    for i in range(1, len(ary)):  # ② From 2nd to end
        if (ary[minIdx] > ary[i]):  # ③ Found smaller?
            minIdx = i          # ④ Update min position!
    return minIdx              # ⑤ Return min position

testAry = [55, 88, 33, 77]
minPos = findMinIdx(testAry)
print('Min value -->', testAry[minPos])

Key Understanding:
· minIdx = 0 : "Let's assume [0] is the smallest"
· if ary[minIdx] > ary[i] : "Is there anything smaller?"
· minIdx = i : "Found something smaller, update!"
· Returns the position (index), not the value!

Code11-02 : Basic Selection Sort (2 Arrays)

def findMinIdx(ary):
    minIdx = 0
    for i in range(1, len(ary)):
        if (ary[minIdx] > ary[i]):
            minIdx = i
    return minIdx

before = [188,162,168,120,50,150,177,105]
after = []              # Empty array for results

print('Before -->', before)
for _ in range(len(before)):
    minPos = findMinIdx(before) # Find min position
    after.append(before[minPos]) # Add to result
    del(before[minPos])     # Delete from original
print('After -->', after)

⚠️ Drawback: Uses 2 arrays (before, after), requiring 2× memory. Next slide shows the improved version using only 1 array!

개선된 선택 정렬

Improved Selection Sort

한국어

배열 1개로 선택 정렬 (In-place)

추가 배열 없이, 원래 배열 안에서 최솟값을 찾아 현재 위치와 교환하는 방식입니다.

☕ 변수 교환 비유 — 컵 바꾸기

커피 컵(a)과 주스 컵(b)의 내용물을 바꾸려면? 빈 컵(tmp)이 하나 더 필요합니다!

        선택 정렬 동작 원리 (4개 데이터)

        매 사이클마다: ① 정렬 안 된 부분에서 최솟값 찾기 → ② 맨 앞과 교환

Code11-03 : 개선된 선택 정렬

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):      # 사이클 반복 (n-1번)
        minIdx = i              # 현재 위치를 최소로 가정
        for k in range(i+1, n):  # 나머지에서 최솟값 찾기
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]            # ┐
        ary[i] = ary[minIdx]    # ├ 두 값 교환 (swap)
        ary[minIdx] = tmp       # ┘
    return ary

dataAry = [188,162,168,120,50,150,177,105]
print('정렬 전 -->', dataAry)
dataAry = selectionSort(dataAry)
print('정렬 후 -->', dataAry)

한 줄 요약: "앞에서부터 자리를 채운다. 각 자리에 넣을 값은 남은 것 중 가장 작은 것을 선택한다."

English

In-place Selection Sort (1 Array)

Without an extra array, find the minimum and swap it with the current position within the original array.

☕ Swap Analogy — Exchanging Cups

To swap coffee cup (a) with juice cup (b)? You need an empty cup (tmp)!

        How Selection Sort Works (4 items)

        Each cycle: ① Find min in unsorted part → ② Swap with front position

Code11-03 : Improved Selection Sort

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):      # Cycle loop (n-1 times)
        minIdx = i              # Assume current is min
        for k in range(i+1, n):  # Find min in rest
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]            # ┐
        ary[i] = ary[minIdx]    # ├ Swap two values
        ary[minIdx] = tmp       # ┘
    return ary

dataAry = [188,162,168,120,50,150,177,105]
print('Before -->', dataAry)
dataAry = selectionSort(dataAry)
print('After -->', dataAry)

One-line Summary: "Fill positions from the front. For each position, select the smallest from what's left."

선택 정렬 성능 분석

Selection Sort Performance Analysis

한국어

비교 횟수 계산

정렬이 얼마나 느린지/빠른지를 판단하려면, "비교를 몇 번 하는가?"를 세면 됩니다.

🏫 비유 — 줄 세우기에 걸리는 시간

학생 4명을 줄 세우는 건 쉽습니다. 하지만 1000명이라면? 비교 횟수가 기하급수적으로 늘어납니다!

        데이터 4개(n=4)일 때 비교 횟수 세어보기

        사이클 1: [0]과 [1],[2],[3] 비교 → 3회

        사이클 2: [1]과 [2],[3] 비교 → 2회

        사이클 3: [2]와 [3] 비교 → 1회

        합계: 3 + 2 + 1 = 6회

O(n²)의 의미 쉽게:
· 데이터 10개 → 45번 비교 (감당 가능)
· 데이터 1000개 → 약 50만번 비교 (좀 느림)
· 데이터 100만개 → 약 5000억번 (불가능!)
결론: 데이터가 적을 때만 사용, 많으면 퀵 정렬 등 사용

English

Counting Comparisons

To judge how slow/fast sorting is, count "how many comparisons?"

🏫 Analogy — Time to Line Up

Lining up 4 students is easy. But 1000 students? The number of comparisons grows dramatically!

        Counting comparisons with 4 items (n=4)

        Cycle 1: Compare [0] with [1],[2],[3] → 3 times

        Cycle 2: Compare [1] with [2],[3] → 2 times

        Cycle 3: Compare [2] with [3] → 1 time

        Total: 3 + 2 + 1 = 6 times

O(n²) in plain terms:
· 10 items → 45 comparisons (manageable)
· 1000 items → ~500K comparisons (slow)
· 1 million items → ~500 billion (impossible!)
Conclusion: Use only for small data; use Quick Sort for large data

연습문제 Part 1

Practice Part 1

한국어

연습 1-1 : 개선된 선택 정렬 (Code11-03)

배열 [188, 162, 168, 120, 50, 150, 177, 105]를 선택 정렬로 오름차순 정렬하는 함수 selectionSort(ary)를 작성하시오. 배열 1개만 사용합니다.

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i
        for k in range(i+1, n):
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
    return ary

dataAry = [188,162,168,120,50,150,177,105]
print('정렬 전 -->', dataAry)
dataAry = selectionSort(dataAry)
print('정렬 후 -->', dataAry)

연습 1-2 : 최댓값 찾기 (Self11-01)

배열에서 최댓값의 위치를 반환하는 함수 findMaxIdx(ary)를 작성하시오.

힌트: findMinIdx와 비교 조건(>)만 <로 바꾸면 됩니다!

def findMaxIdx(ary):
    maxIdx = 0              # 첫번째를 최대로 가정
    for i in range(1, len(ary)):
        if (ary[maxIdx] < ary[i]):  # < 로 변경!
            maxIdx = i
    return maxIdx

testAry = [55, 88, 33, 77]
maxPos = findMaxIdx(testAry)
print('최댓값 -->', testAry[maxPos])

핵심 차이점: findMinIdx는 > (더 작은 것 찾기), findMaxIdx는 < (더 큰 것 찾기)

English

Practice 1-1 : Improved Selection Sort (Code11-03)

Write a function selectionSort(ary) to sort [188, 162, 168, 120, 50, 150, 177, 105] ascending using only 1 array.

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i
        for k in range(i+1, n):
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
    return ary

dataAry = [188,162,168,120,50,150,177,105]
print('Before -->', dataAry)
dataAry = selectionSort(dataAry)
print('After -->', dataAry)

Practice 1-2 : Find Maximum (Self11-01)

Write findMaxIdx(ary) that returns the maximum value's index.

Hint: Just change the comparison (>) to < in findMinIdx!

def findMaxIdx(ary):
    maxIdx = 0              # Assume first is max
    for i in range(1, len(ary)):
        if (ary[maxIdx] < ary[i]):  # Changed to < !
            maxIdx = i
    return maxIdx

testAry = [55, 88, 33, 77]
maxPos = findMaxIdx(testAry)
print('Max value -->', testAry[maxPos])

Key Difference: findMinIdx uses > (find smaller), findMaxIdx uses < (find larger)

02

Part 2

삽입 정렬

Insertion Sort

삽입 위치 찾기, 기본 삽입 정렬, 효율적인 삽입 정렬을 학습합니다.

삽입 정렬 개념과 삽입 위치 찾기

Insertion Sort Concept & Finding Insert Position

한국어

삽입 정렬이란?

삽입 정렬(Insertion Sort)은 기존 정렬된 데이터 중에서 자신의 위치를 찾아 삽입하는 방식입니다.

🃏 비유 — 카드 게임에서 카드 정리하기

카드를 한 장씩 받을 때, 이미 손에 든 카드 사이에서 알맞은 자리를 찾아 끼워넣는 것과 같습니다. 예: 손에 [3, 7, 9]가 있고 5를 받으면 → [3, 5, 7, 9] 사이에 넣습니다.

        삽입 위치 찾기 규칙 (3가지 경우)

        ① 빈 배열 → 첫 번째 자리에 삽입

        ② 자신보다 큰 값을 만나면 → 그 앞에 삽입

        ③ 큰 값이 없으면 → 맨 뒤에 삽입

Code11-04 : 삽입 위치 찾기

def findInsertIdx(ary, data):
    findIdx = -1              # ① 초기값: "아직 못 찾음"
    for i in range(0, len(ary)):
        if (ary[i] > data):       # ② 나보다 큰 값 발견!
            findIdx = i           # ③ 그 위치 기억
            break                 # ④ 더 볼 필요 없음, 중단
    if findIdx == -1:          # ⑤ 나보다 큰 값이 없었다면
        return len(ary)         #    → 맨 뒤에 삽입
    else:
        return findIdx          #    → 찾은 위치에 삽입

testAry = [33, 77, 88]
insPos = findInsertIdx(testAry, 55)
print('삽입할 위치 -->', insPos)
# 결과: 1 (77 앞에 삽입)

findInsertIdx 이해 포인트:
· break를 쓰는 이유: 처음 만난 큰 값 위치만 알면 됨
· findIdx == -1: 배열 전체에서 나보다 큰 값이 없음 = 내가 제일 큼 → 맨 뒤에

English

What is Insertion Sort?

Insertion Sort works by finding the right position in already-sorted data and inserting the element there.

🃏 Analogy — Organizing Cards in Hand

When receiving cards one by one, you find the right spot among cards already in hand and slide it in. e.g.: Hand has [3, 7, 9], receive 5 → [3, 5, 7, 9]

        Finding Insert Position Rules (3 Cases)

        ① Empty array → insert at first position

        ② Find a larger value → insert before it

        ③ No larger value → insert at the end

Code11-04 : Find Insert Position

def findInsertIdx(ary, data):
    findIdx = -1              # ① Init: "not found yet"
    for i in range(0, len(ary)):
        if (ary[i] > data):       # ② Found larger value!
            findIdx = i           # ③ Remember position
            break                 # ④ No need to look further
    if findIdx == -1:          # ⑤ No larger value found
        return len(ary)         #    → insert at end
    else:
        return findIdx          #    → insert at found pos

testAry = [33, 77, 88]
insPos = findInsertIdx(testAry, 55)
print('Insert pos -->', insPos)
# Result: 1 (insert before 77)

Key Points:
· break is used because we only need the first larger value's position
· findIdx == -1: no larger value in array = I'm the largest → go to end

삽입 정렬 구현

Insertion Sort Implementation

한국어

기본 삽입 정렬 (배열 2개)

원본 배열에서 하나씩 꺼내어 새 배열의 올바른 위치에 insert()합니다.

Code11-05 : 기본 삽입 정렬

def findInsertIdx(ary, data):
    findIdx = -1
    for i in range(0, len(ary)):
        if (ary[i] > data):
            findIdx = i
            break
    if findIdx == -1:
        return len(ary)
    else:
        return findIdx

before = [188,162,168,120,50,150,177,105]
after = []
print('정렬 전 -->', before)
for i in range(len(before)):
    data = before[i]              # 하나 꺼내서
    insPos = findInsertIdx(after, data)  # 위치 찾고
    after.insert(insPos, data)    # 삽입!
print('정렬 후 -->', after)

효율적 삽입 정렬 (배열 1개, In-place)

배열 하나에서 뒤쪽 원소를 앞과 비교하며, 작으면 교환, 크면 정지합니다.

💡 쉽게 이해하기

이미 정렬된 앞부분에 새 카드를 끼워넣는 것입니다. 뒤에서 앞으로 한 칸씩 비교하면서 자기 자리를 찾아갑니다.

Code11-06 : 효율적 삽입 정렬

def insertionSort(ary):
    n = len(ary)
    for end in range(1, n):        # [1]부터 끝까지 순서대로
        for cur in range(end, 0, -1): # 뒤→앞으로 비교
            if (ary[cur-1] > ary[cur]):  # 앞이 더 크면
                ary[cur-1], ary[cur] = \  # 교환!
                    ary[cur], ary[cur-1]
            # 앞이 더 작으면? → 자기 자리 찾음 → 자동 정지
    return ary

dataAry = [188,162,168,120,50,150,177,105]
print('정렬 전 -->', dataAry)
dataAry = insertionSort(dataAry)
print('정렬 후 -->', dataAry)

Code11-06 핵심 이해:
· range(end, 0, -1) : end에서 1까지 뒤로 이동
· ary[cur-1] > ary[cur] : "앞이 나보다 크면 교환"
· 앞이 나보다 작으면 if 조건이 거짓 → 교환 안 함 = 자기 자리!

English

Basic Insertion Sort (2 Arrays)

Take one element at a time from original and insert() at the correct position in a new array.

Code11-05 : Basic Insertion Sort

def findInsertIdx(ary, data):
    findIdx = -1
    for i in range(0, len(ary)):
        if (ary[i] > data):
            findIdx = i
            break
    if findIdx == -1:
        return len(ary)
    else:
        return findIdx

before = [188,162,168,120,50,150,177,105]
after = []
print('Before -->', before)
for i in range(len(before)):
    data = before[i]              # Take one out
    insPos = findInsertIdx(after, data)  # Find position
    after.insert(insPos, data)    # Insert!
print('After -->', after)

Efficient Insertion Sort (1 Array, In-place)

Within a single array, compare backwards: swap if smaller, stop if larger.

💡 Easy Understanding

It's like inserting a new card into already-sorted cards. Compare backwards one step at a time to find your spot.

Code11-06 : Efficient Insertion Sort

def insertionSort(ary):
    n = len(ary)
    for end in range(1, n):        # From [1] to end
        for cur in range(end, 0, -1): # Compare backward
            if (ary[cur-1] > ary[cur]):  # Previous is larger
                ary[cur-1], ary[cur] = \  # Swap!
                    ary[cur], ary[cur-1]
            # Previous is smaller? → Found my spot → auto stop
    return ary

dataAry = [188,162,168,120,50,150,177,105]
print('Before -->', dataAry)
dataAry = insertionSort(dataAry)
print('After -->', dataAry)

Code11-06 Key Points:
· range(end, 0, -1) : move from end to 1 backwards
· ary[cur-1] > ary[cur] : "if previous is bigger than me, swap"
· If previous is smaller → if condition is false → no swap = my spot!

선택 정렬 vs 삽입 정렬 비교

Selection Sort vs Insertion Sort

한국어

두 알고리즘 비교

구분	선택 정렬	삽입 정렬
비유	가장 작은 걸 골라 앞에 놓기	카드처럼 자리를 찾아 끼우기
방식	최솟값을 찾아 교환	올바른 위치에 삽입
시간 복잡도	O(n²) 항상	O(n²) 최악 / O(n) 최선
공간	In-place O(1)	In-place O(1)
안정성	불안정	안정
장점	구현 간단, 교환 적음	거의 정렬된 데이터에 빠름
비교 방향	앞 → 뒤 (전체 탐색)	뒤 → 앞 (필요시만)

🤔 언제 어떤 걸 쓸까?

· 데이터가 거의 정렬됨 → 삽입 정렬 (빠름!)
· 데이터가 완전 뒤죽박죽 → 둘 다 비슷하게 느림
· 아주 큰 데이터 → 둘 다 X → 퀵 정렬이나 병합 정렬 사용

        오름차순 ↔ 내림차순 바꾸기

        비교 조건만 바꾸면 됩니다!

        · 오름차순: ary[minIdx] > ary[k] (작은 것 먼저)

        · 내림차순: ary[minIdx] < ary[k] (큰 것 먼저)

English

Comparing Two Algorithms

Aspect	Selection Sort	Insertion Sort
Analogy	Pick smallest, place front	Find spot like cards
Method	Find min & swap	Insert at right position
Time	O(n²) always	O(n²) worst / O(n) best
Space	In-place O(1)	In-place O(1)
Stability	Unstable	Stable
Strength	Simple, fewer swaps	Fast on nearly-sorted
Direction	Front → Back (full scan)	Back → Front (as needed)

🤔 When to use which?

· Data nearly sorted → Insertion Sort (fast!)
· Data completely random → both equally slow
· Very large data → neither → use Quick/Merge Sort

        Switching Ascending ↔ Descending

        Just flip the comparison operator!

        · Ascending: ary[minIdx] > ary[k] (smallest first)

        · Descending: ary[minIdx] < ary[k] (largest first)

연습문제 Part 2

Practice Part 2

한국어

연습 2-1 : 기본 삽입 정렬 (Code11-05)

삽입 위치를 찾는 함수 findInsertIdx()를 사용하여 배열을 오름차순 정렬하는 프로그램을 작성하시오.

def findInsertIdx(ary, data):
    findIdx = -1
    for i in range(0, len(ary)):
        if (ary[i] > data):
            findIdx = i
            break
    if findIdx == -1:
        return len(ary)
    else:
        return findIdx

before = [188,162,168,120,50,150,177,105]
after = []
print('정렬 전 -->', before)
for i in range(len(before)):
    data = before[i]
    insPos = findInsertIdx(after, data)
    after.insert(insPos, data)
print('정렬 후 -->', after)

연습 2-2 : 내림차순 삽입 정렬 (Self11-02)

랜덤 10개 데이터를 내림차순으로 삽입 정렬하시오.

힌트: 비교 조건 >를 <로 바꾸면 내림차순!

import random

def findInsertIdx(ary, data):
    findIdx = -1
    for i in range(0, len(ary)):
        if (ary[i] < data):  # < 로 변경 (내림차순)
            findIdx = i
            break
    if findIdx == -1:
        return len(ary)
    else:
        return findIdx

before = [random.randint(0,200) for _ in range(10)]
after = []
print('정렬 전 -->', before)
for i in range(len(before)):
    data = before[i]
    insPos = findInsertIdx(after, data)
    after.insert(insPos, data)
print('정렬 후 -->', after)

English

Practice 2-1 : Basic Insertion Sort (Code11-05)

Write a program using findInsertIdx() to sort an array in ascending order.

def findInsertIdx(ary, data):
    findIdx = -1
    for i in range(0, len(ary)):
        if (ary[i] > data):
            findIdx = i
            break
    if findIdx == -1:
        return len(ary)
    else:
        return findIdx

before = [188,162,168,120,50,150,177,105]
after = []
print('Before -->', before)
for i in range(len(before)):
    data = before[i]
    insPos = findInsertIdx(after, data)
    after.insert(insPos, data)
print('After -->', after)

Practice 2-2 : Descending Insertion Sort (Self11-02)

Sort 10 random numbers in descending order.

Hint: Change > to < for descending!

import random

def findInsertIdx(ary, data):
    findIdx = -1
    for i in range(0, len(ary)):
        if (ary[i] < data):  # Changed to < (descending)
            findIdx = i
            break
    if findIdx == -1:
        return len(ary)
    else:
        return findIdx

before = [random.randint(0,200) for _ in range(10)]
after = []
print('Before -->', before)
for i in range(len(before)):
    data = before[i]
    insPos = findInsertIdx(after, data)
    after.insert(insPos, data)
print('After -->', after)

03

Part 3

정렬의 응용

Sorting Applications

중앙값 계산, 파일 이름 정렬, 성적별 조 편성, 2차원 배열 중앙값 등 실전 응용을 학습합니다.

중앙값 계산

Median Calculation

한국어

평균값 vs 중앙값

평균값(Mean)은 전체를 합산 후 개수로 나눈 값이고, 중앙값(Median)은 정렬 후 가운데 위치한 값입니다.

💰 비유 — 반 친구들의 용돈

10명의 용돈: [7, 5, 11, 6, 9, 80000, 10, 6, 15, 12]
한 명이 부잣집 아이라 용돈이 80,000원입니다.

· 평균값 = (7+5+11+...+80000)/10 = 약 8,008원
→ 실제로 대부분 친구의 용돈은 10원 내외인데, 평균은 8,008? 비현실적!

· 중앙값 = 정렬 후 가운데 값 = 9원
→ 실제 대부분의 용돈 수준을 잘 반영합니다!

        중앙값을 구하는 방법

        ① 데이터를 오름차순 정렬한다

        ② 가운데 인덱스를 구한다: len(ary) // 2

        ③ 해당 인덱스의 값이 중앙값!

Code11-07 : 중앙값 계산

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i
        for k in range(i+1, n):
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
    return ary

moneyAry = [7,5,11,6,9,80000,10,6,15,12]
print('정렬 전 -->', moneyAry)
moneyAry = selectionSort(moneyAry)
print('정렬 후 -->', moneyAry)
print('중앙값 -->',
    moneyAry[len(moneyAry)//2])  # 10//2 = 5번째

핵심 정리: 중앙값을 구하려면 ① 정렬 ② ary[len(ary)//2] — 딱 두 단계!

English

Mean vs Median

Mean is the sum divided by count; Median is the middle value after sorting.

💰 Analogy — Classmates' Allowance

10 students' allowances: [7, 5, 11, 6, 9, 80000, 10, 6, 15, 12]
One rich kid gets 80,000 allowance.

· Mean = (7+5+11+...+80000)/10 = ~8,008
→ Most get ~10, but mean says 8,008? Unrealistic!

· Median = middle value after sorting = 9
→ Better reflects actual allowance levels!

        How to Find the Median

        ① Sort data in ascending order

        ② Get the middle index: len(ary) // 2

        ③ Value at that index is the median!

Code11-07 : Median Calculation

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i
        for k in range(i+1, n):
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
    return ary

moneyAry = [7,5,11,6,9,80000,10,6,15,12]
print('Before -->', moneyAry)
moneyAry = selectionSort(moneyAry)
print('After -->', moneyAry)
print('Median -->',
    moneyAry[len(moneyAry)//2])  # 10//2 = 5th

Key Summary: Finding median: ① Sort ② ary[len(ary)//2] — just two steps!

파일 정렬과 성적별 조 편성

File Sorting & Score-based Grouping

한국어

파일 이름 역순 정렬 (Code11-08)

os.walk()로 폴더의 파일 목록을 추출한 뒤, 삽입 정렬로 역순(내림차순) 정렬합니다.

import os

def makeFileList(folderName):
    fnameAry = []
    for dirName, subDirList, fnames \
        in os.walk(folderName):   # 폴더 탐색
        for fname in fnames:       # 파일 이름 수집
            fnameAry.append(fname)
    return fnameAry

def insertionSort(ary):
    n = len(ary)
    for end in range(1, n):
        for cur in range(end, 0, -1):
            if (ary[cur-1] < ary[cur]):  # < 내림차순!
                ary[cur-1], ary[cur] = \
                    ary[cur], ary[cur-1]
    return ary

fileAry = makeFileList('C:/Program Files')
fileAry = insertionSort(fileAry)
print('역순 정렬 -->', fileAry)

오름차순 vs 내림차순 — 비교 연산자만 다름!
· 오름차순: ary[cur-1] > ary[cur]
· 내림차순: ary[cur-1] < ary[cur]

성적별 조 편성 (Ex11-01)

성적으로 정렬 후, 상위-하위 학생을 짝지어 균형 잡힌 조를 만듭니다.

💡 조 편성 원리

정렬 후 [영웅67, 화사71, 영탁78, 선미88, 민호92, 초아99]
→ 최하위-최상위 짝짓기:
· 영웅(67) + 초아(99) = 조 1
· 화사(71) + 민호(92) = 조 2
· 영탁(78) + 선미(88) = 조 3
→ 각 조 합계: 166, 163, 166 → 균형!

def scoreSort(ary):
    n = len(ary)
    for end in range(1, n):
        for cur in range(end, 0, -1):
            if (ary[cur-1][1] > ary[cur][1]):  # [1]=점수 기준
                ary[cur-1], ary[cur] = \
                    ary[cur], ary[cur-1]
    return ary

scoreAry = [['선미',88], ['초아',99],
  ['화사',71], ['영탁',78],
  ['영웅',67], ['민호',92]]
scoreAry = scoreSort(scoreAry)
print('## 성적별 조 편성표 ##')
for i in range(len(scoreAry)//2):  # 절반만 반복
    print(scoreAry[i][0], ':',
        scoreAry[len(scoreAry)-1-i][0])  # 앞+뒤 짝짓기

코드 포인트: ary[cur-1][1] — 2차원 배열에서 [1]번(점수)을 기준으로 비교합니다. [0]은 이름입니다.

English

File Name Reverse Sort (Code11-08)

Extract file list with os.walk(), sort reverse (descending).

import os

def makeFileList(folderName):
    fnameAry = []
    for dirName, subDirList, fnames \
        in os.walk(folderName):   # Walk folder
        for fname in fnames:       # Collect filenames
            fnameAry.append(fname)
    return fnameAry

def insertionSort(ary):
    n = len(ary)
    for end in range(1, n):
        for cur in range(end, 0, -1):
            if (ary[cur-1] < ary[cur]):  # < descending!
                ary[cur-1], ary[cur] = \
                    ary[cur], ary[cur-1]
    return ary

fileAry = makeFileList('C:/Program Files')
fileAry = insertionSort(fileAry)
print('Reverse sorted -->', fileAry)

Ascending vs Descending — only the operator differs!
· Ascending: ary[cur-1] > ary[cur]
· Descending: ary[cur-1] < ary[cur]

Score-based Grouping (Ex11-01)

Sort by score, pair top-bottom for balanced groups.

💡 Grouping Principle

After sort: [Youngwoong 67, Hwasa 71, Youngtak 78, Sunmi 88, Minho 92, Choa 99]
→ Pair lowest-highest:
· Youngwoong(67) + Choa(99) = Group 1
· Hwasa(71) + Minho(92) = Group 2
· Youngtak(78) + Sunmi(88) = Group 3
→ Sums: 166, 163, 166 → Balanced!

def scoreSort(ary):
    n = len(ary)
    for end in range(1, n):
        for cur in range(end, 0, -1):
            if (ary[cur-1][1] > ary[cur][1]):  # [1]=score
                ary[cur-1], ary[cur] = \
                    ary[cur], ary[cur-1]
    return ary

scoreAry = [['Sunmi',88], ['Choa',99],
  ['Hwasa',71], ['Youngtak',78],
  ['Youngwoong',67], ['Minho',92]]
scoreAry = scoreSort(scoreAry)
print('## Group Assignment ##')
for i in range(len(scoreAry)//2):  # Half iterations
    print(scoreAry[i][0], ':',
        scoreAry[len(scoreAry)-1-i][0])  # Front+back pair

Code point: ary[cur-1][1] — compares by [1] (score) in a 2D array. [0] is the name.

2차원 배열의 중앙값

2D Array Median

한국어

2차원 → 1차원 변환 후 중앙값

2차원 배열은 바로 정렬할 수 없으므로, 1차원으로 펼친 뒤 정렬하고 중앙값을 구합니다.

💡 비유 — 교실 책상 배치

학생들이 4×4 (행×열)로 앉아 있는데, 키 순서로 줄을 세우려면? → 먼저 한 줄로 서게 해야 합니다! 이것이 "2차원 → 1차원 변환(flatten)"입니다.

EX11-02 : 2차원 배열 중앙값

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i
        for k in range(i+1, n):
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
    return ary

ary2 = [[55,33,250,44],       # 2차원 배열
        [88,1,67,23],
        [199,222,38,47],
        [155,145,20,99]]
ary1 = []                        # 1차원 빈 배열

for i in range(len(ary2)):       # 행 반복
    for k in range(len(ary2[i])): # 열 반복
        ary1.append(ary2[i][k])   # 1차원에 추가

print('정렬 전 -->', ary1)
ary1 = selectionSort(ary1)
print('정렬 후 -->', ary1)
print('중앙값 -->',
    ary1[len(ary1)//2])

English

Flatten 2D → 1D, Then Find Median

2D arrays can't be sorted directly, so flatten to 1D first, sort, then find median.

💡 Analogy — Classroom Seating

Students sitting in 4×4 grid — to line up by height, they must first form a single line! This is "2D → 1D flatten".

EX11-02 : 2D Array Median

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i
        for k in range(i+1, n):
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
    return ary

ary2 = [[55,33,250,44],       # 2D array
        [88,1,67,23],
        [199,222,38,47],
        [155,145,20,99]]
ary1 = []                        # Empty 1D array

for i in range(len(ary2)):       # Loop rows
    for k in range(len(ary2[i])): # Loop columns
        ary1.append(ary2[i][k])   # Add to 1D

print('Before -->', ary1)
ary1 = selectionSort(ary1)
print('After -->', ary1)
print('Median -->',
    ary1[len(ary1)//2])

연습문제 Part 3

Practice Part 3

한국어

연습 3-1 : 성적별 조 편성 (Ex11-01)

학생 이름과 성적이 담긴 2차원 배열을 성적 기준으로 정렬한 뒤, 최하위-최상위 학생을 짝지어 조를 편성하는 프로그램을 작성하시오.

def scoreSort(ary):
    n = len(ary)
    for end in range(1, n):
        for cur in range(end, 0, -1):
            if (ary[cur-1][1] > ary[cur][1]):
                ary[cur-1], ary[cur] = \
                    ary[cur], ary[cur-1]
    return ary

scoreAry = [['선미',88], ['초아',99],
  ['화사',71], ['영탁',78],
  ['영웅',67], ['민호',92]]

print('정렬 전 -->', scoreAry)
scoreAry = scoreSort(scoreAry)
print('정렬 후 -->', scoreAry)

print('## 성적별 조 편성표 ##')
for i in range(len(scoreAry)//2):
    print(scoreAry[i][0], ':',
        scoreAry[len(scoreAry)-1-i][0])

연습 3-2 : 2차원 배열 중앙값 (EX11-02)

4×4 2차원 배열을 1차원으로 변환한 뒤, 선택 정렬하고 중앙값을 출력하는 프로그램을 작성하시오.

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i
        for k in range(i+1, n):
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
    return ary

ary2 = [[55,33,250,44],
        [88,1,67,23],
        [199,222,38,47],
        [155,145,20,99]]
ary1 = []

for i in range(len(ary2)):
    for k in range(len(ary2[i])):
        ary1.append(ary2[i][k])

print('1차원 변경 후, 정렬 전 -->', ary1)
ary1 = selectionSort(ary1)
print('1차원 변경 후, 정렬 후 -->', ary1)
print('중앙값 -->',
    ary1[len(ary1)//2])

English

Practice 3-1 : Score-based Grouping (Ex11-01)

Sort a 2D array of [name, score] by score, then pair lowest with highest to create balanced groups.

def scoreSort(ary):
    n = len(ary)
    for end in range(1, n):
        for cur in range(end, 0, -1):
            if (ary[cur-1][1] > ary[cur][1]):
                ary[cur-1], ary[cur] = \
                    ary[cur], ary[cur-1]
    return ary

scoreAry = [['Sunmi',88], ['Choa',99],
  ['Hwasa',71], ['Youngtak',78],
  ['Youngwoong',67], ['Minho',92]]

print('Before -->', scoreAry)
scoreAry = scoreSort(scoreAry)
print('After -->', scoreAry)

print('## Group Assignment ##')
for i in range(len(scoreAry)//2):
    print(scoreAry[i][0], ':',
        scoreAry[len(scoreAry)-1-i][0])

Practice 3-2 : 2D Array Median (EX11-02)

Flatten a 4×4 2D array to 1D, sort with selection sort, and print the median.

def selectionSort(ary):
    n = len(ary)
    for i in range(0, n-1):
        minIdx = i
        for k in range(i+1, n):
            if (ary[minIdx] > ary[k]):
                minIdx = k
        tmp = ary[i]
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
    return ary

ary2 = [[55,33,250,44],
        [88,1,67,23],
        [199,222,38,47],
        [155,145,20,99]]
ary1 = []

for i in range(len(ary2)):
    for k in range(len(ary2[i])):
        ary1.append(ary2[i][k])

print('After flatten, before sort -->', ary1)
ary1 = selectionSort(ary1)
print('After flatten, after sort -->', ary1)
print('Median -->',
    ary1[len(ary1)//2])