정렬 알고리즘 통합 학습 및 평가 프로그램

학습 안내

정렬(Sorting)은 여러 데이터를 일정한 기준에 따라 오름차순 또는 내림차순으로 재배치하는 알고리즘입니다.

이 프로그램은 먼저 그림과 예시 코드로 6가지 정렬 알고리즘을 학습한 뒤, 각 알고리즘마다 OX 5문항, 5지선다형 2문항, 코드 관련 서술형 1문항을 풀도록 구성되어 있습니다.

학생 정보 입력

서술형은 상세풀이와 비교한 자기평가 방식으로 점수에 반영됩니다.

버블 정렬 Bubble Sort

인접 비교교환기초 학습용

인접한 두 원소를 비교하여 큰 값을 뒤로 보내는 방식입니다.

핵심 원리: 한 번의 반복이 끝날 때마다 가장 큰 값이 맨 뒤로 이동합니다.

시간 복잡도: 평균/최악 O(n²), 개선형 최선 O(n)

동작 원리

앞에서부터 인접한 두 값을 비교한다.
왼쪽 값이 더 크면 두 값을 교환한다.
한 회전이 끝나면 가장 큰 값이 오른쪽 끝에 놓인다.
정렬된 끝부분을 제외하고 반복한다.

출력이 있는 예시 코드

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

data = [5, 3, 8, 4, 2]
print(bubble_sort(data))

출력 결과: [2, 3, 4, 5, 8]

선택 정렬 Selection Sort

최솟값 선택자리 교환

남은 원소 중 가장 작은 값을 찾아 앞쪽 위치와 교환하는 방식입니다.

핵심 원리: 매 단계마다 최솟값을 선택하여 정렬된 영역을 한 칸씩 늘립니다.

시간 복잡도: 최선/평균/최악 O(n²)

동작 원리

현재 위치 i를 정한다.
i 이후의 미정렬 영역에서 최솟값 위치를 찾는다.
현재 위치의 값과 최솟값을 교환한다.
정렬된 영역을 한 칸 확장한다.

출력이 있는 예시 코드

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

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

출력 결과: [11, 12, 22, 25, 64]

삽입 정렬 Insertion Sort

카드 정리 방식거의 정렬된 데이터에 유리

정렬된 영역에 새 원소를 알맞은 위치에 삽입하는 방식입니다.

핵심 원리: 카드를 손에 들고 순서대로 끼워 넣는 방식과 비슷합니다.

시간 복잡도: 최선 O(n), 평균/최악 O(n²)

동작 원리

두 번째 원소부터 key로 잡는다.
key 왼쪽의 정렬된 영역과 비교한다.
key보다 큰 값은 오른쪽으로 한 칸 이동한다.
빈 자리에 key를 삽입한다.

출력이 있는 예시 코드

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

data = [9, 5, 1, 4, 3]
print(insertion_sort(data))

출력 결과: [1, 3, 4, 5, 9]

병합 정렬 Merge Sort

분할 정복안정 정렬O(n log n)

배열을 반으로 나누고, 정렬된 부분 배열을 다시 병합하는 방식입니다.

핵심 원리: 분할 정복을 사용하며 안정적인 O(n log n) 정렬입니다.

시간 복잡도: 최선/평균/최악 O(n log n)

동작 원리

배열을 반으로 나눈다.
각 부분 배열을 다시 반으로 나누어 길이가 1이 될 때까지 반복한다.
작은 값부터 비교하며 두 배열을 병합한다.
모든 병합이 끝나면 전체 배열이 정렬된다.

출력이 있는 예시 코드

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))

출력 결과: [3, 9, 10, 27, 38, 43, 82]

퀵 정렬 Quick Sort

피벗분할 정복평균적으로 빠름

피벗을 기준으로 작은 값과 큰 값을 나누어 정렬하는 방식입니다.

핵심 원리: 평균적으로 매우 빠르지만 피벗 선택에 따라 최악의 경우 O(n²)가 될 수 있습니다.

시간 복잡도: 평균 O(n log n), 최악 O(n²)

동작 원리

기준값인 pivot을 선택한다.
pivot보다 작은 값, 같은 값, 큰 값으로 나눈다.
작은 값 목록과 큰 값 목록을 재귀적으로 정렬한다.
왼쪽 + 가운데 + 오른쪽 순서로 합친다.

