퀵 정렬
솔직히 이건 외우자
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
while (pl <= pr) { // pl 항상 ++ pr은 항상--
while (a[pl] < x) {
pl++;
}
while (a[pr] > x) {
pr--;
}
if (pl <= pr) {
swap(a, pl++, pr--);
}
}
if (left < pr) {
quickSort(a, left, pr);
}
if (pl < right) {
quickSort(a, pl, right);
}
퀵 정렬 (피벗 선택)
// x[a], x[b], x[c]을 정렬(중앙값의 인덱스를 반환 )
static int sort3elem(int[] x, int a, int b, int c) {
if (x[b] < x[a])
swap(x, b, a);
if (x[c] < x[b])
swap(x, c, b);
if (x[b] < x[a])
swap(x, b, a);
return b;
}
int m = sort3elem(a, pl, (pl + pr) / 2, pr);
int x = a[m];
swap(a, m, right - 1);
pl++;
pr -= 2;
-
알고리즘을 이해하자면
- 첫 값, 중앙값, 마지막 값을 정렬하고
- 중앙 인덱스 반환 하기
병합 정렬
static int[] buff; //작업용 배열
static void __mergeSort(int[] a, int left, int right) {
if(left<right) {
// 쓰인변수 i, center, p, j, k
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문은 buferr 복사
for(i=left; i<=center; i++)
buff[p++] = a[i];
// while은 원래배열에 뭔짓거리
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;
}
부르트-포스법
- 무식하게 하나 하나 다 대조해보는
static int bfMatch(String txt, String pat) {
int pt = 0; // 택스트 담당
int pp = 0; // 패턴 담당
while (pt != txt.length() && pp != pat.length()) {
if (txt.charAt(pt) == pat.charAt(pp)) {
pt++;
pp++;
} else {
pt = pt-pp+1; //+1 인거 기억
pp = 0;
}
}
// 검색 성공
if (pp == pat.length()) {
return pt-pp; // 이것도 기억
} else {
return -1;
}
}
KMP 법
static int kmpMatch(String txt, String pat) {
int pt = 1; // kmpMatch 는 1부터 시작
int pp = 0;
int[] skip = new int[pat.length()+1];
skip[pt] = 0; // 0 넣고
while(pt != pat.length()) {
if(pat.charAt(pt) == pat.charAt(pp)) //pat 으로만 분석
skip[++pt] = ++pp; //앞 pt 뒤 pp
else if(pp == 0)
skip[++pt] = pp;
else
pp = skip[pp]; // 여긴 모두 pp
}
pt = pp = 0; // 모든게 끝나면 초기화
// 이후 로직은 부르트 포스와 비슷
else if(pp == 0)
pt++;
else
pp= skip[pp];
}
보이어 무어 법
- 처음 시행 시 주어진 패턴의 전체가 맞지 않는다면 해당 영역만큼 건너 뛰는게 가능하다
static int bmMatch(String txt, String pat) {
int pt;
int pp;
// 보이어는 길이 필요
int txtLen = txt.length();
int patLen = pat.length();
// Character.MAX_VALUE +1
int[] skip = new int[Character.MAX_VALUE +1];
// 첫 for 문은 Character.MAX_VALUE 까지
for(pt = 0; pt<=Character.MAX_VALUE; pt++)
skip[pt] = patLen;
for(pt = 0; pt<patLen-1; pt++)
// 스킵 배열 참조 = patlen - pt -1;
skip[pat.charAt(pt)] = patLen-pt-1;
while(pt < txtLen) {
pp = patLen -1;
while(txt.charAt(pt) == pat.charAt(pp)) {
if(pp == 0)
return pt;
pp--;
pt--;
}
//여기선 두 번째 for 처럼 첨조 근데 -가 pp 맞으면 첫번째꺼 틀리면 뒤에꺼
pt += (skip[txt.charAt(pt)] > patLen-pp) ? skip[txt.charAt(pt)] : patLen-pp;
}
return -1;
}