정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
일반적으로 문제상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
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)
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
선택정렬에 비해 구현난이도가 높지만, 효율적이다.
array = [7,5,9,0,3,1,6,2,4,8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
if array[j] < array[j-1]: # 한 칸 왼쪽과 비교
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array)
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적인 상황에서 가장 많이 사용되며, 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
가장 기본적인 퀵 정렬은, 첫 번째 데이터를 기준 데이터(pivot)로 설정한다.
list = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(list):
// 원소가 1개 이하면 종료
if len(list) <= 1 : return list
// 중간쯤 있는 데이터를 피벗값으로 설정
pivot = list[len(list) // 2]
// 피벗보다 작은배열, 큰배열 선언
less_arr, equal_arr, big_arr = [], [], []
for i in list:
if i < pivot: less_arr.append(i)
elif i > pivot: big_arr.append(i)
else: equal_arr.append(i)
return quick_sort(less_arr) + equal_arr + quick_sort(big_arr)
print(quick_sort(list))
특정한 조건 부합시에만 사용하지만 매우 빠르게 동작한다.
데이터 크기범위가 제한되어 정수형태로 표현할 수 있을 때 사용 가능하다.
동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적이다.
데이터가 적거나 범위가 너무 크면 비효율적이다.
여러 학생의 점수를 정렬할 때 유용
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
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=' ')
정렬 예제 <두 배열의 원소 교체>
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))