자료구조 QuickSort

/*
1. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값이 오른편에 위치시킵니다.
2. 기준 요소 오니편에는 기준 요소보다 작은 요소들이 모여있고 오른편에는 큰 요소들이 모여있습니다.
이렇게 나눈 데이터 집합들을 다시 1에서와 같이 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할합니다.
3. 1과 2의 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게됩니다. */

//방법1. swap함수 만들어 사용하기

#include <stdio.h>

void swap(int *x, int *y) {
        int temp = *x;
        *x = *y;
        *y = temp;
}

int Partition(int DataSet[], int Left, int Right) {
        int First = Left;
        int Pivot = DataSet[First];

        ++Left;

        while (Left<=Right) {
                while (DataSet[Left]<=Pivot && Left<Right)
                ++Left;
                while (DataSet[Right]>Pivot && Left<=Right)
                --Right;

                if (Left< Right)
                        swap(&DataSet[Left], &DataSet[Right]);
                else break;
        }
        swap(&DataSet[Right], &DataSet[First]);
        return Right;
}

void QuickSort(int DataSet[], int Left, int Right) {
        if (Left< Right) {
                int index = Partition(DataSet, Left, Right);

                //재귀 2번 (왼쪽 파티션에 대한 재귀, 오른쪾 파티션에 대한 재귀)
                QuickSort(DataSet, Left, index - 1);
                QuickSort(DataSet, index + 1, Right);
        }
}

void sort(int DataSet[], int l, int r) {
        int left = l;
        int right = r;
        int pivot = DataSet[(l + r) / 2];

        do {
                while (DataSet[left] < pivot) left++;
                while (DataSet[right] > pivot) right--;
                if (left <= right) {
                        swap(&DataSet[left], &DataSet[right]);
                        left++;
                        right--;
                }
        } while (left <= right);

        if (l < right) sort(DataSet, l, right);
        if (r < left) sort(DataSet, left, r);
}

void main() {
        int DataSet[] = { 6,4,2,3,1,5 };
        int Length = sizeof(DataSet) / sizeof(int);
        QuickSort(DataSet, 0, Length - 1);
        for (int i = 0; i < Length; i++)
                printf("%d", DataSet[i]);
        printf("\n");
}

=========================================================================
//방법2. 라이브러리의 qsort함수 이용하기

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
void qsort(
        void *base, : 데이터 집합 배열의 주소
        size_t num, : 데이터 요소의 개수
        size_t width : 한 데이터 요소의 크기
        int(_cdecl *compare)(const void *, const void *)
        비교함수에 대한 포인터
)
int compare((void *)&elem1, (void *)& elem2);
*/
/*
return 값이
<0 : _elem1이 _elem2보다 작다.
0 : 같다
>0 : _elem1이 _elem2보다 크다.
*/

int CompareScore(const void*_elem1, const void*_elem2) {
        int* elem1 = (int *)_elem1;
        int* elem2 = (int *)_elem2;

        if (*elem1 > *elem2) return 1;
        else if (*elem1 < *elem2) return -1;
        else return 0;
}

void main() {
        int DataSet[] = { 6,4,2,3,1,5 };
        int Length = sizeof(DataSet) / sizeof(int);
        qsort((void*)DataSet, Length, sizeof(int), CompareScore);

        for (int i = 0; i < Length; i++)
                printf("%d", DataSet[i]);
        printf("\n");
}
=========================================================================
//출력

자료구조 InsertionSort

/*
1. 데이터 집합에서 대상이 되는 요소들을 선택한다.
이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 증가할 때 마다 1개씩 커집니다.
정렬대상의 최대 범위는 (크기-1)

2. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 잇는지 확인합니다.
그렇지 않다면 이 요소를 적절한 곳을 정렬대상 내에서 찾습니다.
적절한 곳은 데이터집합 가장 왼쪽부터 했을 때 자신보다 더 작은 요소가 없는 위치입니다.

3. 뽑아 든 요소를 삽입할 적절한 곳을 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를
한 자리씩 오른쪽으로 이동시키고, 새로 생긴 빈자리에 삽입합니다.

memmove(주소, 넣을 값의 주소, 크기)
*/

