🔎 정렬 알고리즘

정렬 알고리즘이란?
n개의 원소가 주어졌을 때, 원소들을 번호순이나 사전순서와 같이 일정한 순서대로 정렬하는 알고리즘이다.

시간복잡도 O($n^2$) 정렬

✔ 버블 정렬

이미지 출처
서로 인접한 두 원소를 비교하여 정렬하는 알고리즘으로 비교하였을 때 큰 값이 뒤로 가게된다.
한 바퀴를 정렬하게되면 가장 큰 값이 마지막에 저장되므로 다음 바퀴를 수행할 때는 가장 마지막 값은 제외하고 진행한다.

• 비교 횟수 : n(n-1)/2

✔ 선택 정렬

이미지 출처

주어진 배열 중 최솟값을 찾은 후 그 값을 맨 앞에 위치한 값과 교체하고, 맨 앞 값을 뺀 나머지 배열들을 같은 방법 교체하며 모든 값이 정렬을 마칠때 까지 반복하는 알고리즘이다.

• 선택 정렬은 버블 정렬보다 빠르다.

✔ 삽입 정렬

이미지출처

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 하는 알고리즘 이다.

---

문제

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

풀이

사용 언어 : python
내장된 정렬 함수 sort()를 이용하여 간단하게 풀 수 있지만, 버블정렬과 선택정렬을 이용해서 풀었습니다.

🔎 코드

# 버블 정렬
n = int(input())
num = [int(input()) for i in range(n)]

for x in range(n):
    for y in range(n-1):
        if num[y] > num[y+1]:
            num[y], num[y+1] = num[y+1], num[y]
for z in num:
    print(z)

# 선택 정렬
n = int(input())
num = [int(input()) for i in range(n)]

for x in range(n-1):
    min_index = x 
    for y in range(x+1, n):
        if num[min_index] > num[y]:
            min_index = y

    num[x], num[min_index] = num[min_index], num[x]

for z in num:
    print(z)