백준#2750 수 정렬하기

1. 문제

2. 풀이

1) 파이썬의 기본 정렬 라이브러리 사용

• 시간복잡도: O(nlogn)
• 나의 풀이
  

num_count = int(input())
nums = []
for _ in range(num_count):
    nums.append(int(input()))
nums.sort()
for num in nums:
    print(num)

• 다른 사람의 풀이

n = int(input())
array = list()

for _ in range(n):
    array.append(int(input()))

array.sort()

for i in array:
    print(i)

2) 선택정렬 알고리즘

• 시간복잡도: O(n^2)

  선택 정렬 (selection sort)

• 첫번째 항목과 순차적으로 비교하여 가장 작거나 큰 항목을 찾아서 첫 번째 항목과 위치를 바꾼다

• 계속 반복한다

• 이런 식으로 리스트 끝에 도달할 때 까지 이 과정을 반복한다
  즉, 첫번째로 작은걸 찾아서 첫번째랑 바꾸기
  두번째로 작은걸 찾아서 두뻔째랑 바꾸기

• 나의 풀이
  

def selection_sort(nums):
    for target_index in range(len(nums)):
        target = nums[target_index]
        min = target
        min_index = target_index
        for sub_index in range(target_index, len(nums)):
            if nums[sub_index] < min:
                min = nums[sub_index]
                min_index = sub_index
        nums[target_index] = min
        nums[min_index] = target
    return nums


num_count = int(input())
nums = []
for _ in range(num_count):
    nums.append(int(input()))
for num in selection_sort(nums):
    print(num)

• 다른사람의 풀이
  

n = int(input())
array = list()

for _ in range(n):
    array.append(int(input()))

for i in range(n):
    min_index = i
    for j in range(i+1, n):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

for i in array:
    print(i)

4. 느낀 점

Reference

• 책/파이썬 자료구조와 알고리즘/미아 스타인지음/최길우 옮김/한빛미디어