2025.09.11. 실습 / Sort Algorithm

 

 

Selection Sort

 

 

---

 

import sys
read = sys.stdin.readline

n = int(read())
a = list(map(int, read().split()))

count = 0
for k in range(n - 1, 0, -1):
    max_idx = 0
    max_val = a[0]
    for i in range(1, k + 1):
        if a[i] >= max_val:
            count += 1
            max_val = a[i]
            max_idx = i
    a[k], a[max_idx] = a[max_idx], a[k]

print(count)

 

 

 

 

 

---

Bubble Sort

 

 

n = int(input())
arr = list(map(int, input().split()))

count = 0

for num in range(n-1, 0, -1):
    sorted_flag = True
    
    for i in range(num):
        if arr[i] > arr[i+1]:
            arr[i], arr[i+1] = arr[i+1], arr[i]
            count += 1
            sorted_flag = False
            
    if sorted_flag:
        break

print(count)

 

---

Insertion Sort

 

 

 

 

n = int(input())

A = list(map(int, input().split()))

count = 0

for k in range(1, n):
    key = A[k]

    j = k - 1

    while j >= 0 and A[j] > key:
        A[j + 1] = A[j]
        count += 1
        j -= 1

    A[j + 1] = key
    count += 1

print(count)

 

 

---

Merge Sort

 

 

 

n = int(input())
A = list(map(int, input().split()))

count = 0

def merge_sort(arr, left, right):
    global count
    if left >= right:
        return
    mid = (left + right) // 2
    merge_sort(arr, left, mid)
    merge_sort(arr, mid + 1, right)

    temp = []
    i, j = left, mid + 1
    while i <= mid and j <= right:
        count += 1
        if arr[i] < arr[j]: 
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    while i <= mid:
        temp.append(arr[i])
        i += 1
    while j <= right:
        temp.append(arr[j])
        j += 1
    arr[left:right+1] = temp

merge_sort(A, 0, n - 1)
print(count)

 

 

 

---