Sort , Search

1. 선택 정렬 (Selection Sort)

2. 삽입 정렬(Insertion Sort)

3. 버블 정렬(Bubble Sort)

4. 병합 정렬(Merge Sort)

5. 퀵 정렬(Quick Sort) - 참조 블로그=> http://mygumi.tistory.com/308

6. 이분 탐색(Binary Search) 재귀/비재귀

#include<stdio.h>
void swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
 
void print(int *arr)
{
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
 
 
    puts("");
}
void insertion_sort(int *arr)
{
    for (int i = 1; i < 10; i++) {
        int k = i;
        int j = i - 1;
        while (j >= 0 && arr[k] < arr[j]) {
            swap(&arr[k], &arr[j]);
            k = j;
            j--;
        }
        
    }
 
    print(arr);
 
}
 
void selection_sort(int *arr)    //시간 O(n^2) 공간 O(n)
{
    for (int i = 0; i < 10; i++) {
        int k = i;
        for (int j = i+1; j < 10; j++) {
            if (arr[k] > arr[j]) k = j;
        }
        swap(&arr[k], &arr[i]);
    }
 
 
    print(arr);
}
void bubble_sort(int *arr)
{
    for (int i = 0; i < 10; i++) {
        for (int j = 1; j < 10-i; j++) {
            if (arr[j - 1] > arr[j]) swap(&arr[j - 1], &arr[j]);
        }
    }
 
    print(arr);
}
void merge(int *arr,int s,int e)
{
    int m = (s + e) / 2;
    int i = s, j = m+1;
    int k = 0;
    int tmp_arr[10];
 
    while (i <= m && j <= e){
        if (arr[i] < arr[j]) {
            tmp_arr[k++] = arr[i++];
            continue;
        }
 
        if (arr[j] < arr[i]) {
            tmp_arr[k++] = arr[j++];
            continue;
        }
 
    }
 
    while (i <= m){
        tmp_arr[k++] = arr[i++];
    }
 
    while (j <= e) {
        tmp_arr[k++] = arr[j++];
    }
 
    for (int t = s; t <= e; t++)
    {
        arr[t] = tmp_arr[t - s];
    }
}
void merge_sort(int *arr,int s,int e)
{
    if (s < e) {
        int m = (s + e) / 2;
 
        merge_sort(arr, s, m);
        merge_sort(arr, m + 1, e);
        merge(arr, s, e);
    }
}
 
void quick_sort(int *arr,int s,int e)
{    
    if (s < e) {
        int left = s, right = e, pivot = arr[left];
 
        while (left < right) {
 
            while (arr[right] > pivot) {
                right--;
            }
 
            while (arr[left] <= pivot && left < right) {
                left++;
            }
 
            swap(&arr[left], &arr[right]);
        }
 
        swap(&arr[s], &arr[right]);
 
        quick_sort(arr, s, right - 1);
        quick_sort(arr, right + 1, e);
    }
}
void binary_search(int *arr, int find,int left,int right)
{
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (arr[mid] > find) {
            right = mid - 1;
        }
        else if (arr[mid] < find) {
            left = mid + 1;
        }
        else {
            printf("index is %d\n", mid);
            break;
        }
    }
}
 
void recursive_binary_search(int *arr,int find,int left,int right)
{
    if (left > right) {
        return ;
    }
 
    int mid = (left + right) / 2;
 
    if (arr[mid] > find) {
        recursive_binary_search(arr, find, left, mid - 1);
    }
    else if (arr[mid] < find) {
        recursive_binary_search(arr, find, mid + 1, right);
    }
    else {
        printf("index is %d\n", mid);
        return;
    }
}
int main(void)
{
    int arr[10] = { 10,3,8,4,1,9,2,5,7,6 };
    insertion_sort(arr);
 
    int arr2[10] = { 10,3,8,4,1,9,2,5,7,6 };
    selection_sort(arr2);
 
    int arr3[10]= { 10,3,8,4,1,9,2,5,7,6 };
    bubble_sort(arr3);
    
    int arr4[10] = { 10,3,8,4,1,9,2,5,7,6 };
    merge_sort(arr4,0,9);
    print(arr4);
 
    int arr5[10] = { 10,3,8,4,1,9,2,5,7,6 };
    quick_sort(arr5,0,9);
    print(arr5);
 
    binary_search(arr5, 10, 0, 9);
 
    recursive_binary_search(arr5, 10, 0, 9);
    return 0;
}

< Sorting Class 설계 >

#include<iostream>
#include<vector>
using namespace std;
 
class SORT {
private:
    int N;
    vector<int> arr;
public:
    SORT() {};
    ~SORT() {};
    void input();
    int getArraySize();
    void swap(int x, int y);
    void selection_sort();
    void insertion_sort();
    void bubble_sort();
    void quick_sort(int s,int e);
    void merge(int s, int e);
    void merge_sort(int s,int e);
    void print();
 
};
 
void SORT::input()
{
    cout << "입력받을 수의 개수 입력:";
    cin >> N;
    cout << N << "개 숫자 입력" << endl;
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
}
void SORT::swap(int x,int y)
{
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}
 
int SORT::getArraySize()
{
    return N-1;
}
void SORT::quick_sort(int s,int e)
{
    if (s < e)
    {
        int l = s;
        int r = e;
        int pivot = arr[s];
 
        while (l < r)
        {
            while (arr[r] > pivot)
                r--;
 
            while (arr[l] <= pivot && l<r)
                l++;
 
            swap(l, r);
        }
 
        swap(s, r);
        quick_sort(s, r - 1);
        quick_sort(r + 1, e);
    }
 
}
 
void SORT::merge(int s, int e)
{
    vector<int> tmp(N);
    int k = 0;
    int l = s;
    int mid = (s + e) / 2 ;
    int r = mid + 1;
 
    while (l <= mid && r <= e)
    {
        if (arr[l] <= arr[r])
            tmp[k++] = arr[l++];
 
        if (arr[l] > arr[r])
            tmp[k++] = arr[r++];
    }
 
    while (l <= mid)
    {
        tmp[k++] = arr[l++];
    }
 
    while (r <= e)
    {
        tmp[k++] = arr[r++];
    }
 
    for (int i = s; i <=e ; i++)
    {
        arr[i] = tmp[i - s];
    }
 
 
 
}
void SORT::merge_sort(int s, int e)
{
    if (s < e)
    {
        int mid = (s + e) / 2;
 
        merge_sort(s, mid);
        merge_sort(mid+1, e);
        merge(s, e);
    }
}
void SORT::bubble_sort()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < N - i; j++)
        {
            if (arr[j - 1] > arr[j])
                swap(j - 1, j);
        }
    }
}
void SORT::insertion_sort()
{
    for (int i = 1; i < N; i++)
    {
        int j = i - 1;
        int k = i;
        while (j >= 0 && arr[j] > arr[k])
        {
            swap(j, k);
            j--;
            k--;
        }
    }
}
void SORT::selection_sort()
{
    for (int i = 0; i < N; i++)
    {
        int smallest = i;
 
        for (int j = i + 1; j < N; j++)
        {
            if (arr[j] < arr[smallest])
                smallest = j;
        }
 
        swap(i, smallest);
    }
}
void SORT::print()
{
    for (int i = 0; i < N; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
int main()
{
    while (true) 
    {
        SORT sort_;
        sort_.input();
        sort_.insertion_sort();
        sort_.print();
    }
 
 
    return 0;
}