1. 선택 정렬
- 동작 과정
- 가장 작은 데이터를 맨 앞에 있는 데이터와 바꿈
- 1번 반복
- 시간 복잡도 : O(N^2)
- 비효율적인 정렬 방식
코드
private static void process() {
for (int changeIndex = 0; changeIndex < values.length; changeIndex++) {
int minimumNumberIndex = changeIndex;
// changeIndex 다음부터 끝까지 수 중 가장 작은 수 찾기
for (int findMinimum = changeIndex + 1; findMinimum < values.length; findMinimum++) {
if (values[minimumNumberIndex] > values[findMinimum]) {
minimumNumberIndex = findMinimum;
}
}
// values[changeIndex] <-> values[minimumNumberIndex]
int temp = values[changeIndex];
values[changeIndex] = values[minimumNumberIndex];
values[minimumNumberIndex] = temp;
}
for (int i = 0; i < values.length; i++) {
System.out.print(values[i] + " ");
}
}2. 삽입 정렬
- 동작 과정
- 리스트 내에서 (왼쪽에) 정렬된 데이터가 있음
- 리스트의 (오른쪽에) 정렬되지 않은 데이터 중 특정 데이터 하나를 지정
- 특정 데이터를 왼쪽에 정렬된 리스트에 적절한 위치에 삽입
- 1~3번 반복
- 시간 복잡도 : O(N^2)
- 리스트가 거의 정렬된 상태라면 매우 빠르게 동작함
코드
private static void process() {
// 가장 첫번째 인덱스는 정렬되어있다고 생각하고 두번째 인덱스부터 정렬 시작
for (int i = 1; i < values.length; i++) {
for (int j = i; j > 0; j--) {
if (values[j] < values[j - 1]) {
int temp = values[j];
values[j] = values[j - 1];
values[j - 1] = temp;
} else {
break; // 정렬하려는 숫자보다 작은 숫자를 만나게되면 그 왼쪽은 더 이상 볼 필요가 없으므로 break
}
}
}
for (int i = 0; i < values.length; i++) {
System.out.print(values[i] + " ");
}
}3. 퀵 정렬
-
가장 많이 사용되는 정렬 알고리즘
-
동작 과정
-
리스트의 첫 번째 데이터를 기준 숫자(pivot)로 정함 → 호어 분할 (Hoare Partition)
-
왼쪽에서부터 pivot보다 큰 수를 찾아서 선택 (a)
-
오른쪽에서부터 pivot보다 작은 수를 찾아서 선택 (b)
4-1. a가 b보다 왼쪽에 있는 경우
- a와 b 교환
4-2. a가 b보다 오른쪽에 있는 경우
- pivot과 b 교환
-
-
시간 복잡도 : O(NlogN) → 선택 정렬, 삽입 정렬보다 빠름
- 삽입 정렬과 반대로 이미 어느 정도 정렬된 상태면 속도가 느림
코드
private static void quickSort(int start, int end) {
int pivot = start;
int left = start + 1;
int right = end;
// 원소가 1개인 경우 종료
if (start >= end) {
return;
}
while (left <= right) {
// 왼쪽에서부터 피벗보다 큰 숫자 찾기
while (left <= end && values[left] <= values[pivot]) {
left++;
}
// 오른쪽에서부터 피벗보다 작은 숫자 찾기
while (right > start && values[right] >= values[pivot]) {
right--;
}
// left, right 가 엇갈리지 않았다면 둘을 교체
if (left <= right) {
int temp = values[left];
values[left] = values[right];
values[right] = temp;
} else { // left, right 가 엇갈렸다면 pivot 과 values[right] (작은 수)를 교체
int temp = values[pivot];
values[pivot] = values[right];
values[right] = temp;
}
}
// pivot 기준으로 왼쪽, 오른쪽 리스트에 대해 다시 퀵 정렬
quickSort(start, right - 1);
quickSort(right + 1, end);
}
private static void process() {
quickSort(0, values.length - 1);
for (int i = 0; i < values.length; i++) {
System.out.print(values[i] + " ");
}
}4. 계수 정렬
- 특정 조건을 만족해야만 사용할 수 있지만 사용할 수 있다면 매우 빠르게 동작함
- 조건
- 정수만 가능
- min과 max의 차이가 1,000,000 이하일 경우
- 조건
- 동작 과정
-
(최대값 + 1)에 해당하는 배열을 만듦
ex) 1, 1, 3, 5, 7 → new int[8]
-
리스트 내 해당 숫자를 인덱스로 하는 배열의 값을 증가시켜 숫자의 갯수를 셈
-
작은 수부터 갯수만큼 배열의 인덱스 출력
-
- 시간 복잡도 : O(N+K)
- N : 데이터의 개수
- K : 데이터 중 최대값
코드
private static void process() {
int maxValue = Arrays.stream(values).max().getAsInt();
int[] countCoefficient = new int[maxValue + 1];
for (int number : values) {
countCoefficient[number]++;
}
for (int i = 0; i <= maxValue; i++) {
for (int j = 0; j < countCoefficient[i]; j++) {
System.out.print(i + " ");
}
}
}5. (JAVA) Comparable 사용
- 조건
- 정렬 조건이 필요함
- 시간 복잡도는 약 O(N log N)
- primitive 원소
- Dual-Pivot Quick Sort
- 최악의 경우 O(N^2) → 운이 나쁘면 시간초과 날 수도 있음
- In-place
- 정렬하는 과정에서 무시할만큼의 적은 메모리를 사용함
- object 원소
- Tim Sort
- 최악의 경우도 O(N log N)
- Stable
- 동등한 위상을 갖는 원소가 정렬 후에도 순서가 보존됨 ex) A(1) A(2) D C B... → A(1) A(2) B C D ...
- 동등한 위상을 갖는 원소가 정렬 후에도 순서가 보존됨 ex) A(1) A(2) D C B... → A(1) A(2) B C D ...
- primitive 원소
- 특성
- 비슷한 값의 정보들을 서로 인접해 있음 → 정렬만 해도 문제가 쉽게 풀리는 경우가 많음
- 비슷한 값의 정보들을 서로 인접해 있음 → 정렬만 해도 문제가 쉽게 풀리는 경우가 많음
코드
Comparable 인터페이스를 구현한 클래스(Element) 정의compareTo 메소드 오버라이딩- 오름차순 : this - 매개변수
- 내림차순 : 매개변수 - this
- Element 타입의
배열에 값을 입력받음 Arrays.sort(배열)
static class Element implements Comparable<Element> {
int score;
@Override
public int compareTo(Element other) { //정렬의 기준이 되는 메소드
return this.score - other.score;
}
}
public static void process() {
Arrays.sort(Students); //오버라이딩 한 compareTo 메소드를 기준으로 정의
}