어서와 C언어는 처음이지 제23장.

Presentation on theme: "어서와 C언어는 처음이지 제23장."— Presentation transcript:

1 어서와 C언어는 처음이지 제23장

2 정렬 정렬(sorting)은 값들을 크기 순으로 나열하는 연산

3 버블 정렬 값을 정렬하는 데는 많은 방법들이 있지만 이번 장에서는 버블 정렬(bubble sort)이라고 하는 방법
버블 정렬은 다른 정렬 방법에 비해서 특별히 빠르지는 않지만 이해하기는 쉽다. 데이터를 정렬하는 매 단계마다 가장 작은 값이 물속의 공기방울처럼 리스트의 맨 위로 올라오게 된다.

4

5 // 완전 초보자 가이드 3판 22장 예제 #2 // 파일 Chapter22ex2.c /* 이 프로그램은 10개의 난수를 생성하여 정렬한다. */ #include <stdio.h> #include <stdlib.h> #include <time.h> main() { int ctr, inner, outer, didSwap, temp; int nums[10]; time_t t; // 이 문장을 포함시키지 않으면 항상 동일한 난수가 생성된다. srand(time(&t)); // 첫 번째 단계는 배열을 1부터 100 사이의 난수로 채우는 것이다. for (ctr = 0; ctr < 10; ctr++) nums[ctr] = (rand() % 99) + 1; }

6 // 정렬하기 전의 배열을 출력한다. puts("\n정렬 전의 리스트:"); for (ctr = 0; ctr < 10; ctr++) { printf("%d\n", nums[ctr]); } // 배열을 정렬한다. for (outer = 0; outer < 9; outer++) didSwap = 0; //리스트가 아직 정렬되지 않았으면 1(true) for (inner = outer; inner < 10; inner++) if (nums[inner] < nums[outer]) temp = nums[inner]; nums[inner] = nums[outer]; nums[outer] = temp; didSwap = 1; if (didSwap == 0) break;

7 // 정렬 후의 리스트를 출력한다. puts("\n정렬 후의 리스트:"); for (ctr = 0; ctr < 10; ctr++) { printf("%d\n", nums[ctr]); } return(0);

8 실행 결과 정렬 전의 리스트: 72 1 48 97 54 75 67 93 61 11 정렬 후의 리스트:

9 변수의 값을 교환 올바른 코드 temp = nums[inner]; nums[inner] = nums[outer];
nums[outer] = temp; 잘못된 코드 nums[inner] = nums[outer]; /* 2개의 값이 교환되지 않는다. */ nums[outer] = nums[inner];

10 빨라진 탐색 정렬은 데이터 탐색 속도도 빠르게 한다. 178 313 422 532 562 902
아이디 413을 탐색한다고 하면

11 예제: 신용 카드 프로그램 고객 아이디 값들은 먼저 정렬되고, 사용자는 탐색할 고객 아이디를 입력한다. 그리고 프로그램은 고객의 카드 사용액이 $100보다 작은지를 검사하게 된다.

12 // 완전 초보자 가이드 3판 23장 예제 #2 // 파일 Chapter23ex2.c /* 이 프로그램은 카드 사용액를 확인하기 위하여 고객 아이디의 정렬된 리스트를 탐색한다. */ #include <stdio.h> main() { int ctr; // 루프 카운터 int idSearch; // 탐색할 고객(키) int found = 0; // 고객이 발견되면 1(true) /* 각 평행 배열에 10개의 요소를 정의한다. */ int custID[10] = { 313, 453, 502, 101, 892, 475, 792, 912, 343, 633 }; float custBal[10] = { 0.00, 45.43, 71.23, , 9.08, 192.41, , , 18.31, }; int tempID, inner, outer, didSwap, i; // 정렬을 위하여 필요하다. float tempBal;

13 // 먼저 고객 아이디로 배열을 정렬한다. */ for (outer = 0; outer < 9; outer++) { didSwap = 0; // 리스트가 아직 정렬되지 않았으면 1(true) for (inner = outer; inner < 10; inner++) if (custID[inner] < custID[outer]) tempID = custID[inner]; // 배열 요소 교환 tempBal = custBal[inner]; custID[inner] = custID[outer]; custBal[inner] = custBal[outer]; custID[outer] = tempID; custBal[outer] = tempBal; didSwap = 1; // 교환이 발생하였음(true) } if (didSwap == 0) break;

14 /* 카드 사용액을 찾는 사용자와 상호작용한다. */
printf("\n\n*** 고객 사용잔액 탐색 ***\n"); printf("고객의 아이디는? "); scanf(" %d", &idSearch); // 배열에서 아이디를 찾는다. for (ctr = 0; ctr<10; ctr++) { if (idSearch == custID[ctr]) // 일치하는지 검사 found = 1; //일치하면 플래그를 TRUE로 한다. break; //일치하지 않으면 계속 탐색 } if (custID[ctr] > idSearch) // 계속 탐색할 필요 없음 break;

15 // 반복 루프가 종료되면 아이디가 발견되거나
// (found = 1) 아니면 발견되지 않은 것이다. if (found) { if (custBal[ctr] > 100) printf("\n** 고객의 카드 사용액은 $%.2f.\n", custBal[ctr]); printf("더 이상의 지출은 불가능합니다. \n"); } else // 사용잔액이 $ 이하 printf("\n**더 지출할 수 있습니다!\n"); else // 아이디가 발견되지 않았다. printf("** 잘못된 사용자 ID입니다. "); printf("\n ID %3d은 발견되지 않았습니다. \n", idSearch); return(0);

16 Lab: 단어 정렬 크기가 10인 1차원 배열에 0부터 99 사이의 난수를 저장한 후에, 최대값과 최소값을 출력하는 프로그램을 작성하시오. 난수는 rand() 함수를 호출하여 생성하라. 단어의 개수를 입력하시오(최대 100개): 3 단어 0: dog 단어 1: cat 단어 2: butterfly 정렬된 단어는 다음과 같다. butterfly cat dog

17 strcmp() strcmp(s1, s2)

18 #include <stdio.h>
#include <string.h> int main(void) { char name[100][30], temp[8]; int i, j, n; printf("단어의 개수를 입력하시오(최대 100개): "); scanf("%d", &n); for (i = 0; i < n; i++) printf("단어 %d: ", i); scanf("%s", name[i]); }

19 for (i = 0; i < n - 1; i++) { for (j = i + 1; j < n; j++) if (strcmp(name[i], name[j]) > 0) strcpy(temp, name[i]); strcpy(name[i], name[j]); strcpy(name[j], temp); } printf("\n \n"); printf("정렬된 단어는 다음과 같다.\n"); printf(" \n"); for (i = 0; i < n; i++) printf("%s\n", name[i]); return 0;

20 학습 정리 배열을 낮은 값에서 높은 값으로 정렬하려면 오름차순 정렬을 사용한다.
배열을 높은 값에서 낮은 값으로 정렬하려면 내림차순 정렬을 사용한다. 버블 정렬을 수행하기 위한 문장 구조는 중첩 for 루프이다. 2개의 변수값을 서로 교환하려면 제3의 변수가 반드시 필요하다. 정렬 루틴은 어려울 필요가 없다. 이번 장에서 제시된 루틴으로 시작해서 여러분들이 필요한 대로 수정하라. 배열을 정렬 상태로 두는 것을 잊지 말자. 배열은 일단 정렬되면 빠르게 탐색할 수 있다.

21 Q & A