정렬 알고리즘
정렬(Sorting)
: 데이터를 특정한 기준에 따라 순서대로 나열하는 것
정렬 알고리즘의 종류
1. 선택 정렬
: 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
import.java.util.*;
public class 선택정렬 {
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] = tmep;
}
for (int i = 0; i < n; i++) {
System.out.println(arr[i] + " "); // {0,1,2,3,4,5,6,7,8,9}
}
}
}선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 함
구현 방식에 따라 사소한 오차가 있을 수 있지만 전체 연산 횟수는 다음과 같다.
N + (N-1) + (N-2) + ··· + 2
이는 (N^2 + N -2) / 2로 표현(등차수열의 합)할 수 있는데 빅오 표기법에 따라 O(N^2)이라고 작성
2. 삽입 정렬
: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
import.java.util.*;
public class 삽입정렬 {
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++) {
// 인덱스 i부터 1씩 감소하면 반복하는 문법
for (int j = i; 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.println(arr[i] + " "); // {0,1,2,3,4,5,6,7,8,9}
}
}
}삽입 정렬의 시간 복잡도는 O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용
현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
최선의 경우(이미 모든 데이터가 정렬되어 있는 경우) O(N)의 시간복잡도를 가짐
3. 퀵 정렬
: 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
병합정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정
첫 번째 데이터를 기준으로 왼쪽에서부터 첫 번째 데이터보다 큰 수를 찾고, 오른쪽에서부터 첫 번째 데이터보다 작은 수를 찾는데, 만약 그 위치가 엇갈리는 경우 '피벗', 즉 기준 데이터를 작은 데이터의 위치와 바꾸어 준다.
이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)이라고 한다.
public class Main {
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 tmep = 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);
4. 계수 정렬
: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장
import java.util.*;
public class Main {
public static final int MAX_VALUE = 9;
public static void main(Stirng[] 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.println(i + " "); // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
}
}
}
}
계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+K)
계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용 가능!