1. 버블정렬

버블 정렬은 거품이 떠오르듯 큰 숫자가 왼쪽에서 오른쪽으로 정렬된다.
즉, 올바른 위치로 갈 때까지 움직인다.
< 큰 항목이 오른쪽 끝으로 떠오른다. >

두 개의 인접한 자료 값을 보고 큰 수를 오른쪽으로 위치시키는 방법을 사용한다.
<인접한 항목들의 위치를 바꾼다.>

바깥 부분은 n-1 , 안쪽 부분도 n-1 이므로 둘을 곱하면 n^2 + 2n + 1이다.

수가 커질 수록 n^2의 영향력도 커지므로
Big - O를 이용해 나타내면 O(n^2)

Ω의 경우 상한과 동일하게 Ω(n^2)입니다.
그 이유는 가장 좋은 상황인 정렬된 상태에서도 (정렬 여부에 관계없이)
n^2번 비교하기 때문입니다.

---

만약 교환이 없어질 때 알고리즘을 일찍 종료하도록 만든다면
최선의 경우 버블정렬의 하한선은 n-1입니다.

2. 선택정렬

for i in range(n) :
전부 탐색하여 가장 작은 수를 찾는다.
가장 작은 수를 i번째 item과 swap한다.

반복할 때마다 다음으로 가장 작은 수를 고른다-!

n개의 숫자가 있을 때
n번을 기본적으로 돌아야하며 (for문 이용)
그 for문 안에서 가장 작은 수를 찾기위해 for문을 더 돌아야합니다.
하지만 이미 작은 수라고 판별된 수는 확인하지 않아도 되기때문에

< 가장 작은 수를 선택하고 왼쪽으로 옮긴다.(제 자리에 차례차례 둔다.) >

---

Big - O의 식은

n + (n-1) + (n-2) + .... + 1

이는 수학적 공식을 보면 n(n+1) / 2입니다.
이를 풀어쓰면 1/2n^2 + 1/2(n)입니다.

즉 O(n^2)입니다.

오메가의 경우도 마찬가지입니다.
정렬되어있다고 해도 내가 지금 보는 수가 가장 작은 수인지 모르기때문에 다 돌아보며 확인해야합니다. 즉 Big - O와 동일하게 Ω(n^2)입니다.

2-2 버블이 빨라요 선택이 빨라요?

안쪽 루프에서 교환이 일어나지않는다면 멈추도록 코드를 바꿀 수 있습니다.
이 경우 버블 정렬의 하한은 오메가(n)이 되므로 선택정렬보다 빠를 수 있습니다.

3.재귀

스스로 계속 내부에서 자기 자신을 호출하는 것을 의미한다.

@
@@
@@@
@@@@
를 출력한다고 할 때 재귀를 이용한 출력을 사용할 수 있다.

1) 반복을 이용한 출력

void draw(int h) 
{
	for (int i=1;i<=h;i++) {
    	for(int j=1; j<=i ;j++){
        	printf("@");
        }
        printf("\n");
    }
}

2) 재귀를 이용한 출력

void draw(int h) 
{
	if (h==0) { // 코드가 영원히 반복되는 것을 막는다. 
    	return ;
    }
    draw(h-1);
    
	for (int i=1;i<=h;i++) {
    	print("@");
    }
    printf("\n");
}

함수가 초기에 주어진 입력보다 더 작은 입력을 가지고 계속해서 자신을 호출하는 것을 확인할 수 있다.