정렬
데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말함
선택 정렬
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다. 숫자가 총 N개 있을 때 N-1번 반복하면 된다
연산 횟수는 N+(N-1)+(N-2)+ … +2 = (N² + N)/2 번이다. 따라서 시간 복잡도는 O(N²) 이므로 알고리즘 문제 풀이에 사용하기에는 느리다
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 # 현재 원소 인덱스가 min_index로 대치
array[i] , array[min_index] = array[min_index],array[i] # 스와이프
print(array)
삽입 정렬
데이터를 하나씩 확인하여 각 데이터를 적절한 위치에 삽입한다 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정하여 정렬되어 있는 데이터 리스트에서 특정한 데이터가 들어갈 위치를 찾아 삽입한다.
삽입 정렬은 두번째부터 시작하여 첫번째 데이터가 정렬되어 있다고 가정하여 첫번째 데이터 앞 또는 뒤에 삽입한다.
삽입 정렬은 데이터가 거의 정렬 되어 있을 때 훨씬 효율적이다. 삽입 정렬의 시간 복잡도는 시간 복잡도는 O(N²)지만 데이터가 거의 정렬되었을 때는 빠르게 동작하여 최선의 경우 O(N)의 시간 복잡도를 가진다
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):
if array[j] < array[j-1]:
array[j],array[j-1] = array[j-1],array[j]
else :
break
print(array)
퀵 정렬
기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다
퀵 정렬은 분할하여 정렬하기때문에 시간복잡도는 O(NlogN)이다. 삽입 정렬과 선택 정렬보다 훨씬 빠르다. 다만 최악의 경우 시간 복잡도가 O(N²)이다. 이미 데이터가 정렬되어 있는 경우 매우 느리게 동작한다.
피벗을 설정하여 정렬을 수행한 이후에 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다.
퀵 정렬은 글로만 이해하기가 어려움으로 꼭 그림과 함께 봐야한다.
- pivot을 선정 , 비교를 위한 left와 right 변수 할당
- left와 right를 pivot 과 비교하며 이동
- pivot 위치 수정
- 분할된 리스트에 1~3 과정 적용 및 반복
array = [7,5,9,0,3,1,6,2,4,8]
def quick_sort(array,start,end):
if start >=end :#원소가 1개인 경우 종료
return
pivot = start
left = start+1
right = end
while left <= right :
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left <= end and array[left] <= array[pivot] :
left +=1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while right > start and array[right]>= array[pivot]:
right-=1
#엇갈렸을 때
if left>right:
array[right] , array[pivot] = array[pivot] , array[right]
else :
array[right] , array[left] = array[left] , array[right]
quick_sort(array,start,right-1)
quick_sort(array,right+1,end)
quick_sort(array,0,len(array)-1)
print(array)
- 파이썬 장점을 살린 퀵 정렬 소스코드
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))
계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
계수 정렬을 이용할 때 모든 범위를 담을 수 있는 크기의 리스트를 선언해야하기 때문에 , 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
따라서 동일한 값을 가지는 데이터가 여러개 등장하고 리스트 크기가 작을때 유리하다.
계수 정렬의 공간 복잡도는 O(N+K)이다.
- 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 수 중에 가장 작은 수를 m 가장 큰 수를 M이라고 하면 m부터 M까지의 모든 범위를 담을 수 있는 리스트를 생성해야 한다.
- 만약 초기 나열된 수가 530102 라고 한다면 리스트는 아래와 같다 첫째줄에는 수를 순서대로 적고, 두번째 줄에는 그 수가 몇번 나왔는지 적는다.
| 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 1 | 1 | 1 | 0 | 1 |
- 이제 순서대로 출력하면 된다.
- 001235
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(array)):
for j in range(count[i]):
print(i,end=' ')
파이썬 정렬 라이브러리
- sorted()
- 병합 정렬을 기반으로 만들어 졌으며 퀵 정렬보다 느리고, 최악의 경우에는 시간 복잡도가 O(NlogN)이다
- 리스트와 딕셔너리 자료형 등을 입력 받아서 정렬된 결과를 출력하는데 이때, 집합 자료형이나 딕셔너리 자료형을 입력 받아도 반환되는 결과는 리스트 자료형이다.
array = [7,5,9,0,3,1,6,2,4,8] result = sorted(array) print(result) - sort()
- 리스트 객체의 내장 함수
- 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다
array = [7,5,9,0,3,1,6,2,4,8] array.sort() print(array) - sorted()나 sort()를 이용할 때 key 매개변수를 입력 받을 수 있다
- Key 값이 정렬 기준이 된다.
array = [('바나나',2),('사과',5),('당근',3)] def setting(data): return data[1] result = sorted(array,key = setting) print(result) - 정렬 라이브러리 시간 복잡도
- 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
- 직접 퀵 정렬을 구현할 때보다 더욱더 효과적이다
- 문제 유형
- 정렬 라이브러리로 풀 수 있는 문제 : 기본 정렬 라이브러리 사용
- 정렬 알고리즘의 원리에 대해 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 문제를 풀어야 함
- 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기법으로 풀 수 없고 계수 정렬 등의 다른 정렬 알고리즘을 이용할 것
예제 6-2 위에서 아래로
문제
입력 받은 숫자를 내림차순으로 정렬해 출력해라
n= int(input())
arr=[]
for i in range(n):
num= int(input())
arr.append(num)
arr.sort(reverse=True)
for i in arr:
print(i,end=" ")
예제 6-3 성적이 낮은 순서로 학생 출력하기
문제
학생의 이름과 성적을 입력 받아 낮을 순서로 학생 이름을 출력해라
n= int(input())
arr=[]
for i in range(n):
name, score = map(str,input().split())
arr.append((name,int(score)))
arr.sort(key=lambda ind : ind[1])
for i in arr:
print(i[0],end=" ")
예제 6-4 두 배열의 원소 교체
문제
두 배열 A,B는 N개의 원소로 구성되어 있으며, 최대 K번 서로 원소를 교환할 수 있다.
이때 A의 모든 원소의 합이 최댓값을 출력하는 프로그램을 작성해라
n,k = map(int,input().split())
arr1=[]
arr2 = []
arr1 = list(map(int,input().split()))
arr2 = list(map(int,input().split()))
arr1.sort()
arr2.sort(reverse=True)
for count in range(k):
if arr1[count] < arr2[count]:
arr1[count] , arr2[count] = arr2[count] , arr1[count]
else :
break
print(sum(arr1))