출력이 있는 예시 코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

data = [10, 7, 8, 9, 1, 5]
print(quick_sort(data))

출력 결과: [1, 5, 7, 8, 9, 10]

힙 정렬 Heap Sort

힙 자료구조완전이진트리우선순위 큐

힙 자료구조를 이용하여 최솟값 또는 최댓값을 반복적으로 꺼내 정렬합니다.

핵심 원리: 우선순위 큐와 관련이 깊으며, 평균과 최악 모두 O(n log n)입니다.

시간 복잡도: 평균/최악 O(n log n)

동작 원리

리스트를 힙 구조로 바꾼다.
가장 작은 값을 하나 꺼낸다.
꺼낸 값을 결과 리스트에 넣는다.
힙이 빌 때까지 반복한다.

출력이 있는 예시 코드

import heapq

def heap_sort(arr):
    heapq.heapify(arr)
    result = []

    while arr:
        result.append(heapq.heappop(arr))

    return result

data = [4, 10, 3, 5, 1]
print(heap_sort(data))

출력 결과: [1, 3, 4, 5, 10]

정렬 알고리즘 비교표

정렬	핵심 방식	평균 시간 복잡도	특징
버블 정렬	인접 비교·교환	O(n²)	구현 쉬움, 학습용
선택 정렬	최솟값 선택	O(n²)	교환 횟수 적음
삽입 정렬	알맞은 위치 삽입	O(n²)	거의 정렬된 데이터에 유리
병합 정렬	분할 후 병합	O(n log n)	안정적, 추가 메모리 사용
퀵 정렬	피벗 기준 분할	O(n log n)	평균적으로 빠름
힙 정렬	힙에서 반복 추출	O(n log n)	우선순위 큐와 관련

채점 및 TXT 저장

전체 문항: 48문항 = 6개 알고리즘 × (OX 5 + 5지선다 2 + 서술형 1)

