알고리즘 중간

선형검색

보초법

int i = 0;
arr[arr.length-1] = value;
	while (true) {
	if (arr[i] == value) break;
	i++;
}
return i == arr.length ? -1 : i;

• 배열에 크기를 한칸 더 받음아서 처리

재귀함수

팩토리얼 계산

if (n <= 0) {
	return 1;
}
return n*nPack(n-1);

최대 공약수

if (b == 0) {
	return a;
} else {
	return GCD(b, a % b);
}

• 최소 공배수 x*y/gcd(x, y)

하노히 탑

// no 옮길 원반 수, x 시작기둥 y 목표 기둥
static void move(int no, int x, int y) {
	if (no > 1) {
		move(no - 1, x, 6 - x - y);
	}
	if (no > 1) {
		move(no - 1, 6 - x - y, y);
	}
}

• 첫 if는 끝에 6-x-y
• 뒤 if는 중앙에 6-x-y
• 시작할때 move(원반수, 1, 3)

정렬

버블 정렬 개선 2

while(k<n-1) {
	int last = n-1;
	for(int j=n-1; j>k; j--) {
		if(a[j-1] > a[j]) {
			...
			last = j;
		}
	}
	k = last;
}

• k 까진 정렬 된것으로 보고 범위를 좁힌다

삽입정렬

for(int i=1; i<n; i++) {
	int j;
	int tmp = a[i];
	for( j=i; j>0 && a[j-1]>tmp; j--) {
		a[j] = a[j-1];
	}
	a[j] = tmp;
}

• 2 3 5 4 이렇게 된경우 4를 정렬할 시 해당 4 위치를 5로 바꾸고 원래 5 위치에 삽입 됨

셀 정렬

 int h;
 for (h = 0; h < arr.length; h = h * 3 + 1);
 
for (; h > 0; h /= 3) { // 나눗셈
	for (int i = h; i < arr.length; i++) { // 그 나눈것들로 하나씩 올리는 for 문
		int j, temp = arr[i]; 
		for (j = i - h; j >= 0 && arr[j] > temp; j -= h) { // 그 i 값으로 - h 해주면서 
			arr[j + h] = arr[j]; // j+h 에 j 대입
		}
		arr[j + h] = temp; // j+h에 temp 대입
	}
}

• 중앙부는 삽입이랑 비슷