1. 정렬
: 버블정렬, 삽입정렬, 선택정렬, 퀵정렬
1) 버블정렬
: 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식
2) 삽입정렬
: 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식
3) 선택정렬
: 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식
4) 퀵정렬
: 순환함수 이용
Divide & Conquer(분할정복)
피벗(== 피봇, pivot, 기준)
피벗보다 작으면 왼쪽으로, 비벗보다 크면 오른쪽으로
[3] 5l 7 9 1 10 6 2r 8 4
[3] 2 7l 9 1r 10 6 5 8 4
[3] 2 1r 9l 7 10 6 5 8 4 -> 교차(cross) : 비벗과 r 위치를 교환
1 2 [3] 9 7 10 6 5 8 4 -> 비벗 데이터 기준으로 오른쪽 왼쪽 퀵 정렬을 한다
-> [1] 2
-> [9] 7 10 6 5 8 4
요소가 1개일때까지 순환 호출
2. 버블정렬
#include<stdio.h>
#include<stdlib.h>
void bubble_sort(int* arr, int n) {
for (int a = 0; a < n; a++) {
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
}
}
// 정렬하는 과정 보여주기
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
}
int main() {
int n;
printf("몇 개의 배열을 만들지 숫자를 입력 : ");
scanf("%d", &n);
int* arr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("정렬전 : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 버블 정렬 실행
bubble_sort(arr, n);
printf("정렬후 : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
3. 삽입정렬
#include<stdio.h>
#include<stdlib.h>
void insertion_sort(int* arr, int n) {
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] < arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 정렬하는 과정 보여주기
for (int a = 0; a < n; a++) {
printf("%d ", arr[a]);
}
printf("\n");
}
}
int main() {
int n;
printf("몇 개의 배열을 만들지 숫자를 입력 : ");
scanf("%d", &n);
int* arr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("정렬전 : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 삽입 정렬 실행
insertion_sort(arr, n);
printf("정렬후 : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
4. 선택정렬
#include<stdio.h>
#include<stdlib.h>
void selection_sort(int *arr, int n) {
for (int i = 0; i < n; i++) {
int min = arr[i];
int minIndex = i;
for (int j = i; j < n; j++) {
if (min > arr[j]) {
min = arr[j];
minIndex = j;
}
}
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
// 정렬하는 과정 보여주기
for (int a = 0; a < n; a++) {
printf("%d ", arr[a]);
}
printf("\n");
}
}
int main() {
int n;
printf("몇 개의 배열을 만들지 숫자를 입력 : ");
scanf("%d", &n);
int* arr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("정렬전 : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 선택 정렬 실행
selection_sort(arr, n);
printf("정렬후 : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
5. 퀵 정렬
#include<stdio.h>
#include<stdlib.h>
void swap(int* arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
void quick_sort(int *arr, int start, int end) {
int pivot = arr[start];
int l = start + 1;
int r = end;
while (l <= r) {
while (arr[l] < pivot) {
l++;
}
while (arr[r] > pivot) {
r--;
}
if (l <= r) {
swap(arr, l, r);
}
}
if (start < end) { // 요소가 1개가될때까지
swap(arr, start, r);
quick_sort(arr, start, r - 1);
quick_sort(arr, r + 1, end);
}
}
int main() {
int n;
printf("몇 개의 배열을 만들지 숫자를 입력 : ");
scanf("%d", &n);
int* arr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("정렬전 : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 퀵 정렬 실행
quick_sort(arr, 0, n - 1);
printf("정렬후 : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
6. [문제] 숫자 맞추기 게임
1) 1 ~ 100까지 랜덤으로 숫자 10개 생성
2) 배열에 넣고 출력
3) 오름차순정렬하고 출력 => 알고리즘 사용
4) 0 ~ 9 중에 랜덤으로 선택, 해당 숫자를 맞춰보자!
예시)
[ 1 3 17 18 19 ]
[2]->17
3<= X <=18
15
16<= X <=18
N번 소요됨!
** 내코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
// 1. 랜덤으로 숫자 10개 생성
int number[10];
srand(time(NULL));
for (int i = 0; i < 10; i++) {
// 2. 배열에 넣고 출력
number[i] = rand() % 100 + 1;
printf("%d ", number[i]);
}
printf("\n");
// 3. 오름차순 정렬하고 출력 -> 알고리즘 사용
for (int i = 0; i < 10; i++) {
for (int i = 0; i < 10 - 1; i++) {
if (number[i] > number[i + 1]) {
int temp = number[i];
number[i] = number[i + 1];
number[i + 1] = number[i];
}
}
}
for (int i = 0; i < 10; i++) {
printf("%d ", number[i]);
}
printf("\n");
// 4. 0 ~ 9 중에 랜덤으로 선택, 해당 숫자를 맞춰보기
int n = rand() % 9 + 1;
printf("%d를 맞추는 게임..!!\n", number[n]);
int cnt = 0;
while (1) {
cnt++;
int num;
printf("숫자를 입력 : ");
scanf("%d", &num);
if (num == number[n]) {
printf("\n정답입니다!!\n당신은 %d번 만에 정답을 맞췄습니다.\n\n", cnt);
break;
}
}
return 0;
}
** 강사님 코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int* arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
void quick_sort(int* arr, int start, int end) {
int pivot = arr[start];
int l = start + 1;
int r = end;
while (l <= r) {
while (arr[l] < pivot) {
l++;
}
while (arr[r] > pivot) {
r--;
}
if (l <= r) {
swap(arr, l, r);
}
}
if (start < end) {
swap(arr, start, r);
quick_sort(arr, start, r - 1);
quick_sort(arr, r + 1, end);
}
}
int main() {
srand(time(NULL));
int arr[10];
for (int i = 0; i < 10; i++) {
arr[i] = rand() % 100 + 1;
}
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
printf("\n");
quick_sort(arr, 0, 9);
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
printf("\n");
int index = rand() % 10;
printf("[%d] -> %d를 맞추자!\n", index, arr[index]);
int start = index == 0 ? 1 : arr[index - 1];
int end = index == 9 ? 100 : arr[index + 1];
while (1) {
printf("%d ~ %d : ", start, end);
int n;
scanf("%d", &n);
if (start > n || n > end) {
printf("[올바르게 입력하세요!]\n");
continue;
}
if (n == arr[index]) {
break;
}
else if (arr[index] > n) {
start = n + 1;
}
else {
end = n - 1;
}
}
return 0;
}'웹_프론트_백엔드 > 단과' 카테고리의 다른 글
| [단과_자료구조] 2020.08.05 (0) | 2020.08.10 |
|---|---|
| [단과_자료구조] 2020.08.03 (0) | 2020.08.10 |
| [단과_자료구조] 2020.07.29 (0) | 2020.07.29 |
| [단과_자료구조] 2020.07.27 (0) | 2020.07.27 |
| [단과_자료구조] 2020.07.22 (0) | 2020.07.22 |