저번 게시물에 이어서 이번에는 문자 배열을 정렬하는 것을 알아보겠습니다.
두 가지 함수가 쓰이는데요.
바로 strcmp와 strcpy 함수입니다.
함수 사용을 위해선 코드 제일 상단에 #include <string.h>를 포함해줘야 합니다.
1. 문자 배열 정렬
먼저 어떤 함수들이 사용되는지 확인하고 갑시다
1) strcmp(문자 1, 문자 2) : 아스키코드를 기준으로 문자의 선후를 비교해 줍니다.
// 반환값
-1 : 문자 2가 클 때
0 : 문자가 같을 때
+1: 문자 1이 클 때
2) strcpy(문자 1, 문자 2) : 문자 1과 문자 2의 위치를 바꾼다.
문자 배열을 정렬하는 예시를 보겠습니다.
앞에서 했던 선택 정렬과 똑같은데 문자열에 관한 함수를 쓴다는 것만 다릅니다.
EX)
1. i = 배열의 첫 번째 값
2. for(배열 크기만큼 반복)
3. min = i
4. 배열의 첫 번째 값보다 큰 값이 나오면 (strcpy) 그 값을 min의 배열 값과 바꿈 (strcmp)
6. 2번으로 돌아감
2. Bubble sort
해당 정렬의 개념은 바로 옆의 값과 비교해서 크기에 따라 자리를 바꿔주는 겁니다.
내 옆자리 사람이 나보다 키가 작으면 그 사람과 나의 자리를 바꿔주는 거죠.
목표는 선택하기에 따라 다르지만 일단 제일 작은 값이 맨 앞에 오는 것을 목표로 하겠습니다.
EX)
1. for 1(배열의 크기 -1만큼 반복) : 밑에 있는 for문에서 +1이 되기 때문에 -1을 해줘야 함
2. for 2(위 for 1에서 줄어드는 인자 크기만큼 반복)
3. for 2에 해당하는 인자의 배열 값과 그 인자 +1의 배열 값의 크기 비교
4. 그 인자 +1이 더 작으면 두 배열 값의 위치 교환
5. 2번으로 돌아감
6. for 2가 끝나면 1번으로 돌아감
1~5까지 번호를 붙인 사람들이 있다면, 1번과 2번이 비교하고 -> 2번과 3번이 비교하고 쭉쭉쭉 해나가는 것입니다.
다음번엔 1~4번까지 다시 비교를 반복해 주고
마지막으로 1~2번까지 다시 비교를 해주면 완성됩니다.
3. Quick sort
가장 빠르고 효율적인 정렬방법이라고 합니다.
Pivot이라는 기준 값을 가지고 배열의 좌측 끝에서부터 pivot까지, 우측 끝에서부터 pivot까지 비교를 하며 pivot보다 작거나 큰 값의 위치를 '서로' 바꿔 주는 것입니다.
1). 2 / 3 / 4 / 8 / 6 / 0 / 1 / 5 / 9 이런 배열이 있다고 합시다.
저는 가운데 숫자인 6을 pivot으로 삼겠습니다.
(가장 효율적인 pivot 선정법은 가운데 값으로 하는 거라고 합니다.)
2) 2 / 3 / 4 / 8 / '6' / 0 / 1 / 5 / 9
-> <- 이런 식으로 하나씩 pivot과 크기 비교를 해줄 거예요
왼쪽에선 8만 6보다 크고, 오른쪽에선 다른 값도 있지만 5가 먼저 6보다 작네요
(오름차순 정렬이기 때문에 왼쪽은 pivot보다 작게, 오른쪽은 pivot 보다 크게 정렬하기 위해서입니다.)
3) 그럼 왼쪽에 있는 8과 오른쪽에 있는 5가 서로 자리를 바꾸게 됩니니다.
2 / 3 / 4 / 5 / '6' / 0 / 1 / 8 / 9 이렇게 되겠네요
일단 한번 정렬이 되긴 됐네요.
4) 다음은 pivot을 기준으로 왼쪽과 오른쪽을 다시 한번 같은 과정을 반복해 줍니다.
2 / 3 / 4 / 5와 0 / 1 / 8 / 9를 각자 pivot을 만들고 동일한 과정을 해주는 거죠.
여기서 배열의 크기가 짝수니까 중간값이 따로 없기 때문에 알아서 pivot을 정해주면 됩니다.
만약 pivot = (배열의 시작 인덱스 + 끝 인덱스) / 2 이라면 배열의 원소가 4개일 때 (0 + 3) / 2 = 1.5 이고 정수형을 반환하면 인덱스 1의 배열값이 pivot으로 설정되겠네요.
알고리즘도 위의 예시와 동일합니다.
구현은 아래 코드를 참조해 주세요.
4. SWAP
SWAP 함수는 여러 형태가 있겠지만, 가장 단순하게 사용하는 방법을 알려드리겠습니다.
목적은 두 변수에 저장되어 있는 값을 교환해 주는 겁니다.
#define SWAP(x, y, temp) ((temp)=(x), (x)=(y), (y)=(temp)) 이렇게 선언해 주고,
SWAP(list[low], list[high], temp); 이렇게 사용하시면 됩니다.
위의 Quick sort에서 low 인덱스를 가진 배열값과 high 인덱스를 가진 배열값의 위치를 교환해 주는 데 사용됩니다.
코드 예제입니다.
제가 중간중간 삽입한 주석처리 된 출력 함수 (printf)를 주석 제거 하시면 더 자세한 출력 결과를 보실 수 있습니다.
공통 사항
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
EX) 문자열 정렬 - 선택 정렬 개념을 사용합니다.
#define MAX 10
#define MIN 5
#define NUM 9
void selectionSortWords(char (*words)[MAX], int num_words);
int main(void){
char words[NUM][MAX] =
{"111", "333", "222", "444", "666", "555", "777", "888", "999"};
for(int i = 0; i < NUM; i++){
printf("words[%d] = %s\n", i, words[i]);
}
selectionSortWords(words, NUM);
printf("*************** %d Words after sorting : \n", NUM);
for(int i = 0; i < NUM; i++){
printf("words[%d] = %s\n", i, words[i]);
}
printf("\n");
return 0;
}
void selectionSortWords(char (*words)[MAX], int numwords){
int min;
char temp[MAX];
for(int i = 0; i < NUM; i++){
min = i;
for(int j = i+1; j < NUM; j++){
if(strcmp(words[min], words[j]) > 0){// 0을 기준으로 크고 작음이 반환된다. >0 이면 큼
min = j;
}
}
if (min != i){
strcpy(temp, words[min]); // 배열의 위치를 바꿔준다.
strcpy(words[min], words[i]);
strcpy(words[i], temp);
}
}
}
EX) Bubble sort
void bubbleSort(char (*word)[20], int len){
char temp[20];
for(int i = len-1; i >0; i--){// 비교 횟수 맨 뒤부터 정렬되니까 비교할 수는 점점 줄어야 함
for(int t = 0; t < i; t++){
int check = strcmp(word[t],word[t+1]); // 옆의 수와 비교
if(check>0){ //
strcpy(temp, word[t]); // temp에다 t 넣기
strcpy(word[t],word[t+1]); // t에다 t+1 넣기
strcpy(word[t+1],temp); // t+1에다 t(temp) 넣기
}
}
}
}
int main(void){
char word[5][20] = {"strawberry","apple","cat","brown","book"};
int len= sizeof(word)/sizeof(word[0]);
// int len = sizeof(word[10]);
// printf("%d\n", len);
for(int i = 0; i < len; i++){
printf("%s\n", word[i]);
}
bubbleSort(word,len);
printf("*************** %d Words after sorting : \n", 5);
for(int i = 0; i < len; i++){
printf("%s\n", word[i]);
}
return 0;
}
EX) Quick sort
#define SWAP(x, y, temp) ((temp)=(x), (x)=(y), (y)=(temp))
#define MAX_SIZE 9
int partition(int *list, int left, int right){
int pivot, temp;
int low, high;
while(1){
low = left;
high = right;
pivot = (left+right)/2;
// do while 은 무조건 한 번은 실행됨
// printf("pivot = %d\n", pivot);
while(list[low] < list[pivot] && low <= pivot){
// printf("low = %d\n", low);
low++;
}
while(list[high] > list[pivot] && high >= pivot){
// printf("high = %d\n", high);
high--;
}
// printf("high = %d, low = %d\n", high, low);
if(low < pivot || high > pivot){
SWAP(list[low], list[high], temp);
// printf("SWAP function is going to start.\n");
for(int i = 0; i < MAX_SIZE; i++){
// printf("%d\n", list[i]);
}
}
else if(low == pivot && high == pivot){
break;
}
}
return pivot;
}
void QuickSort(int *list, int left, int right){ // list[] 와 *list는 동일한 결과를 보인다.
if(left < right){
int Q = partition(list, left, right);
QuickSort(list, left, Q-1);
QuickSort(list, Q+1, right);
}
}
int main(void){
// int i;
const int n = MAX_SIZE; // const 뭔지 찾아보자
int list[n] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
for(int i = 0; i < n; i++){
printf("list[%d] = %d\n", i, list[i]);
}
// partition(list, 0, n-1);
QuickSort(list, 0, n-1);
printf("QuickSort has been finised.\n");
for(int i = 0; i < n; i++){
printf("list[%d] = %d\n", i, list[i]);
}
return 0;
}
'Programming > C' 카테고리의 다른 글
| [자료구조 C 언어] C 프로그래밍 기초 - 6 : 2차원 배열, 포인터 배열, 배열 포인터 (2) | 2020.02.24 |
|---|---|
| [자료구조 C 언어] C 프로그래밍 기초 - 5 : 포인터 뿌시기 (Pointer) (1) | 2020.02.23 |
| [자료구조 C 언어] C 프로그래밍 기초 - 3 : 순차탐색 (Sequential search), 이진탐색 (Binary search) (0) | 2020.02.22 |
| [자료구조 C 언어] C 프로그래밍 기초 - 1 : 개요 (0) | 2020.02.20 |
| [자료구조 C 언어] C 프로그래밍 기초 - 2 : 조건문, 반복문 (0) | 2020.02.20 |