6. 기본정렬에 대하여- 버블정렬, 선택 정렬, 삽입 정렬(백준 2750 파이썬)

기본 오브 기본 정렬 문제도 풀어보았다.

내가 기억하는 애들은 기본적인 버블정렬, 선택정렬, 삽입정렬 그리고 대망의 퀵정렬이다. 

아마도 앞의 정렬들은 직접 구현하기보다 파이썬의 sorted()나 .sort()를 써서 해결할 것 같고, 실제 구현을 하게 될 애는 시간복잡도 nlogn에 빛나는 퀵정렬이 아닐까 한다.

백준에 정렬 기본 문제는 2750(브론즈1)과 2751(실버5)가 있는데, 차이는 주어지는 수의 크기 차이로, 실버 문제는 일반 정렬로는 시간초과가 나오지 않을까 예상이 간다. 그래서 오늘은 2750번은 버블정렬, 선택정렬, 삽입정렬 3가지로 풀어보고, 다음 게시글에서 2751번은 퀵정렬을 구현하는 시간을 가져보겠다.

 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

---

import sys

N = int(sys.stdin.readline())
S = []
for _ in range(N):
    S.append(int(sys.stdin.readline()))


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


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


def insertion_sort(arr):
    for i in range(N):
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break
    return arr


result = bubble_sort(S)
# result = selection_sort(S)
# result = insertion_sort(S)

for i in range(N):
    print(result[i])

• 버블 정렬 : 맨 첫 칸이 제일 작게 만드는 것을 한칸씩 한다는 것이 핵심. 정말 버블처럼 움직이는 걸 생각하면 구현하기가 가장 쉽다. 하지만 딱봐도 오래걸림
• 선택 정렬 : 개인적으로 제일 기억에 오래 남고 직관적으로 구현 가능함. min_idx 값만 저장해서 한 라운드에 한번씩만 바꾼다는 점이 버블 정렬과의 차이. 미묘하게 더 효율적이라 기분이 좋음(?)
• 삽입 정렬 : 모든 경우에 대해서 비교하지 않고, 더 작은 애를 만났을 때만 이동하고 넘기는 방식. 삽입이라기보다 왼쪽으로 이동하는 버블 느낌(?)인데 이름이 삽입이라 약간 .insert(n) 같은걸 써야 할 것 같은 이름이 문제인듯ㅋㅋㅋ

다음 게시글은 드디어.. 하고싶지 않은.. 퀵소트를 구현해볼까 한다. 보고 이해하는건 쉬워도 직접 쓰자면 항상 답답한 기분이 드는 정렬.. 그리고 그냥 문풀보다 재미도 없어..