Sorting 정렬
이것이 코딩테스트다 with 파이썬을 읽고 작성하는 글입니다.
정렬
정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열
선택정렬
선택정렬 : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정을 반복하는 정렬
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_index = i
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
print(array)
시간 복잡도 : O(N^2)
삽입정렬
삽입정렬 : 특정한 데이터를 적절한 위치에 삽입하는 정렬
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
for j in range(i, 0, -1):
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j]
else:
break
print(array)
시간 복잡도 : O(N^2), 거의 정렬된 상태인 경우 매우 빠르게 동작
퀵정렬
퀵정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬
피벗 : 교환하기 위한 기준
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))
시간 복잡도 : O(NlogN), 거의 정렬된 상태인 경우 매우 느리게 동작
계수정렬
계수정렬 : 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬
조건 : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있어야 함
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1
for i in range(len(count)):
for j in range(count[i]):
print(i, end=' ')
시간 복잡도 : O(N + K), K(최대값의 크기), 데이터의 크기가 한정되어 있고 많이 중복되어 있을 때 유리
파이썬 정렬 라이브러리
sort(), sorted()
: 병합 정렬 기반, O(NlogN)
[문제] 위에서 아래로
수가 크기에 상관없이 나열되어 있다.
내림차순으로 정렬하는 프로그램을 만드시오.
-> 정렬 라이브러리 이용, reverse 사용하여 내림차순 정렬
# 내 풀이
n = int(input())
array = [0] * n
for i in range(n):
array[i] = int(input())
array.sort(reverse=True)
for data in array:
print(data, end=' ')
[문제] 성적이 낮은 순서로 학생 출력하기
N명의 학생 정보는 이름과 성적으로 구분된다.
성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오.
-> 정렬 라이브러리 이용, lambda 사용하여 특정 기준으로 정렬
# 내 풀이
n = int(input())
array = []
for i in range(n):
name, score = input().split()
array.append([name, int(score)])
array = sorted(array, key=lambda k:k[1])
for data in array:
print(data[0], end=' ')
[문제] 두 배열의 원소 교체
A, B 두 배열은 N개의 원소로 구성되어 있으며 모두 자연수이다.
최대 K번의 바궈치기 연산을 수행할 수 있다.
A의 모든 원소 합이 최대가 되도록하는 프로그램을 작성하시오.
-> 정렬 라이브러리 이용, swap 사용
# 내 풀이
n, k = map(int, input().split())
arrayA = sorted(list(map(int, input().split())))
arrayB = sorted(list(map(int, input().split())), reverse=True)
12345
54432
for i in range(k):
if arrayA[i] >= arrayB[i]: break
arrayA[i], arrayB[i] = arrayB[i], arrayA[i]
print(sum(arrayA))
Author And Source
이 문제에 관하여(Sorting 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dddooo9/Sorting-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)