#include <stdio.h>
#include <string.h>

void InsertionSort(int DataSet[], int Length) {
        for (int i = 1; i < Length; i++) {
                if (DataSet[i] > DataSet[i - 1]) continue;
                int value = DataSet[i];
                for (int j = 0; j < i; j++) {
                        if (DataSet[i] == DataSet[j]) {
                                memmove(&DataSet[j + 1], &DataSet[j], sizeof(int));
                                DataSet[j] = value;
                                break;
                        }
                }
        }
}

void main() {
        int DataSet[] = { 6,4,2,3,1,5 };
        int Length= sizeof(DataSet) / sizeof(int);
        InsertionSort(DataSet, Length- 1);
        for (int i = 0; i < Length; i++)
                printf("%d", DataSet[i]);
        printf("\n");
}

07.18 C++ 복습 - 배열

#include <iostream>
using namespace std;
void main() {
        /*
        int num1;
        int num2;
        int num3;
        //배열 :  똑같은 자료형을 나열시켜놓은 묶음

        //자료형 변수name[개수];
        //3개의 숫자를 나열 시키는 변수

        int arr[3];
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
        printf("%p %p %p \n", &num1, &num2, &num3);
        printf("%p %p %p \n", &arr[0], &arr[1], &arr[2]);
        cout << arr[0] << " , " << arr[1] << " , " << arr[2] << endl;
        */

===============================================================================
 
        //문자를 담을 배열변수 10개 생성 후 0~9번째 인덱스까지 A~J를 차례대로 대입 후 출력
        const int SIZE = 10;
        char a[SIZE];
        char k = 65;

        for (int i = 0; i < 10 ; i++) {
                a[i] = k;
                k++;
        }
        for (int j = 0; j < SIZE; j++) {
                cout << j << "는 " << a[j] << endl;
        }

===============================================================================

        //배열의 개수 구하기
        int arr[] = { 1,2,3,4,5 };
        cout << sizeof(arr)/sizeof(int) << endl;

        char arr[] = { 'A', 'B', 'C' };
        cout << sizeof(arr);
       
===============================================================================

        int j = 0;
        int arr[] = { 1,2,3,4,5 }; //1,2,3,4,5 넣음
        j = arr[sizeof(arr)/sizeof(int )-1];
        for (int i = 4; i > 0; i--) {
                arr[i] = arr[i-1];
        } arr[0] = j;
        for (int k = 0; k < 5; k++) {
                cout << arr[k] << endl;
        }

===============================================================================
        //답안
        const int SIZE = 100;
        int arr2[SIZE], k =0;
        int arr1[] = { 1,2,3};
        int index = 0;
        k = sizeof(arr1) / sizeof(int);
        for (int i = 0; i < k + k; i++) {
                arr2[i] = arr1[index];
                if (i < k-1) {
                        index++;
                }
                else if(i>=k){
                        index--;
                }

         cout << arr2[i] << " ";
 }

===============================================================================
        //오류나는 내 답안
const int SIZE = 100;
 int arr2[SIZE], k =0;
 int arr1[] = { 1,2,3, 4 };
 k = sizeof(arr1) / sizeof(int);
 for (int i = 0; i < k; i++) {
  arr2[i] = arr1[i];
  cout << arr2[i] << " ";
 }
 for (int j = k; j < k + k; j++) {
  for (int m = k; m >= j; m--) {
   arr2[j] = arr1[m];
  }
  cout << arr2[j] << " ";
 }

===============================================================================
//20개의 랜덤값 10개의 배열에 중복되지 않게 넣고 선택정렬하기
        const int SIZE = 10;
        int arr[SIZE];
        srand(time(NULL));
        for (int i = 0; i < SIZE; i++) {
                arr[i] = rand() % 20 + 1;
                for (int j = 0; j < i; j++) {
                        if (arr[i] == arr[j]) {
                                i--;
                                break;
                        }
                }
        }
        int min;
        for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
                min = i;
                for (int k = i + 1; k < sizeof(arr) / sizeof(int); k++) {
                        if (arr[min] > arr[k]) min = k;       
                }
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
        }
        for(int j = 0; j <sizeof(arr)/sizeof(int); j++){
                cout << arr[j] << " "; 
        }
}

