정렬 탐색 알고리즘
- 데이터를 특정 기준에 따라 순서대로 나열하는 것.
Selection sort(선택 정렬)
- 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것 반복.
- N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야함.
시간복잡도
- 시간복잡도: O(N^2)
N + (N-1) +(N-2) +....+ 2(맨 마지막은 정렬하지않음) -> (N^2+N-2)/2로 표현 -> O(N^2)
선택 정렬 (Python)
array = [5,1,3,7,2,0]
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] # swap
print(array)
# 결과
[0, 1, 2, 3, 5, 7]선택 정렬 (Java)
public static void main(String[] args){
int n = 6;
int[] arr = {5,1,3,7,2,0}
for (int i = 0: i<n; i++){
if(arr[min_index]>arr[j]){
min_index = j;
}
}
# swap
int temp = arr[i]
arr[i] = arr[min_index];
arr[min_index] = temp;
}
for(int i=0; i<n; i++){
System.out.print(arr[i]+" ");
}
}
}Insertion Sort(삽입 정렬)
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입.
- 데이터를 하나씩 확인하면서, 이 데이터는 어느 위치에 들어가는게 맞을 지 매번 계산해서 적절한 위치에 들어갈 수 있도록 해줌.
- 선택 정렬에 비해 구현 난이도가 높지만, 더 빠르게 동작.
- 앞쪽에 있는 원소들이 이미 정렬되어있다고 가정하고, 뒤 쪽에 있는 원소를 앞 쪽에 있는 원소의 위치 중에서 한 곳으로 들어가도록 만드는 방식으로 동작.
시간복잡도
- 시간복잡도: O(N^2), 선택정렬과 마찬가지로 반복문이 두번 중첩.
- 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작.
- 최선의 경우 O(N)의 시간복잡도.
삽입 정렬 (Python)
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): # index i 부터 1까지 1씩 감소하며 반복하는 문법
if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
arrary[j], array[j-1] = array[j-1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
print(array)
# 결과
[0,1,2,3,4,5,6,7,8,9]삽입 정렬 (Java)
public static void main(String[] args){
int n = 10;
int[] arr = {7,5,9,0,3,1,6,2,4,8}
for(int i=0; i<n; i++){
for(int j=0; j>0; j--){
if(arr[j]<arr[j-1]){
int tmep = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
else break;
}
}
for(int i=0; i<n; i++){
System.out.print(arr[i]+" ");
}
}
}
# 결과
[0,1,2,3,4,5,6,7,8,9]Quick Sort(퀵 정렬)
- 빠른 정렬 알고리즘 중 하나.
- 데이터의 특성과 관련없이 표준적으로 사용할 수 있는 알고리즘 중 하나.
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.
- 병합 정렬과 더불어 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘.
- C, JAVA, Python의 표준 정렬 라이브러리도 퀵 또는 병합 정렬의 방식을 채택한 하이브리드 방식의 정렬 알고리즘 사용.
- 첫 번째 데이터를 기준 데이터(Pivot) 설정. - 기본적인 퀵정렬
퀵 정렬이 빠른 이유
- 이상적인 경우: 분할이 절반씩 일어난다면 O(NlogN)
- 너비높이 = NlogN = NlogN
시간복잡도
- 평균: O(NlogN)
- 최악의 경우: O(N^2)
- 이미 정렬된 배열에 대해서 퀵 정렬을 수행할 때. 정렬된 상태이면 분할이 이루어질때마다 오른쪽 데이터만 존재, 오른쪽 데이터에 계속 퀵 정렬 수행, 최악의 경우 분할이 수행되는 갯수가 N과 비례. 분할을 하기위해 매번 선형 탐색 수행 => O(N^2)
- 기본 라이브러리는 최악의 경우에도 O(NlogN) 보장되도록 구현.
퀵 정렬 (Python)
array = [7,5,9,0,3,1,6,2,4,8]
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # pivot은 첫번째 원소
left = start+1
right = end
while(left<=right):
# pivot보다 큰 데이터를 찾을 때까지 반복
while(left<=end and array[left]<=array[pivot]):
left+=1
# pivot보다 작은 데이터를 찾을 때까지 반복
while(right>start and array[right]>=array[pivot]):
right-=1
if(left>right): # 엇갈렸다면 작은 데이터와 pivot을 교체
array[right],array[pivot] = array[pivot],array[right]
else : # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right],array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right-1)
qucik_sort(array, right+1, end)
quick_sort(array,0,len(array)-1) print(array)
# 결과
[0,1,2,3,4,5,6,7,8,9]퀵 정렬 (Python): 파이썬 장점
array = [7,5,9,0,3,1,6,2,4,8]
def quick_sort(array):
if len(array) <= 1 # 원소가 1개인 경우 종료
return
pivot = array[0] # pivot은 첫번째 원소
tail = array[1:] # pivot을 제외한 리스트
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) 퀵 정렬 (Java)
public static void quickSort(int[] arr, int start, int end){
if (start>=end) return;
int pivot = start;
int left = start+1
int right = end
while(left<=right){
while(left<=end && arr[left]<=arr[pivot]) left++;
while(right>=start && arr[right]>=arr[pivot] right++;
if(left>right){
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
}
else{
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
quickSort(arr, start, right-1);
quickSort(arr, right+1, end);
}Counting Sort(계수 정렬)
- 특정한 조건을 부합할 때만 사용할 수 있지만 매우 빠르게 동작.
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용가능.
- 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K) 보장.
시간복잡도
- 시간복잡도와 공간복잡도: O(N+K).
- 데이터의 범위가 큰 경우 비효율성 초래 -> 데이터가 0과 999,999로 단 2개만 존재하는 경우. 데이터는 2개만 존재하지만 총 100만개의 원소가 담길 수 있는 배열을 만들어서 사용해야함.
- 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적 -> 학생들을 성적에 따라 정렬할 때.
계수 정렬 (Python)
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
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=' ')
# 결과
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9계수 정렬 (Java)
public static final int MAX_VALUE = 9;
public static void main(String[] args){
int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int[] arr = {7,5,9,0,3,1,6,2,9,1,4,8,0,5,2};
// 모든 범위를 포함하는 배열 선언(모든 값은 0으로 초기화)
int[] cnt = new int[MAX_VALUE+1];
for(int i=0; i<n; i++){
cnt[arr[i]] += 1
}
for(int i=0; i<=MAX_VALUE; i++){
for(int j=0; j<cnt[i]; j++){
System.out.print(i+" ");
}
}
}정렬 알고리즘 비교
- 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어있음.
| 정렬 알고리즘 | 평균 시간 복잡도 | 공간 복잡도 | 특징 |
|---|---|---|---|
| 선택 정렬 | O(N^2) | O(N) | 매우 간단 |
| 삽입 정렬 | O(N^2) | O(N) | 거의 정렬되어있는 데이터의 경우 가장 빠름 |
| 퀵 정렬 | O(NlogN) | O(N) | 대부분의 경우에 가장 적함, 충분히 빠름 |
| 계수 정렬 | O(N+K) | O(N+K) | 데이터의 크기가 한정되어있는 경우에만 사용가능,매우빠름 |
선택 정렬과 기본 정렬 라이브러리 수행시간 비교
# 선택 정렬
from random import randint
import time
# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
# 1부터 100 사이의 랜덤한 정수
array.append(randint(1,100))
# 선택 정렬 프로그램 성능 측정
start_time = time.time()
# 선택 정렬 프로그램 소스코드
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]
# 측정 종료
end_time = time.time()
print("선택 정렬", end_time - start_time)
# 배열 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
array.append(randint(1,100))
# 기본 정렬 프로그램 성능 측정
start_time = time.time()
# 기본 정렬 라이브러리 사용
array.sort()
# 측정 종료
end_time = time.time()
print("기본 정렬", end_time - start_time)
# 수행시간
선택 정렬: 35.841....
기본 정렬: 0.0013....문제 1: 두 배열의 원소 교체
- 두 개의 배열 A와 B, 두 배열은 N개의 원소로 구성. 원소는 모두 자연수.
- 최대 K번의 바꿔치기 연산을 수행, 바꿔치기 -> A에 있는 원소 하나와 B에 있는 원소를 바꾸는 것.
- A의 모든 원소의 합이 최대가 되도록 해야함
- N,K, 배열 A,B 가 주어졌을때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열A의 모든 원소의 합의 최댓값을 출력하는 프로그램 작성.
문제해결방법
- 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체.
답안 (Python)
n,k = map(int,input().split())
a = list(map(int, input(),split())
b = list(map(int, input().split())
a.sort()
b.sort()
for i in range(3):
if a[i] < b[-1-i]:
a[i],b[-1-i] = b[-1-i],a[i]
print(sum(a))
# or
a.sort()
b.sort(reverse=True) # 내림차순정렬
for i in range(3):
if a[i] < b[i]:
a[i],b[i] = b[i],a[i]
print(sum(a))답안 (Java)
int n = sc.nextInt();
int k = sc.nextInt();
Integer[] a = new Integer[n];
for(int i=0; i<n; i++){
a[i] = sc.nextInt();
}
Integer[] b = new Integer[n];
for(int i=0; i<n; i++){
b[i] = sc.nextInt();
}
Arrays.sort(a);
Arrays.sort(b, Collections.reverseOrder());
for(int i=0; i<k; i++){
if(a[i]<b[i]){
int temp = a[i];
a[i] = b[i];
b[i] = temp;
}
else break;
}
long result = 0;
for(int i=0; i<n; i++){
result += a[i]
}
System.out.println(result)
}
Hello!