[백준] 2750번 수 정렬하기

문제 설명

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

제한 사항

-첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

-첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

​

입출력 예

input	output
5 5 2 3 4 1	1 2 3 4 5

접근법

정말 간단하게 풀려면 파이썬 내의 sorted함수를 이용하시면 됩니다. 하지만, 버블정렬, 퀵정렬, 합병정렬 등 다양한 정렬 방법을 이용해서 푸셔도 됩니다!

​

※ 파이썬 내의 sorted함수의 시간 복잡도는 얼마나 되나요?

파이썬 sorted함수는 O(nlongn)의 시간 복잡도를 가진다고 합니다.

​

나의 코드

(1) 파이썬 내의 sorted함수 이용

number = int(input())
input_list = []

for _ in range(number):
    input_list.append(int(input()))

for item in sorted(input_list):
    print(item)

(2) 버블 정렬 이용

number = int(input())
input_list = []

for _ in range(number):
    input_list.append(int(input()))

for i in range(len(input_list)-1):
    for j in range(len(input_list)-i-1):
        if input_list[j] > input_list[j+1]:
            input_list[j], input_list[j+1] = input_list[j+1], input_list[j]

for item in input_list:
    print(item)

(3) 선택 정렬 이용

number = int(input())
input_list = []

for _ in range(number):
    input_list.append(int(input()))

for i in range(len(input_list)):
    index = i
    for j in range(i+1,len(input_list)):
        if input_list[index] > input_list[j]:
            index = j
    input_list[i], input_list[index] = input_list[index], input_list[i]

for item in input_list:
    print(item)

(4) 삽입 정렬 이용

number = int(input())
input_list = []

for _ in range(number):
    input_list.append(int(input()))

for i in range(1,len(input_list)):
    for j in range(i,0,-1):
        if input_list[j] < input_list[j-1]:
            input_list[j], input_list[j-1] = input_list[j-1], input_list[j]

for item in input_list:
    print(item)

(5) 합병 정렬 이용

number = int(input())
input_list = []

for _ in range(number):
    input_list.append(int(input()))

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst)//2
    left_list = merge_sort(lst[:mid])
    right_list = merge_sort(lst[mid:])
    return merge(left_list,right_list)

def merge(left_list, right_list):
    sorted_list = []
    li = 0
    ri = 0
    while (li < len(left_list) and ri < len(right_list)):
        if left_list[li] < right_list[ri]:
            sorted_list.append(left_list[li])
            li += 1
        else:
            sorted_list.append(right_list[ri])
            ri += 1

    while(li < len(left_list)):
        sorted_list.append(left_list[li])
        li += 1
    while (ri < len(right_list)):
        sorted_list.append(right_list[ri])
        ri += 1
    return sorted_list

input_list = merge_sort(input_list)

for item in input_list:
    print(item)

(6) 힙정렬 이용

number = int(input())
input_list = []

for _ in range(number):
    input_list.append(int(input()))

def heapify(lst, index, size):
    parent = index
    child = 2 * index + 1
    if child < size and lst[child] > lst[parent]:
        parent = child
    if (child + 1) < size and lst[(child + 1)] > lst[parent]:
        parent = (child + 1)
    if parent != index:
        lst[parent], lst[index] = lst[index], lst[parent]
        heapify(lst, parent, size)

def heap_sort(lst):
    for i in range(len(lst)//2-1,-1,-1):
        heapify(lst, i, len(lst))
    for i in range(len(lst) - 1, 0, -1):
        lst[0], lst[i] = lst[i], lst[0]
        heapify(lst, 0, i)
    return lst

input_list = heap_sort(input_list)

for item in input_list:
    print(item)

(7) 퀵정렬 이용

number = int(input())
input_list = []

for _ in range(number):
    input_list.append(int(input()))

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[0]
    left, right = [], []
    for item in lst[1:]:
        if item < pivot: left.append(item)
        else: right.append(item)
    return quick_sort(left) + [pivot] + quick_sort(right)

input_list = quick_sort(input_list)

for item in input_list:
    print(item)

(8) 계수 정렬 이용

number = int(input())
input_list = []

for _ in range(number):
    input_list.append(int(input()))

def counting_sort(lst, K):
    count_lst = [0] * K
    sorted_lst = [0] * len(lst)

    for item in lst:
        count_lst[item] += 1

    for count in range(1,K):
        count_lst[count] += count_lst[count-1]

    for index in range(len(lst)):
        sorted_lst[count_lst[lst[index]]-1] = lst[index]
        count_lst[lst[index]] -= 1
    return sorted_lst

input_list = counting_sort(input_list,max(input_list)+1)

for item in input_list:
    print(item)