정렬

퀵 정렬

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	public static void main(String[] args) throws IOException {
		
	}
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	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);
	}
}

피벗(pivot) : 그룹을 나누는 기준

피벗을 x, 왼쪽 끝 요소의 인덱스 pl, 오른쪽 끝 요소의 인덱스 pr이라고 할때 작업실행

1. a[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔
2. a[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔

피벗 이하의 그룹 : a[0] ~ a[pl - 1]

피벗 이상의 그룹 : a[pr + 1] ~ a[n - 1]

피벗과 일치하는 값을 가지는 그룹 : a[pr + 1] ~ a[pl - 1]

---

병합정렬

요소의 개수가 na개인 배열 a

요소의 개수가 nb개인 배열 b

를 병합하여 배열 c에 저장

처음 인덱스는 pa,pb,pc이다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	static int[] buff; //작업용 배열
	public static void main(String[] args) throws IOException {
		
	}
	static void __mergeSort(int[] a, int left, int right) {
		if(left < right) {
			int i;
			int center = (left + right) / 2;
			int p = 0;
			int j = 0;
			int k = left;
			__mergeSort(a, left, center); //배열의 앞부분을 병합 정렬합니다.
			__mergeSort(a, center + 1, right); //배열의 뒷부분을 병합 정렬합니다.
			
			for(i = left; i <= center; i++)
				buff[p++] = a[i];
			
			while (i <= right && j < p)
				a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
			
			while(j < p)
				a[k++] = buff[j++];
		}
	}
	static void mergeSort(int[] a, int n) {
		buff = new int[n]; //작업용 배열을 생성
		__mergeSort(a, 0, n - 1); //배열 전체를 병합 정렬합니다.
		buff = null; //작업용 배열을 해제합니다.
	}
}

--mergeSort 메서드는 a, left, right 를 인자로 전달받으며 left가 right보다 작을 때 동작합니다.

1. 배열의 앞부분 (a[left] ~ a[center])을 buff[0] ~ buff[center - left]에 복사합니다. for문이 끝날 때 p의 값은 복사한 요소의 개수 center - left + 1이 됩니다
2. 배열의 뒷부분(a[center + 1] ~ a[right])과 buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 a에 저장합니다.
3. 배열 buff에 남아 있는 요소를 배열 a에 복사합니다.

---

힙 정렬

1. 부모는 a[(i - 1) / 2]
2. 왼쪽 자식은 a[i * 2 + 1]
3. 오른쪽 자식은 a[i* 2 + 2]

순서

1. 루트를 꺼냅니다.
2. 마지막 요소를 루트로 이동합니다.
3. 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복합니다. 이때 자식의 값이 작거나 잎에 다다르면 작업이 종료됩니다.

힙 정렬 알고리즘

1. 변수 i의 값을 n - 1로 초기화합니다.
2. a[0]과 a[i]를 바꿉니다.
3. a[0], a[1], ~ a[i - 1]을 힙으로 만듭니다.
4. i의 값을 1씩 줄여 0이 되면 끝이납니다. 그렇지 않으면 2로 돌아갑니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	static int[] buff; //작업용 배열
	public static void main(String[] args) throws IOException {
		
	}
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	static void downHeap(int[] a, int left, int right) {
		int temp = 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 (temp >= a[child])
				break;
			a[parent] = a[child];
		}
		a[parent] = temp;
	}
	static void heapSort(int[] a, int n) {
		for (int i = (n - 1) / 2; i>= 0; i--) //a[i] ~ a[n-1]를 힙으로 만들기
			downHeap(a, i, n - 1);
		for(int i = n - 1; i > 0; i--) {
			swap(a, 0, i); //가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
			downHeap(a, 0, i - 1); // a[0] ~ a[i - 1]을 힙으로 만듭니다.
		}
	}
}

---

도수 정렬

요소의 대소 관계를 판단하지 않고 빠르게 정렬

도수 알고리즘은 4단계로 이루어진다

1. 도수분포표 만들기
   1. 배열 f를 사용
   2. a[0]은 5점이므로 f[5]를 1만큼 증가(counting sort)
   3. f[a[i]]++;
2. 누적도수분포표 만들기
   1. 0점부터 점수 n까지 몇 명의 학생이 있는지
   2. f[i] += f[i - 1];
3. 목적 배열 만들기
   1. 배열a의 요소를 마지막 위치부터 처음 위치까지 스캔하면서 배열 f와 대조하는 작업을 수행한다.
   2. b[--f[a[i]]] = a[i];
   3. 배열 a와 같은 요소의 개수를 갖는 작업용 배열 b가 필요
   4. 미리 값을 감소시켜야함 -1
4. 배열 복사하기
   1. 배열 b값을 배열 a로 복사

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException {
		int max = x[0];
		for (int i = 1; i < nx; i++) 
			if(x[i] > max) max = x[i]; //배열 x를 도수 정렬
	}
	static void fSort(int[] a, int n, int max) {
		int[] f = new int[max + 1];
		int[] b = new int[n];
		
		for(int i = 0; i < n; i++) f[a[i]]++; //1단계
		for(int i = 1; i <= max; i++) f[i] += f[i - 1]; //2단계
		for(int i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i]; //3단계
		for(int i = 0; i < n; i++) a[i] = b[i]; //4단계
	}
}