정렬 알고리즘 통합 학습 및 평가 결과 학번: 1120 이름: 김인수 응시시각: 2026-05-25_22-21-06 점수: 0 / 48 (0점 환산) 총 문항 수: 48 1. [버블 정렬 / OX] 오답 문항: 버블 정렬은 인접한 두 원소를 비교하며 정렬한다. 내 답: 미응답 정답: O 상세풀이: 버블 정렬은 바로 옆 원소끼리 비교하고 필요하면 교환합니다. 2. [버블 정렬 / OX] 오답 문항: 버블 정렬은 항상 시간 복잡도가 O(n log n)이다. 내 답: 미응답 정답: X 상세풀이: 기본 버블 정렬의 평균·최악 시간 복잡도는 O(n²)입니다. 3. [버블 정렬 / OX] 오답 문항: 한 회전이 끝날 때마다 가장 큰 값이 뒤쪽으로 이동한다. 내 답: 미응답 정답: O 상세풀이: 오름차순 버블 정렬에서는 큰 값이 뒤로 밀려납니다. 4. [버블 정렬 / OX] 오답 문항: 버블 정렬은 교환이 전혀 일어나지 않아도 반드시 끝까지 반복해야만 한다. 내 답: 미응답 정답: X 상세풀이: 개선형 버블 정렬은 교환 여부를 확인해 조기 종료할 수 있습니다. 5. [버블 정렬 / OX] 오답 문항: 버블 정렬은 구현이 비교적 쉽다. 내 답: 미응답 정답: O 상세풀이: 반복문과 조건문만으로 쉽게 구현할 수 있습니다. 6. [버블 정렬 / MC] 오답 문항: 버블 정렬의 핵심 동작은? 내 답: 미응답 정답: 2번 상세풀이: 버블 정렬은 인접한 두 값을 비교하고 교환합니다. 7. [버블 정렬 / MC] 오답 문항: 오름차순 버블 정렬에서 첫 번째 전체 회전 후 일반적으로 맨 뒤에 위치하는 값은? 내 답: 미응답 정답: 3번 상세풀이: 큰 값이 계속 오른쪽으로 이동하므로 최댓값이 맨 뒤로 갑니다. 8. [버블 정렬 / ESSAY] 오답 문항: 다음 코드에서 `n - i - 1`을 사용하는 이유를 설명하시오. 내 답: 미작성 정답: 상세풀이 기준 자기평가 상세풀이: 뒤쪽의 i개 원소는 이미 정렬되어 있으므로 다시 비교할 필요가 없습니다. 또한 j+1 접근 시 인덱스 범위를 넘지 않게 합니다. 9. [선택 정렬 / OX] 오답 문항: 선택 정렬은 매 단계에서 최솟값을 찾는다. 내 답: 미응답 정답: O 상세풀이: 오름차순 선택 정렬은 남은 값 중 최솟값을 찾습니다. 10. [선택 정렬 / OX] 오답 문항: 선택 정렬은 데이터가 이미 정렬되어 있으면 비교를 거의 하지 않는다. 내 답: 미응답 정답: X 상세풀이: 선택 정렬은 이미 정렬되어 있어도 최솟값 탐색을 위해 비교를 수행합니다. 11. [선택 정렬 / OX] 오답 문항: 선택 정렬의 평균 시간 복잡도는 O(n²)이다. 내 답: 미응답 정답: O 상세풀이: 중첩 반복으로 인해 평균적으로 O(n²)입니다. 12. [선택 정렬 / OX] 오답 문항: 선택 정렬은 일반적으로 교환 횟수가 버블 정렬보다 적다. 내 답: 미응답 정답: O 상세풀이: 각 단계에서 보통 한 번만 교환하므로 교환 횟수가 적은 편입니다. 13. [선택 정렬 / OX] 오답 문항: 선택 정렬은 반드시 재귀 함수로만 구현해야 한다. 내 답: 미응답 정답: X 상세풀이: 대부분 반복문으로 간단히 구현합니다. 14. [선택 정렬 / MC] 오답 문항: 선택 정렬에서 `min_idx`의 역할은? 내 답: 미응답 정답: 2번 상세풀이: `min_idx`는 현재 탐색 구간의 최솟값 위치입니다. 15. [선택 정렬 / MC] 오답 문항: 선택 정렬의 대표적 특징은? 내 답: 미응답 정답: 2번 상세풀이: 선택 정렬은 비교는 많지만 교환 횟수는 적습니다. 16. [선택 정렬 / ESSAY] 오답 문항: 다음 코드에서 `for j in range(i + 1, len(arr))`로 탐색하는 이유를 설명하시오. 내 답: 미작성 정답: 상세풀이 기준 자기평가 상세풀이: i 이전 영역은 이미 정렬된 영역이므로 제외하고, i 이후의 미정렬 영역에서 최솟값을 찾기 위해서입니다. 17. [삽입 정렬 / OX] 오답 문항: 삽입 정렬은 정렬된 부분에 원소를 삽입한다. 내 답: 미응답 정답: O 상세풀이: 앞쪽 정렬 영역에 key 값을 알맞은 위치에 넣습니다. 18. [삽입 정렬 / OX] 오답 문항: 삽입 정렬은 거의 정렬된 데이터에서 효율적이다. 내 답: 미응답 정답: O 상세풀이: 이동할 원소가 적으면 빠르게 동작합니다. 19. [삽입 정렬 / OX] 오답 문항: 삽입 정렬은 항상 O(n log n)으로 동작한다. 내 답: 미응답 정답: X 상세풀이: 평균·최악은 O(n²)입니다. 20. [삽입 정렬 / OX] 오답 문항: 삽입 정렬에서 key는 현재 삽입할 원소이다. 내 답: 미응답 정답: O 상세풀이: `key`는 현재 정렬된 영역에 넣을 대상 값입니다. 21. [삽입 정렬 / OX] 오답 문항: 삽입 정렬은 원소를 비교하며 필요하면 오른쪽으로 밀어낸다. 내 답: 미응답 정답: O 상세풀이: 큰 값을 오른쪽으로 이동시킨 뒤 key를 삽입합니다. 22. [삽입 정렬 / MC] 오답 문항: 삽입 정렬과 가장 비슷한 생활 예시는? 내 답: 미응답 정답: 2번 상세풀이: 삽입 정렬은 손에 든 카드를 정렬하는 방식과 비슷합니다. 23. [삽입 정렬 / MC] 오답 문항: 삽입 정렬의 최선 시간 복잡도는? 내 답: 미응답 정답: 2번 상세풀이: 이미 정렬된 경우 한 번씩만 비교하므로 O(n)입니다. 24. [삽입 정렬 / ESSAY] 오답 문항: `while j >= 0 and arr[j] > key:` 조건의 의미를 설명하시오. 내 답: 미작성 정답: 상세풀이 기준 자기평가 상세풀이: 배열의 범위를 벗어나지 않으면서 key보다 큰 값들을 오른쪽으로 이동시키기 위한 조건입니다. 25. [병합 정렬 / OX] 오답 문항: 병합 정렬은 분할 정복 알고리즘이다. 내 답: 미응답 정답: O 상세풀이: 나누고 정렬한 뒤 합치는 분할 정복 방식입니다. 26. [병합 정렬 / OX] 오답 문항: 병합 정렬의 평균 시간 복잡도는 O(n log n)이다. 내 답: 미응답 정답: O 상세풀이: 분할 단계와 병합 단계가 결합되어 O(n log n)입니다. 27. [병합 정렬 / OX] 오답 문항: 병합 정렬은 피벗을 기준으로 배열을 나눈다. 내 답: 미응답 정답: X 상세풀이: 피벗은 퀵 정렬의 핵심 개념입니다. 28. [병합 정렬 / OX] 오답 문항: 병합 정렬은 추가 메모리를 사용할 수 있다. 내 답: 미응답 정답: O 상세풀이: 병합 과정에서 결과 배열이 필요합니다. 29. [병합 정렬 / OX] 오답 문항: 병합 정렬은 큰 데이터를 안정적으로 정렬하는 데 유리하다. 내 답: 미응답 정답: O 상세풀이: 시간 복잡도가 일정하고 안정 정렬로 구현할 수 있습니다. 30. [병합 정렬 / MC] 오답 문항: 병합 정렬의 핵심 과정은? 내 답: 미응답 정답: 3번 상세풀이: 배열을 나누고 정렬된 두 배열을 병합합니다. 31. [병합 정렬 / MC] 오답 문항: 병합 정렬의 평균 시간 복잡도는? 내 답: 미응답 정답: 3번 상세풀이: 병합 정렬은 평균과 최악 모두 O(n log n)입니다. 32. [병합 정렬 / ESSAY] 오답 문항: `result.extend(left[i:])`와 `result.extend(right[j:])`가 필요한 이유를 설명하시오. 내 답: 미작성 정답: 상세풀이 기준 자기평가 상세풀이: 한쪽 배열의 원소가 먼저 모두 처리되면 다른 쪽 배열에 남은 원소들은 이미 정렬된 상태이므로 결과에 그대로 붙입니다. 33. [퀵 정렬 / OX] 오답 문항: 퀵 정렬은 피벗을 사용한다. 내 답: 미응답 정답: O 상세풀이: 피벗을 기준으로 작은 값과 큰 값을 나눕니다. 34. [퀵 정렬 / OX] 오답 문항: 퀵 정렬의 평균 시간 복잡도는 O(n log n)이다. 내 답: 미응답 정답: O 상세풀이: 균형 있게 분할되면 O(n log n)에 가깝습니다. 35. [퀵 정렬 / OX] 오답 문항: 퀵 정렬은 어떤 경우에도 O(n log n)을 보장한다. 내 답: 미응답 정답: X 상세풀이: 피벗 선택이 나쁘면 최악 O(n²)가 될 수 있습니다. 36. [퀵 정렬 / OX] 오답 문항: 퀵 정렬은 분할 정복 알고리즘이다. 내 답: 미응답 정답: O 상세풀이: 배열을 분할하고 부분 배열을 재귀적으로 정렬합니다. 37. [퀵 정렬 / OX] 오답 문항: 퀵 정렬에서 pivot은 정렬 기준값 역할을 한다. 내 답: 미응답 정답: O 상세풀이: pivot보다 작은 값과 큰 값을 나누는 기준입니다. 38. [퀵 정렬 / MC] 오답 문항: 퀵 정렬에서 pivot의 역할은? 내 답: 미응답 정답: 2번 상세풀이: pivot은 배열을 나누는 기준값입니다. 39. [퀵 정렬 / MC] 오답 문항: 퀵 정렬의 최악 시간 복잡도는? 내 답: 미응답 정답: 4번 상세풀이: 분할이 한쪽으로 치우치면 O(n²)가 됩니다. 40. [퀵 정렬 / ESSAY] 오답 문항: `left`, `middle`, `right` 리스트가 각각 무엇을 의미하는지 설명하시오. 내 답: 미작성 정답: 상세풀이 기준 자기평가 상세풀이: `left`는 pivot보다 작은 값, `middle`은 pivot과 같은 값, `right`는 pivot보다 큰 값을 모은 리스트입니다. 41. [힙 정렬 / OX] 오답 문항: 힙 정렬은 힙 자료구조를 사용한다. 내 답: 미응답 정답: O 상세풀이: 힙 정렬은 힙을 이용해 우선순위가 높은 값을 꺼냅니다. 42. [힙 정렬 / OX] 오답 문항: 파이썬 heapq는 기본적으로 최소 힙이다. 내 답: 미응답 정답: O 상세풀이: heapq.heappop은 가장 작은 값을 꺼냅니다. 43. [힙 정렬 / OX] 오답 문항: 힙 정렬의 평균 시간 복잡도는 O(n log n)이다. 내 답: 미응답 정답: O 상세풀이: 힙 삽입·삭제 과정이 log n 수준으로 반복됩니다. 44. [힙 정렬 / OX] 오답 문항: 힙 정렬은 피벗을 기준으로 분할한다. 내 답: 미응답 정답: X 상세풀이: 피벗 분할은 퀵 정렬의 특징입니다. 45. [힙 정렬 / OX] 오답 문항: 힙 정렬은 우선순위 큐 개념과 관련이 있다. 내 답: 미응답 정답: O 상세풀이: 힙은 우선순위 큐 구현에 자주 사용됩니다. 46. [힙 정렬 / MC] 오답 문항: 파이썬 `heapq.heappop(arr)`은 기본적으로 무엇을 꺼내는가? 내 답: 미응답 정답: 2번 상세풀이: heapq는 최소 힙이므로 가장 작은 값을 꺼냅니다. 47. [힙 정렬 / MC] 오답 문항: 힙 정렬과 가장 관련 깊은 자료구조는? 내 답: 미응답 정답: 3번 상세풀이: 힙 정렬은 힙 자료구조를 사용합니다. 48. [힙 정렬 / ESSAY] 오답 문항: `heapq.heapify(arr)`의 역할을 설명하시오. 내 답: 미작성 정답: 상세풀이 기준 자기평가 상세풀이: 일반 리스트를 힙 조건을 만족하는 구조로 재배치하여 heappop으로 최솟값을 효율적으로 꺼낼 수 있게 합니다.

