본문 바로가기
웹_프론트_백엔드/C언어

[자료구조] 2020.07.31

shine94 2020. 8. 2. 14:31

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;
}

'웹_프론트_백엔드 > C언어' 카테고리의 다른 글

[자료구조] 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

'웹_프론트_백엔드/C언어' Related Articles

티스토리툴바