Bubble Sort

#include <stdio.h>

void BubbleSort(int DataSet[], int Length){
        for (int i = 0; i < Length - 1; i++) {
                for (int j = 0; j < Length - (i+1); j++) {
                        if (DataSet[j] > DataSet[j + 1]) {
                                int temp = DataSet[j];
                                DataSet[j] = DataSet[j + 1];
                                DataSet[j + 1] = temp;
                        }
                }
        }
}

void main() {
        int DataSet[] = { 6,4,2,3,1,5 };
        int Length = sizeof(DataSet) / sizeof(int);
        BubbleSort(DataSet, Length);
        for (int i = 0; i < Length; i++)
                printf("%d", DataSet[i]);
        printf("\n");
}

피보나치 수열 ( Fibonacci )

#include <stdio.h>

int fibonacci(int n) {
        if (n < 1) return 0;
        if (n < 3) return 1;
  return fibonacci(n-2) + fibonacci(n - 1);
}

void main() {
        for (int i = 0; i < 50; i++)
printf("%2d : %3d\n", i, fibonacci(i));
}

하노이 타워 ( Hanoi Tower )

#include <stdio.h>
#include <stdlib.h>

void HanoiTower(int n, char x, char y, char z) {
        if(n==1)
                printf("%c -> %c\n", x, y);
        else {
                HanoiTower(n - 1, x, z, y);
                printf("%c -> %c\n", x, y);
                HanoiTower(n - 1, z, y, x);
        }
}

void main() {
        HanoiTower(3, 'A', 'B', 'C');
}

==============================================================================
//출력

자료구조 분리집합 DisjointSet

//disJointSet.h 헤더파일 만들기

#pragma once
#ifndef DISJOINTSET_H
#define DISJOINTSET_H

#include <stdio.h>
#include <stdlib.h>

//분리집합 : 교집합을 갖지 않는 집합들
typedef struct tagDisjointSet {
        struct tagDisjointSet * Parent;
        void* Data;
}DisjointSet;

void UnionSet(DisjointSet* Set1, DisjointSet* Set2);
DisjointSet* FindSet(DisjointSet* Set);
DisjointSet* MakeSet(void* NewData);
void DestroySet(DisjointSet* Set);

#endif

=============================================================================

#include "disjointSet.h"

void UnionSet(DisjointSet* Set1, DisjointSet* Set2) {
        Set2 = FindSet(Set2);
        Set2 -> Parent = Set1;
}

DisjointSet* FindSet(DisjointSet* Set) {
        while (Set->Parent != NULL)
                Set = Set->Parent;
        return Set;
}

DisjointSet* MakeSet(void* NewData) {
        DisjointSet* NewSet = (DisjointSet*)malloc(sizeof(DisjointSet));
        NewSet->Data = NewData;
        NewSet->Parent = NULL;

        return NewSet;
}

void DestroySet(DisjointSet* Set){
}

void main() {
        int a = 1, b = 2, c = 3, d = 4;
        DisjointSet* Set1 = MakeSet(&a);
        DisjointSet* Set2 = MakeSet(&b);
        DisjointSet* Set3 = MakeSet(&c);
        DisjointSet* Set4 = MakeSet(&d);

        printf("Set1 == Set2 : %d\n", FindSet(Set1) == FindSet(Set2));

        UnionSet(Set1, Set3);
        printf("Set1 == Set3 : %d\n", FindSet(Set1) == FindSet(Set3));

        UnionSet(Set3, Set4);
        printf("Set3 == Set4 : %d\n", FindSet(Set3) == FindSet(Set4));
}