참고 교재 : 나동빈 "이것이 취업을 위한 코딩테스트다 with Python"
참고 영상 : 링크텍스트
참고 깃허브 : 링크텍스트
1. 선택 정렬
- 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정을 반복한다.
- 선택 정렬의 시간 복잡도
N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
전체 연산 횟수는 N + (N-1) + (N-2) + ... + 2
이는 (N²+N-2)/2 로 표현할 수 있는데, 빅오 표기법에 따라 O(N²)이라고 작성한다.
<자바 코드>
import java.util.*;
public class Main {
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++) {
int min_index = i; // 가장 작은 원소의 인덱스
for (int j = i + 1; j < n; j++) {
if (arr[min_index] > arr[j]) {
min_index = j;
}
}
// 스와프
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] + " ");
}
}
}2. 삽입 정렬
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
- 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.
<자바 코드>
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for (int i = 1; i < n; i++) {
// 인덱스 i부터 1까지 감소하며 반복하는 문법
for (int j = i; j > 0; j--) {
// 한 칸씩 왼쪽으로 이동
if (arr[j] < arr[j - 1]) {
// 스와프(Swap)
int temp = 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] + " ");
}
}
}3. 퀵 정렬
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)으로 설정
1) pivot 값보다 작은 데이터를 왼쪽에서부터 찾고, pivot 값보다 큰 데이터를 오른쪽에서부터 찾는다.
2) 작은 데이터와 큰 데이터의 위치를 서로 변경한다.
3) 큰 데이터와 작은 데이터의 위치가 엇갈리는 경우 pivot과 작은 데이터의 위치를 서로 변경한다.
이렇게 pivot을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)이라고 한다.
4) 왼쪽 데이터와 오른쪽 데이터 각각 다시 퀵 정렬을 진행한다.
- 퀵 정렬의 시간 복잡도
평균의 경우 O(NlogN), 최악의 경우 O(N²)
<자바 코드>
import java.util.*;
public class Main {
public static void quickSort(int[] arr, int start, int end) {
if (start >= end) return; // 원소가 1개인 경우 종료
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);
}
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(arr, 0, n - 1);
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}퀵 정렬의 경우 파이썬으로 하는 것이 훨씬 간결하다고 합니다. 코드가 훨씬 짧네 😀
<파이썬 코드>
array = [5, 7, 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))4. 계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
- 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
- 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다.
- 공간 복잡도는 높다.
step 0) 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다.
step 1) 데이터를 하나씩 확인하며 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. (모든 데이터를 확인할 때까지 반복)
step 2) 결과적으로 최종 리스트에는 각 데이터가 몇 번씩 등장했는지 그 횟수가 기록된다.
step 3) 결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다.
인덱스 = 데이터 값
출력 결과 : 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
- 계수 정렬의 복잡도 분석
-시간 복잡도와 공간 복잡도는 모두 O(N+K) 이다.
-계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. (ex. 데이터가 0과 999,999로 단 2개만 존재하는 경우)
-계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다. (ex. 성적의 경우 같은 점수의 학생이 여러 명이므로)
<자바코드>
import java.util.*;
public class Main {
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 + " "); // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
}
}
}
}
