백준 문제 중 2750번, 정렬, ‘수 정렬하기’

백준 문제 중 2750번

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

문제

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

입력

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

출력

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

---

풀이

1. 삽입정렬

• n개의 리스트에서 2번째 원소인 1번 인덱스부터 시작하여 tmp에 현재 비교중인 데이터를 저장하고 현재 인덱스부터 인덱스를 앞쪽으로 한칸씩 이동하고 이때 tmp보다 이동한 인덱스의 데이터값이 크고 인덱스가 0보다 크다면 이를 반복한다. 만약 인덱스가 0이되거나 이동한 인덱스의 데이터값이 tmp보다 작거나 같으면 해당 인덱스에 tmp를 저장한다. 이를 2번째원소부터 n번째까지 하면 정렬이 종료 된다.

from typing import List

n = int(input())

nums = [None]*n

for i in range(n):
    nums[i]=int(input())


 #삽입정렬을 구현하는 함수 선언
def insert_sort(nums:List[int])->None:
    
     # 2번째원소인 idx 1부터 n까지 반복
    for i in range(1,n):

         # 현재 비교 중인 데이터
        tmp = nums[i]

         # 반복을 위한 변수 j선언
        j=i 

         # j<=0이면 더이상 반복할 원소가 없고
         # nums[i-1]<=tmp이면 해당자리가 tmp의 자리
        while j>0 and nums[j-1]>tmp:
            nums[j] = nums[j-1]
            j-=1

         # while 탈출시 해당 자리에 tmp 대입
        nums[j] = tmp

insert_sort(nums)

for n in nums:
    print(n)

5
5
4
3
2
1
1
2
3
4
5

1. 버블정렬

• n개의 리스트에서 끝에서 두번째 인덱스 i를 시작으로 i의 데이터와 i+1 의 대소를 비교해 순서에 맞게 교환하고 이 과정을 i를 1씩 감소시켜 i가 0일때 까지 반복하면 1개의 원소가 정렬된다. 과정이 완료 될때 마다 1개의 원소가 정렬이 완료되어 다음 과정에서는 n-1개의 원소를 정렬하고 모든 원소가 정렬될때까지 반복한다.

from typing import List

n = int(input())

nums = [None]*n

for i in range(n):
    nums[i]=int(input())

 # 버블정렬을 구현 하는 함수 선언
def bubble_sort(nums:List[int])->None:

     # n-1번째 인덱스부터 0까지 반복
    for i in range(n-1,-1,-1):

         # j부터 i번째까지 반복
        for j in range(i):

             # 대소 비교후 스왑
            if nums[j]>nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]

bubble_sort(nums)

for n in nums:
    print(n)

5
5
4
3
2
1
1
2
3
4
5