🔎 정렬 알고리즘

정렬 알고리즘이란?
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)