[정렬] 백준 2750 수 정렬하기 (Python 파이썬)

💡문제 링크

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

 

💡문제 분석 요약

첫 째 줄에 정수 N 입력

N개의 줄에 걸쳐 정수 입력입력된 정수를 오름차순으로 정렬해서 한 줄에 하나씩 출력

 

💡알고리즘 설계

1. N개의 줄에 걸쳐 입력받은 정수를 하나의 리스트에 담기 위해 리스트 안에 for문 사용

2. 오름차순 정렬하기 위해 sort()함수 사용

 

💡코드

n = int(input())
numbers = [int(input()) for _ in range(n)]
numbers.sort()
for i in range(n):
  print(numbers[i])

 

💡 오답 풀이

...

 

💡 다른 풀이

버블정렬(선택 정렬)

# 선택 정렬 사용
numbers = [5, 3, 2, 3, 7, 1]
n = len(numbers)

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

삽입 정렬

# 삽입 정렬
numbers = [5, 3, 2, 3, 7, 1]
n = len(numbers)

for i in range(1, n): # i = 1, 2, 3, 4, 5
  j = i-1
  key = numbers[i]
  while j >= 0 and numbers[j] > key:
    numbers[j+1] = numbers[j]
    j -= 1
  numbers[j+1] = key
  print("Step%2d:" %(i+1), numbers)

 

💡 느낀점 or 기억할정보

정렬하는 방법 2가지

1. numbers.sort() 하면 기존의 numbers 리스트가 바로 정렬된다.

2. number = sorted(numbers) 하면 정렬된 리스트가 number에 저장된다.

정렬함수 매개변수

1. numbers.sort(reverse = True) 하면 내림차순 정렬

 

버블정렬 (Bubble Sort)

버블정렬은 인접한 두 요소를 비교하고, 정렬된 순서로 되어 있지 않으면 그 두 요소를 교환하는 방식으로 리스트를 정렬합니다. 이 과정을 리스트의 끝까지 반복하며, 한 번의 반복이 끝나면 가장 큰 값이 리스트의 끝에 위치하게 됩니다. 이 과정을 리스트가 완전히 정렬될 때까지 반복합니다.

동작 과정

1. 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 비교합니다.
2. 인접한 두 요소를 비교하여 필요하면 교환합니다.
3. 리스트의 끝까지 가면 가장 큰 요소가 정렬된 상태가 됩니다.
4. 위 과정을 남은 요소에 대해 반복합니다.

시간 복잡도

• 최선의 경우: O(n) (이미 정렬된 경우)
• 평균 및 최악의 경우: O(n^2)

선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 가장 작은 (또는 가장 큰) 요소를 찾아 첫 번째 위치와 교환하고, 다음 위치로 이동하여 같은 작업을 반복하는 방식으로 동작합니다.

동작 과정

1. 리스트에서 가장 작은 요소를 찾아 첫 번째 요소와 교환합니다.
2. 두 번째 요소부터 다시 가장 작은 요소를 찾아 두 번째 요소와 교환합니다.
3. 이 과정을 리스트의 끝까지 반복합니다.