백준(baekjoon) 2750번: 수 정렬하기(브론즈 2, 파이썬 PYTHON) - 정렬

문제

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

 

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

2750번: 수 정렬하기

 

import sys

N=int(sys.stdin.readline())
num_list=[]

for _ in range(N):
  num=int(sys.stdin.readline())
  num_list.append(num)

for x in range(N):
  for y in range(x,0,-1):
    if(num_list[y-1]>num_list[y]):
      num_list[y-1],num_list[y]=num_list[y],num_list[y-1]  

for x in num_list:
  print(x)

 

 

※ 정렬

 

 

● 삽입정렬을 이용하여 풀어보았다.

num_list 배열 두번째 원소부터 끝 원소까지 순회하며 각 원소가 들어갈 위치를 찾아주는 알고리즘이다.

각 단계에서 들어갈 위치를 찾아야 하는 원소의 앞 원소들과 값을 비교하여 알맞은 위치를 찾아준다.

 

* 배열 [5,4,3,2,1] 을 오름차순 정렬 한다고 가정

-> 먼저 5 앞에는 원소가 없으므로 다음 단계로 패스. 

 

-> 이제 4의 원소의 자리를 찾아주자. 4 앞에는 5라는 원소가 있다. 4보다 앞 원소인 5가 더 크므로 4와 5의 자리를 바꿔준다. [4,5,3,2,1]

 

-> 이제 3의 자리를 찾아주자. 3 앞에는 4와 5라는 원소가 있다. 먼저 3과 가까운 5와 비교하면 앞 원소인 5가 더 크므로 3과 5의 자리를 바꿔준다. [4,3,5,2,1]  다른 앞 원소 4도 3보다 크므로 3과 4의 자리도 바꿔준다. [3,4,5,2,1]

 

-> 이제 2의 자리를 찾아주자. 2 앞에는 3,4,5라는 원소가 있다. 모두 2보다 작으므로 2는 비교를 통해 맨 앞자리로 가게 된다. [2,3,4,5,1]

 

->이제 1의 자리를 찾아주자. 1 앞에는 2,3,4,5라는 원소가 있다. 모두 1보다 작으므로 1은 비교를 통해 맨 앞자리로 가게 된다. [1,2,3,4,5]

 

 

결과

 

 

♣ 참고: 삽입 정렬

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

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