정렬 알고리즘 비교 분석하기

import time
import random

# 버블 정렬
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

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

# 퀵 정렬
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)

# 성능 비교 함수
def compare_sorting_algorithms():
    array_size = 1000
    test_data = [random.randint(0, 10000) for _ in range(array_size)]
    
    # 버블 정렬 성능 측정
    bubble_data = test_data.copy()
    start_time = time.time()
    bubble_sort(bubble_data)
    bubble_sort_time = time.time() - start_time

    # 삽입 정렬 성능 측정
    insertion_data = test_data.copy()
    start_time = time.time()
    insertion_sort(insertion_data)
    insertion_sort_time = time.time() - start_time

    # 퀵 정렬 성능 측정
    quick_data = test_data.copy()
    start_time = time.time()
    quick_sort(quick_data)
    quick_sort_time = time.time() - start_time

    # 결과 출력
    print(f"버블 정렬 시간: {bubble_sort_time:.6f} 초")
    print(f"삽입 정렬 시간: {insertion_sort_time:.6f} 초")
    print(f"퀵 정렬 시간: {quick_sort_time:.6f} 초")

compare_sorting_algorithms()

---

1. 버블 정렬 (Bubble Sort):

• 시간 복잡도: O(n²)
• 설명: 인접한 두 원소를 비교하여 크기가 큰 원소를 뒤로 보내는 방식입니다. 배열이 거의 정렬된 상태에서는 효율적이지 않으며, 모든 원소를 비교해야 하므로 속도가 가장 느립니다.

2. 삽입 정렬 (Insertion Sort):

• 시간 복잡도: O(n²)
• 설명: 배열을 순차적으로 정렬해 나가며, 각 원소를 적절한 위치에 삽입하는 방식입니다. 배열이 거의 정렬된 상태에서는 빠르게 동작하지만, 무작위 데이터에서는 비효율적입니다.

3. 퀵 정렬 (Quick Sort):

• 시간 복잡도: 평균적으로 O(n log n), 최악의 경우 O(n²)

• 설명: 배열을 피벗을 기준으로 두 부분으로 나누어 정렬합니다. 평균적으로 가장 빠른 정렬 알고리즘 중 하나이며, 실전에서 많이 사용됩니다.

  ---

• 버블정열이랑 삽입정열이나 차이가 나는 이유 : 버블 정렬과 삽입 정렬의 시간 복잡도는 둘 다𝑂(𝑛2)로 동일하지만, 실제 성능에서 차이가 나는 이유는 두 알고리즘의 동작 방식과 비교 및 교환 횟수