선택정렬
- 타 정렬들에 비해 매우 비효율적 but 가장 작은 데이터를 찾는 문제가 많으므로 기억해둬야 함!
def SelectionSort(arr,N):
for i in range(N-1): # 0부터 N-2까지~~마지막 요소는 이미 정렬되어있으므로 -1
minIdx = i # 최솟값 인덱스 초기화(맨 앞자리)
for j in range(i+1,N): # 비교를 위해 그다음인 1부터 N-1까지~~
if arr[minIdx] > arr[j]: # 최솟값 인덱스 갱신1
minIdx = j # 최솟값 인덱스 갱신2
arr[i], arr[minIdx] = arr[minIdx], arr[i] # 찾은 최솟값이랑 자리바꾸기삽입정렬
- 거의 정렬되어 있는 상태일 때 매우 강력한 효율
for i in range(1, len(arr)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복
if arr[j] < arr[j-1]: # 한칸씩 왼쪽으로 이동
arr[j], arr[j-1] = arr[j-1], arr[j]
else: # 자신보다 작은 데이터를 만나면 그자리 내자리! 멈춤
break퀵 정렬
- 선택, 삽입에 비해 매우 빠름. but 데이터가 이미 정렬되어 있는 경우엔 매우 느림
def quick_Sort(arr, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # 기준
left = start + 1
right = end
while left <= right: # 왼오가 같아지면 종료
while left <= end and arr[left] <= arr[pivot]: # 배열 인덱스 범위 안에서 피벗보다 작거나 같은 데이터인 동안 반복
left += 1
while right > start and arr[right] >= arr[pivot]: # 위랑 반대
right += 1
if left > right: # 엇갈렸으면? 작<->피벗 교체
arr[right], arr[pivot] = arr[pivot], arr[right]
else: # 엇갈리지 않았다면 작<->큰 교체
arr[left], arr[right] = arr[right], arr[left]
quick_Sort(arr, start, right-1)
quick_Sort(arr,right+1,end)
# 호출 예시 quick_Sort(array,0,len(array)-1)계수 정렬
- 특정 조건(데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때)이 부합할 때에만 사용가능하지만 매우 빠름
- 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리함!
- 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 사용x
- why? 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문!
# 배열의 모든 원소의 값이 0보다 크거나 같다고 가정
counts = [0] * (max(arr)+1) # 0부터 시작하므로 +1 해주기!
for i in range(len(arr)):
counts[arr[i]] += 1
for i in range(len(counts)):
for j in range(counts[i]):
print(i, end=' ')정렬 라이브러리에서 key를 활용한 소스코드
array = [('A',2),('B',5),('C',3)]
def setting(data):
return data[1]
result = sorted(array, key=setting) # key값은 함수가 들어가야하며 이는 정렬 기준이 됨
print(result) # [('A',2),('C',3),('B',5)]기존의 list가 필요하면 sorted 필요없으면 sort
2부 - 3번 p.180
data = []
N = int(input())
for i in range(N):
info = input().split()
data.append((info[0], int(info[1])))
result = sorted(data, key=lambda x: x[1]) # x를 받으면 x[1]을 return하는 임시함수
for i in data:
print(i[0],end=" ")2부 - 4번 p.182
N, K = map(int, input().split()) # 배열길이 / 바꿔치기 최대횟수
A = list(map(int, input().split()))
B = list(map(int, input().split()))
for i in range(K):
if min(A) <= max(B):
A[A.index(min(A))], B[B.index(max(B))] = B[B.index(max(B))], A[A.index(min(A))]
print(sum(A))교과서 풀이
N, K = map(int, input().split()) # 배열길이 / 바꿔치기 최대횟수
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort(reverse=True)
for i in range(K):
if A[i] < B[i]:
A[i], B[i] = B[i], A[i]
else:
break
print(sum(A))3부 23번 국영수 p.359
* 튜플을 원소로 하는 리스트가 있을 때, 그 리스트를 정렬하면 기본적으로 각 튜플을 구성하는 원소의 순서에 맞게 정렬!
* 음수기호를 붙이면 내림차순!
data =[]
N = int(input())
for i in range(N):
data.append(input().split())
data.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))
# 두번째 내림/세번째 오름/네번째 내림/첫번째 오름 순서!
for i in data:
print(data[0])3부 24번 안테나 p.360
N = int(input())
H = list(map(int, input().split()))
H.sort()
sum_list = []
for i in H:
sum_dis = 0
for j in H:
sum_dis += abs(i-j)
sum_list.append(sum_dis)
print(H[sum_list.index(min(sum_list))])N = int(input())
H = list(map(int, input().split()))
H.sort()
print(H[(N-1)//2]) # 중간값이 항상 최솟값이므로3부 25번 실패율 p.361
# 실패율 = 도달 but 클리어x 수 / 도달 수
N = int(input()) # 스테이지 개수
stages = list(map(int, input().split()))
# N+1은 완주한 유저
# 실패율이 같다면 오름차순
# 실패율 100%면 실패율 0
def solution(N, stages):
answer = []
length = len(stages)
for i in range(1, N+1):
cnt = stages.count(i)
if length == 0:
fail = 0
else:
fail = cnt / length
answer.append((i, fail)) # 튜플로 묶어서 저장!
length -= cnt # 처리완료한 스테이지 모두 삭제
answer = sorted(answer, key=lambda x: x[1], reverse=True) # key를 이용해서 실패율을 기준으로 정렬하도록
answer = [i[0] for i in answer] # 스테이지만 출력해야되므로!
return answer3부 26번 카드 정렬하기 p.363