정렬
arr = [3,1,4,5,2]
arr.sort() # 오름차순 정렬
print(arr) #[1,2,3,4,5]
arr.sort(reverse = True) #내림차순 정렬
print(arr) #[5,4,3,2,1]
정렬로직에는 선택정렬, 삽입정렬, 버블정렬등이 있다. 이 로직들은 크게 복잡하지 않아 쉽게 배울 수 있다는 장점이 있찌만, 너무 느리기 때문에 실제로 사용하기는 어렵다.
선택정렬
: 선택정렬은 우리가 앞에서 배운 최대값, 최소값을 찾는 로직과 두 값을 바꿔주는 로직을 혼합하여 구현하는 로직이다
3 1 4 5 2 #처음 주어진 리스트
1 3 4 5 2 # 최소값 1과 맨 앞의 수인 3과 교환
1 2 4 5 3 #첫번째를 제외한 최소값 2와 두번째 수인 3과 교환
1 2 3 5 4 #두번째를 제외한 최소값 3와 세번째 수인 4와 교환
1 2 3 4 5 #세번째를 제외한 최소값 4와 네번째 수인 5를 교환
arr = [ 3,1,4,5,2]
def selection_sort(arr) :
n = len(arr) #리스트 길이 확인
for i in range(n) :
min_idx = i
for j in range(i+1 , n) :
if arr[j] < arr[min_idx] :
min_idx = j
arr[i] , arr[min_idx] = arr[min_idx] , arr[i]
return arr
거품정렬(버블정렬)
: 앞에서 두 수를 비교해서 큰 수를 뒤로 보내는 것을 반복하는 방법
3 1 4 5 2 #처음 주어진 리스트
1 3 4 5 2 # 3과1을 비교해서 큰 수를 뒤로 보냄
1 3 4 5 2 #3과4는 정렬이 되어 있으므로 넘어감
1 3 4 5 2 #4와 5도 정렬이 되어 있으므로 넘어감
1 3 4 2 5 #2와 5의 자리를 바꿔줌
1 3 2 4 5 #4와 2의 자리를 바꿔줌
1 2 3 4 5 #3과 2의 자리를 바꿔줌
def bubble_sort(arr) :
n = len(arr)
for i in range(n) :
for j in range(n-i-1) :
if arr[j+1] < arr[j] :
arr[j],arr[j+1] = arr[j+1],arr[j]
return arr
삽입 정렬
: 새로운 리스트에 기존 리스트 값을 위치에 맞게 넣는 방식으로 진행
3 1 4 5 2 #처음 주어진 리스트
3 #기존 리스트에서 첫번째 값을 꺼내여 새로운 리스트에 넣음
1 3 #1을 꺼내어 3과 비교하여 정렬
1 3 4 #위의 리스트에서 4의 위치에 맞게 삽입함
1 3 4 5 #위의 리스트에서 5의 위치에 맞게 삽입함
1 2 3 4 5 #위의 리스트에서 2의 위치에 맞게 삽입함
def insertion_sort(arr) :
new_arr = [arr[0]]
for i in range(1,len(arr)) :
j = 0
while j < i and arr[j] < arr[i] :
j+=1
new_arr.insert(j,arr[i])
return new_arr
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[백준] 2961번 도영이가 만든 맛있는 음식 - 파이썬 (1) | 2023.10.04 |
---|---|
[백준] 2503번 숫자야구 - 파이썬 (0) | 2023.10.03 |
기초 알고리즘 [수학] (0) | 2023.09.27 |
코딩테스트 공부 day3 [DFS/BFS] (0) | 2023.09.27 |
코딩테스트 공부 START (0) | 2023.09.18 |