728x90
셸 정렬
- 단순 삽입 정렬의 장점은 살리고, 단점을 보완하여 좀 더 빠르게 정렬
- 장점: 정렬을 마쳤거나 마친 상태에 가까우면 속도가 빨라짐
- 단점: 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아짐
- 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬 수행 ▶ 그룹을 합치면서 정렬 반복(이동 횟수 줄임)
- i = 8일 때 j = 4-4 = 0인데 조건으로 j >= 0이 가능하게 만들어줌으로써 구간이 [4] ~ [12]까지로 바뀌고 계속 반복 실행
static void shellSort(int[] a, int n) { //n = 배열의 길이
for(int term = n/2; term > 0; term /= 2) { //{8, 1, 4, 2, 7, 6, 3, 5} 일 때 h = 8, 4, 2, 1 ▶ h-정렬 나타냄
for(int i = term; i < n; i++) { //term부터 +1 하면서 끝까지 실행
int insertValue = a[i]; //맨 처음 insertValue = h
int j; //j = insertValue(기준값) - term(급간) 이므로 j는 0부터 시작됨
for(j = i - h; j >= 0 && insertValue < a[j]; j = j-term) { //8과0(8-8), 9와 1(9-8), 10과 2(10-8)... 비교, 극간이 4일때 8과 4일때, j = 4-4 = 0인데 조건에 j>=0이므로 0까지 감
a[j + term] = a[j]; //앞이 더 크면 바꿔줌
}
a[j+term] = insertValue; //조건문을 빠져나온 j는 이미 j-h 연산이 끝났으므로 다시 +h 해야함 (ex) 0-8 = -8이니까 +8해서 0으로 만들어줌)
}
}
}급간(h)의 설정
- h = ..., 121, 40, 13, 4, 1 을 사용하면 효율적인 정렬을 기대할 수 있음
- 1부터 h * 3 + 1 한 값
- h의 초깃값이 너무 크면 효과가 없기 때문에 배열의 요솟수 n을 9로 나눈 값을 넘지 않도록 해야 함
static void shellSort(int[] a, int n) {
int h;
for(h = 1; h < n / 9; h = h*3+1) { //h의 초깃값: n/9를 넘지 않는 가장 큰 값
}
for( ; h > 0; h /= 3) { //h가 변하는 방법, h를 3으로 나눠서 마지막에는 1이 됨
//여기부터는 같음
for(int i = h; i < n; i++) {
int tmp = a[i];
int j;
for(j = i - h; j >= 0 && tmp < a[j]; j = i-h) {
a[j+h] = a[j];
}
a[j+h] = tmp;
}
}
}- 셸 정렬의 시간 복잡도는 O(n^1.25)로 기존의 시간 복잡도 O(n^2)에 비해 매우 빠르지만, 멀리 떨어져있는 요소를 교환해야 하기 때문에 안정적이지는 않음
퀵 정렬
- 재귀를 사용하여 한 번 확인 후, 왼쪽 그룹 ▶ 오른쪽 그룹 순으로 다시 정렬 해야 함
파티셔닝 (정렬X)
- do ~ while 사용
static void partition(int[] a, int n) {
int first = 0; //첫번째
int last = n - 1; //마지막
int pivot = a[n / 2]; //피벗 = 가운데 위치
do {
while(a[first] < pivot) first++;
while(a[last] > pivot) last--;
if(first <= last) swap(a, first++, last--);
} while (first <= last); //겹치기 전까지 반복
System.out.println("pivot : " + pivot);
System.out.println("피벗 이하의 그룹");
for(int i = 0; i <= first-1; i++) //a[0] ~ a[first-1]
System.out.print(a[i] + " ");
System.out.println();
if(first > last + 1) { //이 조건 확인
System.out.println("피벗과 일치하는 그룹");
for(int i = last + 1; i <= first -1; i++) //a[last+1] ~ a[first-1]
System.out.print(a[i] + " ");
System.out.println();
}
System.out.println("피벗 이상의 그룹");
for(int i = last+1; i < n; i++) //a[last+1] ~ a[n-1]
System.out.print(a[i] + " ");
System.out.println();
}더보기
package chap06_3;
import java.util.Scanner;
//파티셔닝, 정렬x
//do ~ while에서 그룹을 나눔
public class Partition {
//swap 메서드
static void swap(int[] a, int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
static void partition(int[] a, int n) {
int first = 0; //첫번째
int last = n - 1; //마지막
int pivot = a[n / 2]; //피벗 = 가운데 위치
do {
while(a[first] < pivot) first++;
while(a[last] > pivot) last--;
if(first <= last) swap(a, first++, last--);
} while (first <= last); //겹치기 전까지 반복
System.out.println("pivot : " + pivot);
System.out.println("피벗 이하의 그룹");
for(int i = 0; i <= first-1; i++) //a[0] ~ a[first-1]
System.out.print(a[i] + " ");
System.out.println();
if(first > last + 1) { //이 조건 확인
System.out.println("피벗과 일치하는 그룹");
for(int i = last + 1; i <= first -1; i++) //a[last+1] ~ a[first-1]
System.out.print(a[i] + " ");
System.out.println();
}
System.out.println("피벗 이상의 그룹");
for(int i = last+1; i < n; i++) //a[last+1] ~ a[n-1]
System.out.print(a[i] + " ");
System.out.println();
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("요솟수: ");
int nx = scan.nextInt();
int[] x = new int[nx]; //배열 생성
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "] = ");
x[i] = scan.nextInt();
}
partition(x, nx); //파티셔닝
}
}QuickSort - 매개변수 3개
- while만 사용
- 재귀 사용시 if문이 없음
//퀵 정렬 메서드
static void quickSort(int[] a, int first, int last) {
System.out.printf("\n\n**first %d, last %d\n", first, last);
for(int p = 0; p < a.length; p++) {
System.out.printf("%d ", a[p]);
}
System.out.printf("\n");
if(first >= last) return; //재귀함수의 종료 조건
int pivot = first; //피봇(맨 처음 인덱스)
int i = first+1; //첫번째 인덱스의 다음 인덱스
int j = last; //마지막 인덱스
System.out.printf("\npivot = %d \n", a[pivot]); //피봇 확인 출력문
while(i <= j) { //i와 j가 교차될 때까지
while(i <= last && a[i] <= a[pivot]) i++; //i가 마지막까지, 피봇보다 작으면 i인덱스 증가
while(j > first && a[j] >= a[pivot]) j--; //j가 첫번째까지, 피봇보다 크면 j 인덱스 감소
if(i > j) { //i와 j가 교차될 때
swap(a, pivot, j); //j를 기준으로 피봇과 swap
} else { //i <= j 일 때(정상적일 때 멈춰있다면)
swap(a, i, j); //i와 j swap
}
System.out.printf("swap result\n"); //swap 결과 확인
for(int p = 0; p < a.length; p++) {
System.out.printf("%d ", a[p]);
}
System.out.printf("\n");
}
System.out.printf("pivot result\n"); //pivot 결과 확인
for(int p = 0; p < a.length; p++) {
System.out.printf("%d ", a[p]);
}
System.out.printf("\n");
//피봇 기준으로 재귀함수로 왼쪽 오른쪽도 반복
quickSort(a, first, j-1);
quickSort(a, j+1, last);
}더보기
package chap06_3;
import java.util.Scanner;
//재귀 사용 퀵 정렬
public class QuickSort {
//swap 메서드
static void swap(int[] a, int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
//퀵 정렬 메서드
static void quickSort(int[] a, int first, int last) {
System.out.printf("\n\n**first %d, last %d\n", first, last);
for(int p = 0; p < a.length; p++) {
System.out.printf("%d ", a[p]);
}
System.out.printf("\n");
if(first >= last) return; //재귀함수의 종료 조건
int pivot = first; //피봇(맨 처음 인덱스)
int i = first+1; //첫번째 인덱스의 다음 인덱스
int j = last; //마지막 인덱스
System.out.printf("\npivot = %d \n", a[pivot]); //피봇 확인 출력문
while(i <= j) { //i와 j가 교차될 때까지
while(i <= last && a[i] <= a[pivot]) i++; //i가 마지막까지, 피봇보다 작으면 i인덱스 증가
while(j > first && a[j] >= a[pivot]) j--; //j가 첫번째까지, 피봇보다 크면 j 인덱스 감소
if(i > j) { //i와 j가 교차될 때
swap(a, pivot, j); //j를 기준으로 피봇과 swap
} else { //i <= j 일 때(정상적일 때 멈춰있다면)
swap(a, i, j); //i와 j swap
}
System.out.printf("swap result\n"); //swap 결과 확인
for(int p = 0; p < a.length; p++) {
System.out.printf("%d ", a[p]);
}
System.out.printf("\n");
}
System.out.printf("pivot result\n"); //pivot 결과 확인
for(int p = 0; p < a.length; p++) {
System.out.printf("%d ", a[p]);
}
System.out.printf("\n");
//피봇 기준으로 재귀함수로 왼쪽 오른쪽도 반복
quickSort(a, first, j-1);
quickSort(a, j+1, last);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("요솟수: ");
int nx = scan.nextInt();
int[] x = new int[nx]; //배열 생성
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "] = ");
x[i] = scan.nextInt();
}
quickSort(x, 0, nx-1); //퀵 정렬
System.out.println("\n오름차순 정렬 했습니다.");
for(int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}QuickSort - 매개변수 2개
- do ~ while 사용
- 재귀 사용시 if문 있어야 함
1. 매개변수 3개 quickSort 만들고, overload 해서 만들고, 넣어줌
// 퀵정렬(left, right)
static void quickSort(int[] a, int left, int right) {
int pl = left; // 왼쪽 커서
int pr = right; // 오른쪽 커서
int x = a[(pl + pr) / 2]; // 피벗 (중앙의 요소)
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) swap(a, pl++, pr--);
} while (pl <= pr);
if (left < pr) quickSort(a, left, pr);
if (pl < right) quickSort(a, pl, right);
}
// 퀵정렬(n)
static void quickSort(int[] a, int n) {
quickSort(a, 0, n - 1);
}2. 처음부터 요솟수로 만들기
static void quickSort(int[] a, int n) {
for(int p = 0; p < a.length; p++) {
System.out.printf("%d ", a[p]);
}
System.out.printf("\n");
int first = 0;
int last = n-1;
int pivot = a[n/2];
do {
while(a[first] < pivot) first++;
while(a[last] > pivot) last--;
if(first <= last) swap(a, first++, last--);
} while (first <= last);
//여기 조건 잘 생각해보기
if(0 < last) quickSort(a, first);
if(first < n-1) quickSort(a, last-1);
}더보기
package chap06_3;
import java.util.Scanner;
//매개변수가 요소의 갯수만 있을 때 퀵 정렬
public class Quiz10 {
//swap 메서드
static void swap(int[] a, int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
static void quickSort(int[] a, int n) {
for(int p = 0; p < a.length; p++) {
System.out.printf("%d ", a[p]);
}
System.out.printf("\n");
int first = 0;
int last = n-1;
int pivot = a[n/2];
do {
while(a[first] < pivot) first++;
while(a[last] > pivot) last--;
if(first <= last) swap(a, first++, last--);
} while (first <= last);
//여기 조건 잘 생각해보기
if(0 < last) quickSort(a, first);
if(first < n-1) quickSort(a, last-1);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("요솟수: ");
int nx = scan.nextInt();
int[] x = new int[nx]; //배열 생성
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "] = ");
x[i] = scan.nextInt();
}
quickSort(x, nx); //퀵 정렬
System.out.println("\n오름차순 정렬 했습니다.");
for(int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}QuickSort (재귀X) - 매개변수 3개, stack 사용
tatic void quickSort(int[] a, int left, int right) {
//스택의 생성
IntStack lstack = new IntStack(right - left + 1);
IntStack rstack = new IntStack(right - left + 1);
lstack.push(left); //첫 lstack = 0
rstack.push(right); //첫 rstack = 마지막 인덱스
while(!lstack.isEmpty()) { //스택이 비워질 때까지 반복
int first = left = lstack.pop(); //처음, 왼쪽
int last = right = rstack.pop(); //마지막, 오른쪽
int pivot = a[(left + right) / 2]; //피벗
do {
while(a[first] < pivot) first++;
while(a[last] > pivot) last--;
if(first <= last)
swap(a, first++, last--);
} while (first <= right);
//왼쪽 그룹과 오른쪽 그룹으로 나뉨 a[left] ~ a[right]
//pivot 보다 작은 구간 push
if(left < last) { //a[0] ~ a[4]
lstack.push(left);
rstack.push(last);
}
//pivot 보다 큰 구간 push
if(first < right) { //a[5] ~ a[8]
lstack.push(first);
rstack.push(right);
}
}
}더보기
package chap06_3;
import java.util.Scanner;
public class Quiz11 {
//swap 메서드
static void swap(int[] a, int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
static void quickSort(int[] a, int left, int right) { //stack 사용
//스택의 생성
IntStack lstack = new IntStack(right - left + 1);
IntStack rstack = new IntStack(right - left + 1);
lstack.push(left);
rstack.push(right);
System.out.printf("a[%d] ~ a[%d]를 분석하는 문제를 스택에 푸시합니다.\n", left, right);
System.out.print("Lstack: ");
lstack.dump(); //스택 안의 모든 데이터를 바닥 → 꼭대기 순서로 출력
System.out.print("Rstack: ");
rstack.dump();
while(!lstack.isEmpty()) { //스택이 비어지지 않을 때까지 반복
int first = left = lstack.pop(); //왼쪽
int last = right = rstack.pop(); //오른쪽
int pivot = a[(left + right)/2]; //중앙
System.out.printf("스택에서 분할하는 문제를 꺼냈습니다. a[%d] ~ a[%d]를 분할합니다.\n", left, right);
do {
while(a[first] < pivot) first++;
while(a[last] > pivot) last--;
if(first <= last) swap(a, first++, last--);
} while (first <= last);
if(left < last) {
lstack.push(left); // 머리쪽 그룹의 범위
rstack.push(last); // (index)를 푸시
System.out.printf("a[%d]~a[%d]를 분할하는 문제를 스택에 푸시합니다.\n", left, last);
System.out.print("Lstack:");
lstack.dump();
System.out.print("Rstack:");
rstack.dump();
}
if (first < right) {
lstack.push(first); // 꼬리쪽그룹의 범위
rstack.push(right); // (index)를 푸시
System.out.printf("a[%d]~a[%d]를 분할하는 문제를 스택에 푸시합니다.\n", first, right);
System.out.print("Lstack:");
lstack.dump();
System.out.print("Rstack:");
rstack.dump();
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("요솟수: ");
int nx = scan.nextInt();
int[] x = new int[nx]; //배열 생성
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "] = ");
x[i] = scan.nextInt();
}
quickSort(x, 0, nx-1); //퀵 정렬
System.out.println("\n오름차순 정렬 했습니다.");
for(int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}Best! - stack
요소의 개수가 많은 그룹을 먼저 push 하면
개수가 적은 그룹이 먼저 pop되므로 스택에 쌓이는 데이터의 최대 개수가 적어짐
p.238
pivot 선택
- 첫번째로 놓는 것보다 중앙으로 놓는게 효율이 좋음
1. 나눌 배열 요소 개수가 3이상이면
임의의 요소 3을 선택
그 중에서 중앙값인 요소를 피벗으로 선택
2. 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음
끝에서 두번째 요소를 교환
피벗으로 끝에서 두 번째 요소의 값(a[right-1])을 선택하여 나눌 대상의 범위를 a[left+1] ~ a[right-2]로 좁힘
궁금증
- 왼쪽 - 중간 pivot, 오른쪽 - 첫번째 pivot
- 재귀 함수를 종료할 조건을 적지 않으면 무한루프
병합 정렬
- 분할 & 병합 반복
배열의 요소 개수가 2개 이상인 경우
1. 배열의 앞부분을 병합 정렬로 정렬
2. 배열의 뒷부분을 병합 정렬로 정렬
3. 배열의 앞부분과 뒷부분을 병합
static void merge(int[] data, int[] temp, int first, int last) {
if(first < last) { //원소가 1개면 비교를 못하니까 들어온 인덱스의 값이 last가 클 때만 비교함
int mid = (first + last) / 2; //전체원소/2
//계속 분할 해야하는데 mid값을 기준으로 fisrt~mid, mid+1~last 재귀함수 사용
merge(data, temp, first, mid);
merge(data, temp, mid+1, last);
//왼쪽, 오른쪽 부분 집합의 인덱스로 사용하기 위해서 left와 right로 설정
int left = first; //왼쪽의 첫번째 인덱스
int right = mid + 1; //오른쪽의 첫번째 인덱스
int tempIndex = left;
while(left <= mid || right <= last) {
if(right > last || (left <= mid && data[left] < data[right])) //데이터가 정상적으로 남아있는 경우, 왼쪽, 오른쪽의 값을 병합하려고 비교하는 것
temp[tempIndex++] = data[left++];
else temp[tempIndex++] = data[right++]; //오른쪽이 더 작으면 오른쪽에 있는 인덱스를 넣어줌
}
System.out.printf("\n\n**** 부분 정렬 결과 ****\n");
for(int i = 0; i <= temp.length-1; i++) {
System.out.print(temp[i] + " ");
}
for(int i = first; i <= last; i++) {
data[i] = temp[i];
}
}
}- while 반복문 안의 right > last || left <= mid 이해 안 감
더보기
package chap06_4;
public class MergeSort {
static void merge(int[] data, int[] temp, int first, int last) {
if(first < last) { //원소가 1개면 비교를 못하니까 들어온 인덱스의 값이 last가 클 때만 비교함
int mid = (first + last) / 2; //전체원소/2
//계속 분할 해야하는데 mid값을 기준으로 fisrt~mid, mid+1~last 재귀함수 사용
merge(data, temp, first, mid);
merge(data, temp, mid+1, last);
//왼쪽, 오른쪽 부분 집합의 인덱스로 사용하기 위해서 left와 right로 설정
int left = first; //왼쪽의 첫번째 인덱스
int right = mid + 1; //오른쪽의 첫번째 인덱스
int tempIndex = left;
while(left <= mid || right <= last) {
if(right > last || (left <= mid && data[left] < data[right])) //데이터가 정상적으로 남아있는 경우, 왼쪽, 오른쪽의 값을 병합하려고 비교하는 것
temp[tempIndex++] = data[left++];
else temp[tempIndex++] = data[right++]; //오른쪽이 더 작으면 오른쪽에 있는 인덱스를 넣어줌
}
System.out.printf("\n\n**** 부분 정렬 결과 ****\n");
for(int i = 0; i <= temp.length-1; i++) {
System.out.print(temp[i] + " ");
}
for(int i = first; i <= last; i++) {
data[i] = temp[i];
}
}
}
public static void main(String[] args) {
System.out.println("병합 정렬 프로그램");
int[] data = new int[]{30, 50, 7, 40, 88, 15, 44, 55, 22, 33, 77, 99, 11, 66, 1, 85};
int[] temp = new int[data.length];
System.out.printf("\n**** 병합 정렬 전 데이터 ****\n");
for(int i = 0; i <= data.length-1; i++) {
System.out.print(data[i] + " ");
}
merge(data, temp, 0, data.length-1);
System.out.printf("\n\n**** 병합 정렬 후 데이터 ****\n");
for(int i = 0; i <= data.length-1; i++) {
System.out.print(data[i] + " ");
}
}
}단순 알고리즘 - 반복문 3개
- 시간 복잡도 O(n)
package chap06_4;
import java.util.Scanner;
public class MergeArray {
static void merge(int[] a, int na, int[] b, int nb, int[] temp) {
int pa = 0;
int pb = 0;
int tempIdx = 0;
while(pa < na && pb < nb) //작은 값을 저장
temp[tempIdx++] = (a[pa] <= b[pb] ? a[pa++] : b[pb++]);
//위에서 비교가 다 끝나고 남은 요소들 처리
while(pa < na) //a에 남아있는 요소를 복사
temp[tempIdx++] = a[pa++];
while(pb < nb) //b에 남아있는 요소를 복사
temp[tempIdx++] = b[pb++];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int[] a = {2, 4, 6, 8, 11, 13};
int[] b = {1, 2, 3, 4, 9, 16, 21};
int[] temp = new int[13];
System.out.println("두 배열의 병합");
merge(a, a.length, b, b.length, temp); //a와 b를 병합하여 temp에 저장
System.out.println("배열 temp: ");
for(int i = 0; i < temp.length; i++) {
System.out.println("temp[" + i + "] = " + temp[i]);
}
}
}병합 정렬(2)
- 시간 복잡도는 O(n)
- 데이터 요소 개수가 n개일 때, 병합 정렬의 단계는 log n 만큼 필요하므로 전체 시간 복잡도 O(n log n)
- 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법
더보기
package chap06_4;
import java.util.Scanner;
public class MergeSort2 {
static int[] temp; //작업용 배열
static void __mergeSort(int[] a, int left, int right) {
if(left < right) {
int i; //a의 뒷부분을 사용할 인덱스
int mid = (left + right) / 2;
int p = 0; //p는 앞부분을 a에 복사하면서 복사 안된 인덱스의 첫번째가 되어야 함
int j = 0; //temp에 복사한 앞부분 a의 인덱스
int k = left; //최종으로 넣는 a인덱스
__mergeSort(a, left, mid); //배열의 앞부분 병합 정렬
__mergeSort(a, mid+1, right); //배열의 뒷부분 병합 정렬
//정렬을 마친 앞부분, 뒷부분 병합
//1. 배열 a의 앞부분을 temp에 복사
for(i = left; i <= mid; i++) {
temp[p++] = a[i];
}
//2. 배열 a의 뒷부분을 temp에 병합
while(i <= right && j < p) //a[5]까지 복사되면 p = 6
a[k++] = (temp[j] <= a[i]) ? temp[j++] : a[i++];
//3. 확정 정렬이 안 된 temp의 나머지 요소를 배열 a에 복사
while(j < p)
a[k++] = temp[j++];
}
}
//병합 정렬
static void mergeSort(int[] a, int n) {
temp = new int[n]; //작업용 배열 생성
__mergeSort(a, 0, n-1); //배열 전체 병합
temp = null; //작업용 배열 해제
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("병합 정렬");
System.out.print("요솟수: "); int nx = scan.nextInt();
int[] x = new int[nx];
for(int i = 0; i < nx; i++) {
System.out.print("x[" + i + "] = ");
x[i] = scan.nextInt();
}
mergeSort(x, nx); //배열 x를 병합
System.out.println("오름차순으로 정렬했습니다.");
for(int i = 0; i < nx; i++) {
System.out.println("x[" + i + "] = " + x[i]);
}
}
}Arrays.sort - 퀵 & 병합 정렬
Arrays.sort(정렬할 배열);1. 기본 자료형 배열의 정렬 - 퀵
- 퀵 정렬 알고리즘을 개선한 방법
- 배열에 같은 값이 존재할 경우 값 사이의 순서가 뒤바뀔 수 있음 = 안정적이지 않음
2. 클래스 객체 배열의 정렬 - 병합
- 병합 정렬 알고리즘을 개선한 방법
- 안정적임
자연 정렬 필요한 배열 - Object[ ] x
package chap06_4;
import java.util.GregorianCalendar;
import static java.util.GregorianCalendar.*;
import java.util.Arrays;
public class SortCalendar {
public static void main(String[] args) {
GregorianCalendar[] x = {
new GregorianCalendar(2023, NOVEMBER, 1),
new GregorianCalendar(2018, OCTOBER, 18),
new GregorianCalendar(1995, APRIL, 5),
};
Arrays.sort(x);
for(int i = 0; i < x.length; i++) {
System.out.printf("%04d년 %02d월 %02d일\n"
, x[i].get(YEAR)
, x[i].get(MONTH)
, x[i].get(DATE)
);
}
}
}- GregorianCalendar 클래스는 Comparable 인터페이스와 compareTo 메서드 구현
- 1 ~ 12월을 0 ~ 11로 표현하므로 get(MONTH)에 의해 얻는 값에 +1 해야함
자연 정렬 필요하지 않은(X) 배열 - T[ ] x, Comparator c
package chap06_4;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class PhyscExamSort {
static class PhyscData {
String name;
int height;
double vision;
public PhyscData(String name, int height, double vision) {
super();
this.name = name;
this.height = height;
this.vision = vision;
}
@Override
public String toString() {
return "PhyscData [name=" + name + ", height=" + height + ", vision=" + vision + "]";
}
//키 오름차순용 comparator
//HeightOrderComparator 인스턴스를 생성
static final Comparator<PhyscData> Height_Order = new HeightOrderComparator();
//compare 메서드를 구현한 클래스 작성
private static class HeightOrderComparator implements Comparator<PhyscData> {
public int compare(PhyscData d1, PhyscData d2) {
return (d1.height > d2.height) ? 1 : ((d1.height < d2.height) ? -1 : 0);
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
PhyscData[] x = { //키의 오름차순으로 정렬되어 있음
new PhyscData("이나령", 162, 0.3),
new PhyscData("유지훈", 168, 0.4),
new PhyscData("김한결", 169, 0.8),
new PhyscData("홍준기", 171, 1.5),
new PhyscData("전서현", 173, 0.7),
new PhyscData("이호연", 174, 1.2),
new PhyscData("이수민", 175, 2.0),
};
//배열 x를 PhyscData의 Height_Order를 사용하여 정렬
Arrays.sort(x, PhyscData.Height_Order);
System.out.println("--- 신체검사 리스트 ---");
System.out.println(" 이름 키 시력");
System.out.println("-----------------------");
for(int i = 0; i < x.length; i++) {
System.out.printf("%-8s%3d%5.1f\n", x[i].name, x[i].height, x[i].vision);
}
}
}- 두번째 매개변수로 전달하는 comparator 만드는 방법은 binarySearch와 같음
힙 정렬
- heap: 부모의 값이 자식 값보다 항상 크거나 작다는 조건을 만족하는 완전이진트리 (관계만 일정하면 됨)
- 힙의 가장 위쪽에 있는 루트의 값이 가장 크거나 작음
i = 인덱스 값으로 1부터 시작
부모 = a[(i-1) / 2]
왼쪽 자식 = a[i * 2 +1]
오른쪽 자식 = a[i * 2 +2]
힙 정렬 알고리즘
1. 루트를 배열로 꺼냄
2. 마지막 요소를 루트로 이동
3. 자기보다 큰 값을 가지는 자식 요소와 swap 하면서 아래로 내려감
▶ 이 때 자식의 값이 작거나 힙에 다다르면 작업 종료
- 오름차순은 위와 같이 진행되지만
- 내림차순은 가장 큰 값인 루트를 꺼내 a[15]로 옮김 = 정렬을 뒤에서부터 마침
책
더보기
package chap06_4;
public class HeapSort {
static void swap(int[] a, int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
//a[left] ~ a[right]를 힙으로 만듦
//루트를 없애고 힙 상태로 만듦
static void downHeap(int[] a, int left, int right) {
int tmp = a[left]; //루트
int child; //큰 값을 가진 노드
int parent; //부모
for(parent = left; parent < (right + 1) / 2; parent = child) {
int cl = parent * 2 + 1; //왼쪽 자식
int cr = cl + 1; //오른쪽 자식
child = (cr <= right && a[cr] > a[cl]) ? cr : cl; //큰 값을 가진 노드를 자식에 대입
if(tmp >= a[child])
break;
a[parent] = a[child];
}
a[parent] = tmp;
}
//힙 정렬
static void heapSort(int[] a, int len) {
//downHeap 메서드를 사용하여 배열 a를 힙으로 만듦
for(int i = (len-1) / 2; i >= 0; i--) { //a[i] ~ a[len-1]을 힙으로 만듦
downHeap(a, i, len-1);
}
//a[0]에 있는 가장 큰 값을 빼내어 마지막 배열 요소와 바꾸고, 배열의 나머지 부분을 다시 힙으로 만듦
for(int i = len - 1; i > 0; i--) {
swap(a, 0, i); //가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
downHeap(a, 0, i-1); //a[0] ~ a[i-1]을 힙으로 만듦
}
}
public static void main(String[] args) {
// int[] data = {10, 1, 5, 6, 3, 2, 4, 7, 9, 8};
int[] data = {22, 5, 11, 32, 120, 68, 70};
heapSort(data, data.length);
for(int i = 0; i < data.length; i++) {
System.out.println("data[" + i + "] = " + data[i]);
}
}
}유튜브
더보기
1.
package chap06_4;
public class HeapSort2 {
static void swap(int[] a, int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
static void heapSort(int[] a, int size) {
//1. 전체 트리 구조를 최대 힙 구조로 바꿈
for(int i = 1; i < size; i++) {
int c = i; //c는 맨 위 루트 제외하고 1, 2, 3, 4... 마지막 배열까지 반복, 자식 루트
do {
int root = (c - 1) / 2; //root는 특정 요소의 부모 루트
if(a[root] < a[c]) {
swap(a, root, c); //자식이 더 크면 부모랑 자식이랑 swap
}
c = root; //자식이 부모로 이동해서 반복적으로 수행
} while (c != 0);
}
//2. 크기를 줄여가며 반복적으로 힙 구성
for(int i = size-1; i >= 0; i--) {
//▼ 가장 큰 값을 맨 뒤로 보내는 부분
swap(a, 0, i); //기본적으로 가장 큰 값인 루트(=a[0])와 가장 마지막에 있는 요소를 바꿔줌
int root = 0;
int c = 1;
//▼ 힙 구조를 만드는 부분
do {
c = 2 * root + 1;
//자식 중에 더 큰 값 찾기
if(c < i - 1 && a[c] < a[c+1]) {//c<i-1 범위밖으로 안 넘어가게 막아줌
c++; //c를 더해줘서 오른쪽으로 이동시켜 줌
}
//루트보다 자식이 더 크다면 교환
if(c < i && a[root] < a[c]) {
swap(a, root, c);
}
root = c; //한 번 바꾸면 c를 root로 이동시켜서 재귀적으로 힙 구조를 만들어줌
} while (c < i);
}
}
public static void main(String[] args) {
// int[] data = {10, 1, 5, 6, 3, 2, 4, 7, 9, 8};
int[] data = {22, 5, 11, 32, 120, 68, 70};
heapSort(data, data.length);
for(int i = 0; i < data.length; i++) {
System.out.println("data[" + i + "] = " + data[i]);
}
}
}2.
package chap06_4;
public class HeapSort3 {
static void swap(int[] a, int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
// 2의 n 제곱을 구합니다
static int pow2(int n) {
int k = 1;
while (n-- > 0)
k *= 2;
return (k);
}
// n개의 스페이스를 출력
static void dispSpace(int n) {
for (int i = 0; i < n; i++) {
System.out.print(' ');
// System.out.print(' ');
}
}
// 힙을 출력
static void dispHeap(int a[], int n) {
int i = n;
int height = 1; // 트리의 높이
while ((i >>= 1) > 0)
height++;
i = 0;
int w = 1;
Loop: {
for (int level = 0; level < height; level++) {
dispSpace(pow2(height - level) - 1);
for (int k = 0; k < w; k++) {
System.out.printf("%02d", a[i++]);
if (i >= n)
break Loop;
if (k < w - 1)
dispSpace(pow2(height - level + 1) - 2);
}
System.out.println();
dispSpace(pow2(height - level) - 4);
for (int k = 0; k < w; k++) {
if (2 * k + i < n)
System.out.print(" ／ ");
if (2 * k + i + 1 < n)
System.out.print(" ＼ ");
if (k < w - 1)
dispSpace(pow2(height - level + 1) - 8);
}
System.out.println();
w *= 2;
}
}
System.out.println();
System.out.println();
}
static void heapSort(int[] a, int size) {
//1. 최대 힙 구조로 변환 (상 → 하)
for(int i = 1; i < size; i++) {
int c = i;
do {
//c는 자식이고, 부모는 1개, 부모가 자식보다 크게 변환
//부모가 자식을 최대 2개까지 가질 수 있고, 2번째 자식이 부모보다 클 수 있지만 size까지 다 돌면 해결
int parent = (c - 1) / 2; //0(1-2), 1(3-4), 2(5-6) 이런식으로
if(a[parent] < a[c]) {
swap(a, parent, c);
} else {
break; //이론상 변경이 없으면 이미 위로는 힙구조
}
c = parent; //자식이 부모로 이동해서 반복적으로 수행
} while (c != 0);
}
//출력
dispHeap(a, size);
//2. 크기를 줄이면서 힙 유지
for(int i = size - 1; i >= 1; i--) {
//현재 a[0] 자리(최상위, 루트)에는 최댓값이 있고, 이를 i로 빼냄. 반복하면 내림차순 정렬
swap(a, 0, i);
//i를 제외한 전부를 다시 최대힙으로 변경, 따라서 0번 자리에는 i를 제외한 가장 큰 값이 위치함
//이 때 c와 parent를 비교하여, 변경된 c 가지 방향으로만 나아가면 됨
int parent = 0;
do {
int c = 2 * parent + 1;
if(c >= i) break;
if(c + 1 < i) {
if(a[c] < a[c + 1])
c++;
}
if(a[parent] < a[c]) {
swap(a, parent, c);
} else { //변경이 없다면 c가지 방향으로 이미 힙구조가 되어 있음
break;
}
parent = c;
} while (true);
}
}
public static void main(String[] args) {
// int[] data = {10, 1, 5, 6, 3, 2, 4, 7, 9, 8};
int[] data = {22, 5, 11, 32, 120, 68, 70};
heapSort(data, data.length);
for(int i = 0; i < data.length; i++) {
System.out.println("data[" + i + "] = " + data[i]);
}
}
}블로그
더보기
package chap06_3;
public class HeapSort4 {
static void swap(int[] a, int idx1, int idx2) {
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
// 힙을 출력
static void heapSort(int[] a, int size) {
/*
* 부모노드와 heapify 과정에서 음수가 발생하면 잘못된 참조가 일어나기 때문에
* 원소가 1개 혹은 0개 일때는 함수 종료
*/
if(size < 2) return;
/*
* parent 인덱스 = a[ (index - 1) / 2 ]
* left 인덱스 = a[ index * 2 + 1 ]
* right 인덱스 = a[ index * 2 + 2 ]
*/
int lastParentIdx = (size - 1) / 2; //가장 마지막 요소의 부모 인덱스
//최대 힙
for(int i = lastParentIdx; i >= 0; i--) {
heapify(a, i, size-1);
}
/*
* root인 0번째 인덱스와 i번째 인덱스의 값을 교환해준 뒤
* 0 ~ (i-1) 까지의 부분트리에 대해 최대힙을 만족하도록 반복
*/
for(int i = size - 1; i > 0; i--) {
swap(a, 0, i);
heapify(a, 0, i-1);
}
}
static void heapify(int[] a, int parentIdx, int lastIdx) {
int left;
int right;
int largestIdx;
/*
* (현재 부모 인덱스의) 자식 노드 인덱스가 마지막 인덱스를 넘지 않을 때 까지 반복
* 왼쪽 자식 노드를 기준으로 해야 함
* 오른쪽 자식 노드를 기준으로 범위를 검사하게 되면 마지막 부모 인덱스가 왼쪽 자식만 갖고 있을 경우 왼쪽 자식노드와는 비교 및 교환 불가
*/
while((parentIdx * 2 + 1) <= lastIdx) {
left = (parentIdx * 2) + 1;
right = (parentIdx * 2) + 2;
largestIdx = parentIdx;
if(a[left] > a[largestIdx]) largestIdx = left; //while문에서 비교함
if(right <= lastIdx && a[right] > a[largestIdx]) largestIdx = right;
if(largestIdx != parentIdx) {
swap(a, parentIdx, largestIdx);
parentIdx = largestIdx;
} else {
return;
}
}
}
public static void main(String[] args) {
// int[] data = {10, 1, 5, 6, 3, 2, 4, 7, 9, 8};
int[] data = {22, 5, 11, 32, 120, 68, 70};
heapSort(data, data.length);
for(int i = 0; i < data.length; i++) {
System.out.println("data[" + i + "] = " + data[i]);
}
}
}출처 - https://st-lab.tistory.com
시간 복잡도
- 선택 정렬을 응용한 알고리즘으로 단순 선택 정렬은 정렬되지 않은 모든 요소를 대상으로 가장 큰 값을 선택
- 힙 정렬에서는 첫 요소를 꺼내면 무조건 큰 값 유지 = O(1)
- 그 대신 나머지 요소를 다시 힙으로 만들어야 함 = O(log n)
여기서 힙으로 만드는 작업을 요소의 개수만큼 반복하므로 n을 곱해야 함
단순 성택 정렬의 시간 복잡도 = O(n^2)
힙 정렬의 시간 복잡도 = O(n log n)
도수(계수) 정렬 = CountingSort
- 요소의 대소 관계를 판단하지 않고 빠르게 정렬
- 데이터의 비교, 교환 작업이 필요 없어 매우 빠름
- 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 알고 있는 경우에만 사용 가능 (0 ~ max인 경우에만)
- 입력 배열의 최댓값으로 카운트 배열을 생성하고 초기화하는지?
카운트 배열의 인덱스는 정렬할 값의 범위에 해당하는 값이고, 값은 해당 값의 출연 빈도를 의미, 카운트 배열의 크기를 입력 배열의 최댓값에 따라 결정하면, 모든 값들이 카운트 배열의 유효한 인덱스 범위 내에 포함되므로 정확한 도수 정보를 기록할 수 있음
4단계의 과정
1. count한 도수분포표 만들기 = 각 값의 개수가 담겨 있는 배열 생성
2. counting 배열의 각 값을 누적합으로 변환
3. 기존 배열의 뒤쪽부터 순회하면서 해당 값에 대응되는 counting[ ] - 1을 찾아서
4. 최종 result 배열에 인덱스에 그 값으로 인덱스를 넣기
package chap06_4;
public class Fsort {
static void counting(int[] data, int[] cnt) {
for(int i = 0; i < 10; i++) {
cnt[ data[i] ]++; //data[i]의 값을 cnt에 인덱스에 맞춰서 count
}
}
static void fSort(int[] cnt) {
for(int i = 0; i < cnt.length; i++) {
if(cnt[i] != 0) { //cnt의 값이 0이 아니면
int j = 0; //몇번 반복할지를 나타내는 변수
while(j < cnt[i]) { //인덱스니까 앞부분도 같은 숫자를 적으려면 적어야 함
System.out.print(i + " "); //인덱스 값 적기
j++;
}
}
}
}
static void guide() {
System.out.println(" 인덱스 : 0 1 2 3 4 5 6 7 8 9");
System.out.print(" 데이터 : ");
}
public static void main(String[] args) {
int[] data = {3, 5, 1, 4, 1, 2, 2, 3, 2, 7};
int[] cnt = new int[10];
System.out.println("도수 정렬 전 값");
guide();
for(int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println("\n\n정렬 전 cnt 값");
guide();
for(int i = 0; i < cnt.length; i++) {
System.out.print(cnt[i] + " ");
}
counting(data, cnt);
System.out.println("\n\n정렬 후 cnt 값");
guide();
for(int i = 0; i < cnt.length; i++) {
System.out.print(cnt[i] + " ");
}
System.out.println("\n\n도수 정렬 후 값");
guide();
fSort(cnt);
}
}누적 합으로 구하기 - 오름차순
자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)
[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) - [현재 페이지] 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합병(
st-lab.tistory.com
public class CountingSort {
public static void main(String[] args) {
int[] array = new int[100]; // 수열의 원소 : 100개
int[] counting = new int[31]; // 수의 범위 : 0 ~ 30
int[] result = new int[100]; // 정렬 될 배열
for(int i = 0; i < array.length; i++) {
array[i] = (int)(Math.random()*31); // 0 ~ 30
}
// Counting Sort
// 과정 1
for(int i = 0; i < array.length; i++) {
// array 의 value 값을 index 로 하는 counting 배열 값 1 증가
counting[array[i]]++;
}
// 과정 2
for(int i = 1; i < counting.length; i++) {
// 누적 합 해주기
counting[i] += counting[i - 1];
}
// 과정 3
for(int i = array.length - 1; i >= 0; i--) { //뒤부터 실행해야 안정적임, 앞에서부터 실행하면 같은 값이 있을 때 앞뒤가 바뀌게 되므로
/*
* i 번쨰 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤
* counting 배열의 값을 인덱스로 하여 result에 value 값을 저장한다.
*/
int value = array[i];
counting[value]--; //누적합을 인덱스로 사용하려고 하니까 -1을 해주는 것
result[counting[value]] = value;
}
}
}문제 풀이시 사용 방법
public class counting_sort {
public static void main(String[] args) {
int[] arr = new int[101]; // 수의 범위 : 0 ~ 100
for (int i = 0; i < 50; i++) { // 수열의 크기 : 50
arr[(int) (Math.random() * 101)]++; // 0 ~ 100
}
for(int i = 0; i < arr.length; i++) {
while(arr[i]-- > 0) { // arr 값이 0보다 클 경우
System.out.print(i + " ");
}
}
}
}요솟값의 범위 min ~ max, 요소의 개수 n - 수정
max - min + 2 로 하면 boundary 오류
손 코딩 했을때는 맞았음
package chap06_4;
import java.util.Arrays;
import java.util.Scanner;
public class Quiz19 {
static void countingSort(int[] arr, int n, int min, int max) {
int[] counting = new int[max - min + 1]; // min ~ max개, 기존에는 max + 1 로 누적도수 배열 만듦
System.out.println(Arrays.toString(arr));
System.out.println("최솟값:" + min);
System.out.println("최댓값:" + max);
//25 - 16 + 2 = 11인 크기 배열
//1. counting 배열 만들기
for(int i = 0; i < n; i++) {
counting[arr[i] - min]++;
}
//2. 누적 합 만들기
for(int i = 1; i < max - min + 1; i++) { //i는 1부터 시작
counting[i] += counting[i-1];
}
//3. i 원소를 인덱스로 하는 counting 배열의 값을 1 감소, counting 배열의 값을 인덱스로 result에 value 값을 저장
int[] result = new int[n]; //기존에는 밖에 었는데 매개값으로 result가 안 들어오니까 여기서 만듦
for(int i = n-1; i >= 0; i--) {
int value = arr[i];
counting[value - min]--;
result[counting[value - min]] = value;
}
//4. 결과 배열을 기존 배열에 복사
for (int i = 0; i < n; i++) {
arr[i] = result[i];
}
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("요소의 개수 : "); int nx = scan.nextInt();
int[] x = new int[nx];
for(int i = 0; i < x.length; i++) {
x[i] = (int)(Math.random()*21); // 0 ~ 20
}
int max = x[0];
for(int i = 0; i < nx; i++) {
if(x[i] > max)
max = x[i];
}
int min = x[0];
for(int i = 0; i < nx; i++) {
if(x[i] < min)
min = x[i];
}
countingSort(x, nx, min, max);
}
}boundary 오류
- counting 안에 들어가는 인덱스를 설정할 때 min을 빼주는 이유?
counting 배열의 인덱스 값은 arr 배열의 요소들을 표현하기 위한 값으로 사용
주어진 코드에서 counting 배열의 인덱스 값을 계산하기 위해 arr 배열의 값에서 min을 빼는 것은, counting 배열의 인덱스가 min 값을 0으로 가지도록 조정하기 위한 작업 - 예를 들어, arr 배열의 값이 [18, 13, 8, 8, 7]이고 min 값이 7,
counting 배열의 인덱스는 min 값인 7을 0으로 가지기 위해 arr 배열의 값에서 min을 뺀 결과인 [11, 6, 1, 1, 0]를 사용
counting 배열의 인덱스는 arr 배열의 요소들을 표현하는데 적합한 값들로 맞춰지게 됩니다. - 따라서, countingSort 메서드에서 counting 배열에 값을 누적하고, 값을 인덱스로하여 결과 배열에 저장할 때에도 arr 배열의 값에서 min을 빼고, 이를 인덱스로 사용하여 작업을 수행합니다. 이를 통해 요소의 범위에 맞게 counting 배열을 적절히 조정하고 정렬을 수행할 수 있습니다.
- counting 배열 만들 때 max - min + 2 하면 인덱스가 0부터 시작해서 안빼줘도 되지 않나?
경계 오류가 발생하는 경우는 arr 배열의 값들이 min보다 작거나 max보다 큰 경우
이럴 경우 counting 배열의 인덱스 계산이 올바르지 않을 수 있고, 이러한 상황에 대비하여 적절한 예외 처리를 추가하는 것이 좋음
728x90
'Study > Data Structure&Algorithm' 카테고리의 다른 글
| [자료구조&알고리즘] 트리, 이진 트리, 이진 검색 트리 (0) | 2023.06.25 |
|---|---|
| [자료구조&알고리즘] 리스트 (선형, 연결(포인터, 커서), 원형, 이중 연결) (0) | 2023.06.07 |
| [자료구조&알고리즘] 재귀 알고리즘(팩토리얼, 유클리드 호제법), 하노이의 탑, N퀸 문제 ??? (0) | 2023.05.08 |
| [자료구조&알고리즘] stack(스택), queue(큐) (0) | 2023.05.07 |
| [알고리즘] 유클리드 호제법 (Euclidean algorithm), 약수, 배수 (0) | 2023.04.25 |
