정렬
선택 정렬 O(N**2)
- 가장 작은 값 찾아서 첫번째 자리와 교환 → (n-1)번째 까지
array = [5,4,3,2,1,6,7,8,9]
for i in range(len(array)-1):
m = i
for j in range(i+1, len(array)):
if array[m] > array[j]:
m = j
array[i], array[m] = array[m], array[i] # 실제 교환은 최소
삽입 정렬
- 정렬이 되어있으면 최적으로 O(N)이라 정렬이 많이 된 경우에 좋음
- 첫 원소는 정렬되었다고 가정하고, 두번째 원소부터 어디에 위치할지 비교
a = [5,4,3,2,1,6,7,8,9]
for i in range(1, len(array)):
for j in range(i-1, 0, -1): # 작으면, 한칸씩 앞으로
if a[i] > a[j]:
a[i], a[j] = a[j], a[i]
else:
break
퀵 정렬
- 평균 O(NlogN)로 상대적으로 빠름,그러나 최악은 O(N**2)이며 왼쪽 데이터가 정렬되어있는 경우는 매우 느려서 선택 정렬과 반대
- 첫 원소를 피벗으로 잡아서 왼쪽에서 큰 값과 오른쪽에서 작은 값 위치를 변경 → 왼쪽과 오른쪽의 탐색 값이 서로 엇갈리면, 작은 데이터와 피벗 위치 교환 → 피벗 기준 2개인 각 파트에서 다시 피벗을 설정 후 진행
def quick(a, start, end):
# 원소가 1개인 경우, 종료
if start == end:
break
p = a[start]
i = start+1
j = end
while i <= j:
while a[i] < p:
i += 1
while a[j] < p:
j -= 1
if i > j:
break
if i > j: # 엇갈림 -> while문 종료
a[j], a[start] = a[start], a[j]
else:
a[i], a[j] = a[j], a[i]
a[0], a[i] = a[i], a[0]
quick(a, start, i-1)
quick(a, i+1, end)
a = [5,4,3,2,1,6,7,8,9]
quick(a, 0, len(a)-1))
print(a)
# python의 장점 이용
def quick(a):
# 원소가 1개인 경우, 종료
if len(a) == 1:
return a
p = a[0]
rest = a[1:]
left = [x for x in rest if x <= p]
right = [x for x in rest if x > p]
return quick(letf) + p + quick(right)
a = [5,4,3,2,1,6,7,8,9]
print(quick(a))
계수 정렬 : O(데이터 개수 + 데이터 최댓값)을 최악에도 보장
- 특정 조건(데이터 범위가 제한되어 정수로 표현 가능한 경우)에서만 사용 가능하지만, 매우 빠름
- 모든 데이터+1을 담을 수 있는 리스트 생성 후, 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시키는 방식 ⇒ 1이 들어간 곳은 숫자가 존재함
a = [5,4,3,2,1,6,7,8,9]
result = [0]*(max(a)+1) # 포인트 : 최대값 + 1
for i in a:
result[i] += 1 # 중복 고려
for i in range(len(result)): # i(인덱스)가 값
for j in range(i):
print(i, end = " ")
- reverse() : O(N)
- sorted() : O(NlogN) 보장
문제 풀이
- 정렬 라이브러리 이용
- 계수 정렬 or 퀵 정렬 이용
1. 위에서 아래로
초기 idea : 내림차순 정렬 → 수의 개수가 500개 이하 정수로 계수 정렬 이용
효율 idea : 라이브러리 이용
2. 성적이 낮은 순서로 학생 출력하기
3. 두 배열의 원소 교체
- 횟수만큼 max, min 탐색 → 차라리 O(NlogN)인 sort 라이브러리가 나음