(c++)c++ 구현

각 정렬 별 시간복잡도는 여기 에 있다.

선택 정렬

key값이랑 최소값이랑 바꾸는 것
idx > j 가 만족할 때 j를 idx에 넣어줌으로써 최소값을 넣는다.

int n, idx, tmp;
cin >> n;

for (int i = 0; i < n; i++)
	cin >> arr[i];

for (int i = 0; i < n - 1; i++) {
	idx = i;
	for (int j = i + 1; j < n; j++) {
		if (arr[j] < arr[idx])
			idx = j;
	}
	tmp = arr[i];
	arr[i] = arr[idx];
	arr[idx] = tmp;
}

for (int i = 0; i < n; i++)
	cout << arr[i];

버블 정렬

j 와 j+1 을 비교해 나아간다.
안쪽 for문이 끝날때마다 제일 끝 수는 비교하지 않아도 된다. 따라서 범위를 n-i-1로 해주면 된다. ex)0~6 0~5 0~4 이런식이다.

int n, idx, tmp;
cin >> n;

for (int i = 0; i < n; i++)
	cin >> arr[i];

for (int i = 0; i < n - 1; i++) {
	for (int j = 0; j < n-i-1; j++) {
		if (arr[j+1] < arr[j]) {
			tmp = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = tmp;
		}
	}
}

for (int i = 0; i < n; i++)
	cout << arr[i] << " ";

삽입 정렬

key를 선정 후 앞으로 가면서 자신보다 클 경우 뒤로 보내고 자기 자신이 그 자리를 매꾸는 형태이다.
포인트는 안쪽 for문 j를 바깥에서 선언을 해주는 것이다.

int n, tmp, j;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 1; i < n; i++) {
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--) {
			if (tmp < arr[j])
				arr[j+1] = arr[j];
			else
				break;
		}
		arr[j + 1] = tmp;
	}

	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";

이분 탐색

첫 값과 끝 값 그리고 중간 값을 수시로 바꿔주며 찾는 탐색기법이다.

셸 정렬

퀵 정렬

https://bigdatadiary0819.tistory.com/113

힙 정렬

병합 정렬

split

factorial(재귀)

int factorial(int num){    
	if (num == 1) 
    	return 1;     
    return num * factorial(num - 1);
} 

int main()
{    
	int n;
    cin >> n;
    int result = 0;
    
    result = factorial(num);     
    
    cout << num << "! : " << result;   
    return 0;
}

피보나치(재귀)

int fibo(int n) {
   if(n == 0)
      return 0;
   else if(n == 1)
      return 1;
   else
      return fibo(n - 1) + fibo(n - 2);
}

Java Swap

public class Swap {
    public static void swap(int[] arr) {
        int temp = arr[0];
        arr[0] = arr[1];
        arr[1] = temp;
	}

    public static void main(String[] args) {
        int a = 10;
        int b = 20;
        int[] arr = {a, b};

        swap(arr);

        System.out.println(arr[0] + " " + arr[1]);
    }
}

c++ Swap

void swap(int *a, int *b){
	int tmp = *b;
	*b = *a;
	*a = tmp;
}

int main(){
	int a = 10;
    int b = 15;
    swap(&a, &b);
}