2750. 수 정렬하기

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

*시간복잡도가 O($n^2$)인 정렬 알고리즘 이용 : 선택, 거품, 삽입 정렬

 

 

1. 선택 정렬
https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

선택 정렬 - 위키백과, 우리 모두의 백과사전

 

N = int(input())
numbers = [int(input()) for _ in range(N)]

for i in range(N-1):
    minindex = i
    
    for j in range(i+1,N):
        if numbers[j] < numbers[minindex]:
            minindex = j
    
    numbers[i], numbers[minindex] = numbers[minindex], numbers[i]
    
for number in numbers:
    print(number)

 

 

2. 버블 정렬

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

거품 정렬 - 위키백과, 우리 모두의 백과사전

 

N = int(input())
numbers = [int(input()) for _ in range(N)]

for i in range(N-1):
    for j in range(N-i-1):
        if numbers[j] > numbers[j+1]:
            numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
            
for number in numbers:
    print(number)

 

 

3. 삽입 정렬

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

삽입 정렬 - 위키백과, 우리 모두의 백과사전

 

N = int(input())
numbers = [int(input()) for _ in range(N)]

for i in range(1,N):
    key = numbers[i]
    j = i-1
    
    while numbers[j] > key and j >= 0:
        numbers[j+1] = numbers[j]
        j = j-1
    numbers[j+1] = key
    
for number in numbers:
    print(number)