학습 안내

학생 정보 입력

버블 정렬 Bubble Sort

동작 원리

출력이 있는 예시 코드

버블 정렬 OX 퀴즈 5개

버블 정렬 5지선다형 문제 2개

버블 정렬 코드 관련 서술형 문제 1개

선택 정렬 Selection Sort

동작 원리

출력이 있는 예시 코드

선택 정렬 OX 퀴즈 5개

선택 정렬 5지선다형 문제 2개

선택 정렬 코드 관련 서술형 문제 1개

삽입 정렬 Insertion Sort

동작 원리

출력이 있는 예시 코드

삽입 정렬 OX 퀴즈 5개

삽입 정렬 5지선다형 문제 2개

삽입 정렬 코드 관련 서술형 문제 1개

병합 정렬 Merge Sort

동작 원리

출력이 있는 예시 코드

병합 정렬 OX 퀴즈 5개

병합 정렬 5지선다형 문제 2개

병합 정렬 코드 관련 서술형 문제 1개

퀵 정렬 Quick Sort

동작 원리

출력이 있는 예시 코드

퀵 정렬 OX 퀴즈 5개

퀵 정렬 5지선다형 문제 2개

퀵 정렬 코드 관련 서술형 문제 1개

힙 정렬 Heap Sort

동작 원리

출력이 있는 예시 코드

힙 정렬 OX 퀴즈 5개

힙 정렬 5지선다형 문제 2개

힙 정렬 코드 관련 서술형 문제 1개

정렬 알고리즘 비교표

채점 및 TXT 저장