#문자수만큼 오른쪽으로 한바퀴 회전하여 출력하는 프로그램
한 글자를 임시 변수에 저장해두고 제쳐둔다음, 나머지 글자를 하나씩 밀어주기(=회전시키기)
여기서 중요한건.. tmp라는 변수에 문자를 저장하는 것임.
//문자수만큼 오른쪽으로 한바퀴 회전하여 출력하는 프로그램 //길이 구하는 함수 int whatLen(char* snt) { int len = 0; for (int i = 0; snt[i] != '\0'; i++) //표현 기억해두기. len++; return len; } void move(char* snt, char tmp) { int len = whatLen(snt); for (int i = 0; i < len; i++) { /*임시변수 tmp에 가장 끝 글자 저장하고, 끝에서부터 한칸씩 밀어준다. * 마지막으로 가장 첫번째에 임시tmp에 저장해둔 끝 글자 넣어주면 됨. */ tmp = snt[len - 1]; for (int k = len - 1; k >= 0; k--) { snt[k] = snt[k - 1]; } snt[0] = tmp; for (int i = 0; i < len; i++) printf("%c", *(snt + i)); printf("\n"); } } int main(void){ char snt[100]; char tmp = ' '; scanf("%s", snt); move(snt, tmp); }
#2 버블정렬
크기가 N인 배열에 대한 버블정렬 의사코드
bubble_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
for last <- N downto 2
for i <- 1 to last - 1
if (A[i] > A[i + 1]) then A[i] <-> A[i + 1] # 원소 교환
}
<1> 개선되기 전 코드. 알고리즘 시간이 많이 소요된다.
T(n) = (n-1)*(n-1)*C
T(n) = C(n^2 - 2n + 1) = O(n^2)
void bubble_sort(int *arr) { for (int k = 1; k < sizeof(arr); k++) { for (int i = 0; i < sizeof(arr)-1; i++) { if (arr[i] > arr[i + 1]) SWAP(arr[i], arr[i + 1]); } } } int main(void) { int num; printf("배열의 크기 입력: "); scanf("%d", &num); int* arr; arr= (int*)malloc(sizeof(int) * num); for (int i = 0; i < num; i++) scanf("%d", arr + i); bubble_sort(arr); for (int i = 0; i < num; i++) printf("%d ", *(arr + i)); free(arr); }
<2> flag 변수 사용해서 불필요한 반복 줄이기.
Best case : C*(n-1) = O(n)
*총 비교 단계 : 항목개수 - 1
void bubble_sort(int* arr, int num) { int flag; int count = 0; for (int k = 1; k < num; k++) { flag = 1; for (int i = 0; i < num - k; i++) { count++; if (arr[i] > arr[i + 1]) { flag = 0; SWAP(arr[i], arr[i + 1]); } } if (flag == 1) break; } printf("%d\n", count); }
각 단계의 시작 부분에서 1로 설정, 비교 작업을 계속 하다가 교환이 발생할 시에 flag 값을 0으로 만든다.
이렇게하면 특정 단계의 비교작업이 완료되었을 때 flag 값이 0이면 교환 작업이 최소한 한번은 이루어졌다는 뜻이고 flag 값이 1이면 교환 작업이 없었다는 뜻이기 때문에 정렬이 완료되었다는 뜻입니다.
blog에서 퍼온 내용이다.
버블 정렬 특성상 계속해서 비교를 해야되기 때문에 불필요한 작업이 많이 필요하다.
더 이상 교환이 발생하지 않는다는건 정렬 작업이 완료되었다는 뜻이므로 flag를 사용하면 보다 빠르고 효율적으로 알고리즘을 구사할 수 있는 것이다.
비교 횟수를 알아보기 위해서 count 변수를 사용했다.
ex) arr = {1, 3, 6, 4, 2} 1번 코드 count = 16 / 2번 코드 count = 10
비교 횟수를 계속 누적시켰더니 확실히 후자가 횟수가 적다. 이렇게 같은 알고리즘이여도 비교 횟수가 확연히 차이난다. 불필요한 부분을 어떻게 제거할지, 어떻게하면 더 간결하고 깔끔하게 구현할 수 있을지 고민해보자..
'Major > Data Structure & Algorithm' 카테고리의 다른 글
연결리스트 노드 개수 카운팅,특정 노드 순서 바꾸기,첫번째 노드 삭제하기 ... (0) | 2022.04.03 |
---|---|
[JAVA] 연결리스트, 노드, 삽입 및 삭제 (0) | 2022.04.03 |
[python+]연결리스트,노드,삽입,삭제 (0) | 2022.04.02 |
배열 순차 자료구조, 선형 리스트, 다항식의 순차 자료구조 (0) | 2022.03.20 |
[2월 18일] Selection Sort Algorithm 삽입정렬, Insertion Sort Algorithm 삽입정렬 (0) | 2022.02.18 |