버블정렬, 삽입정렬

오 뻐큐 갓뎀

다이나믹이니 dfs니 뭐니 그런거 한다고 깝치다가 더 기본적인걸 무시하고 있었군

기본중의 기본인 버블정렬, 삽입정렬도 제대로 구현못하다니 짱난다

일단 버블소트

for(int i=0; i<10; i++) for(int j=0; j<10-i; j++) //매번 첫번째 원소부터 시작해서 비교하는데 //한번 돌고나면 배열의 끝에는 가장 큰수가 있으므로 비교횟수가 1번씩 줄어든다 if(a[j] > a[j+1]) //앞에놈이 뒤에꺼보다 크면 바꿔 swap(a[j], a[j+1]); 그리고 삽입정렬

for(int i=1; i<10; i++){ //비교하는 배열이 두개, 세개... 늘어남 if( a[i] < a[i-1] ){ //그전거는 다 정렬되어있으니 앞에놈이랑만 비교해보면돼 int j=i; while( a[i] <= a[j] ) //자기보다 작은놈 나올때까지 인덱스 줄임 j--; j++; //내가 원하는 인덱스보다 하나 더 줄었으니 증가해주고 int tmp = a[i]; memmove(&a[j+1], &a[j], sizeof(a[0])*(i-j)); //쭉 땡겨주고 a[j] = tmp; //빈자리에 삽입 } } 저기있는 memmove는 string.h에 포함되어있고, 이름그대로 메모리를 이동시킨다

첫번째 인자는 새로 옮길주소, 두번째는 원본데이터의 주소, 세번째는 이동시킬 데이터의 양이다

a[0]가 4byte니까 4*(i-j) 바이트만큼 옮겨준다

memmove는 처음본다 쩝

버블이나 삽입이나 둘다 시간복잡도는 O(n^2)이라서 둘다 병신인데

버블은 정렬된 상태에서도 비교를 하나하나 다하지만

삽입은 정렬된 상태이면 비교를 안하니까 좋단다