코영방

동빈나의 머지소트

#include <bits/stdc++.h>
using namespace std;

int number = 8;
int sorted[8]; //정렬 배열은 받드시 전역 배열

void merge(int a[], int m, int middle, int n){ //m : 시작점, middle : 중간점, n : 끝점

    int i = m;
    int j = middle+1;
    int k = m;

    //작은 순서대로 배열에 삽입
    while(i <= middle && j <= n){
        if(a[i] <= a[j]){
            sorted[k] = a[i];
            i++;
        }
        else{
            sorted[k] = a[j];
            j++;
        }
        k++;
    }
    if(i > middle){
        for(int t = j; t<=n; t++){
            sorted[k] = a[t];
            k++;
        }
    }
    else{
        for(int t=i; t<=middle; t++){
            sorted[k] = a[t];
            k++;
        }
    }

    //sorted 에서 a배열로 옮겨준다
    for(int t=m; t<=n; t++){
        a[t] = sorted[t];
    }
}

void mergesort(int a[], int m, int n){
    //크기가 1보다 큰 경우
    if(m < n){
        int middle = (m+n)/2;
        mergesort(a, m, middle);
        mergesort(a, middle+1, n);
        merge(a,m, middle, n);
    }
}

int main()
{
    int array[8] = {7,6,5,8,3,5,9,1};
    mergesort(array, 0, number-1);
    for(int t=0; t<number; t++){
        printf("%d ", array[t]);
    }
    return 0;
}

동빈나의 머지소트

#include <bits/stdc++.h>
using namespace std;

int number = 8;
int sorted[8]; //정렬 배열은 받드시 전역 배열

void merge(int a[], int m, int middle, int n){ //m : 시작점, middle : 중간점, n : 끝점

    int i = m;
    int j = middle+1;
    int k = m;

    //작은 순서대로 배열에 삽입
    while(i <= middle && j <= n){
        if(a[i] <= a[j]){
            sorted[k] = a[i];
            i++;
        }
        else{
            sorted[k] = a[j];
            j++;
        }
        k++;
    }
    if(i > middle){
        for(int t = j; t<=n; t++){
            sorted[k] = a[t];
            k++;
        }
    }
    else{
        for(int t=i; t<=middle; t++){
            sorted[k] = a[t];
            k++;
        }
    }

    //sorted 에서 a배열로 옮겨준다
    for(int t=m; t<=n; t++){
        a[t] = sorted[t];
    }
}

void mergesort(int a[], int m, int n){
    //크기가 1보다 큰 경우
    if(m < n){
        int middle = (m+n)/2;
        mergesort(a, m, middle);
        mergesort(a, middle+1, n);
        merge(a,m, middle, n);
    }
}

int main()
{
    int array[8] = {7,6,5,8,3,5,9,1};
    mergesort(array, 0, number-1);
    for(int t=0; t<number; t++){
        printf("%d ", array[t]);
    }
    return 0;
}

www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=216&sca=10c0

선택 정렬 사용해서 풀기,

가장 작은 값을 찾아서, 제일 오른쪽 끝으로 옮기는 방식으로 해결

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 자가진단 1
*/

void f(int a[], int n){ //int *b
    //내림차순

    int min;
    for(int i=0;i<n;i++)
    {
        min = 99;
        int min_idx = 0;
        for(int j=0;j<n-i;j++){
          if(min>a[j]){
            min=a[j];
            min_idx = j;
          }
        }
        int temp= a[min_idx];
        a[min_idx] = a[n-i-1];
        a[n-i-1] = temp;
    }
}

int main()
{
    int a[10];
    int n;
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    f(a, n);  //배열의 이름은 배열의 시작 주소다.ㅁ

    for(int i=0;i<n;i++){
        printf("%d ", a[i]);
    }

    return 0;
}

위 코드에서  swap() 함수를 사용한 것으로 개선

https://en.cppreference.com/w/cpp/algorithm/swap

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 자가진단1
*/

void f(int a[], int n){ //int *b
    //내림차순

    int min;
    for(int i=0;i<n;i++)
    {
        min = 99;
        int min_idx = 0;
        for(int j=0;j<n-i;j++){
          if(min>a[j]){
            min=a[j];
            min_idx = j;
          }
        }
        /*
        int temp= a[min_idx];
        a[min_idx] = a[n-i-1];
        a[n-i-1] = temp;
        */
        swap(a[min_idx], a[n-i-1]);

    }
}

int main()
{
    int a[10];
    int n;
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    f(a, n);  //배열의 이름은 배열의 시작 주소다.ㅁ

    for(int i=0;i<n;i++){
        printf("%d ", a[i]);
    }

    return 0;
}

선택 정렬 사용해서 풀기 2,

가장 큰 값을 찾아서, 제일 왼쪽 끝으로 옮기는 방식으로 해결

#include <bits/stdc++.h>
using namespace std;
/*
함수2 - 자가진단1
*/

void f(int a[], int n){ //int *b
    //내림차순

    int max;
    for(int i=0;i<n;i++)
    {
        max = -1000;
        int max_idx = 0;
        for(int j=i;j<n;j++){
          if(max<a[j]){
            max=a[j];
            max_idx = j;
          }
        }
        /*
        int temp= a[min_idx];
        a[min_idx] = a[n-i-1];
        a[n-i-1] = temp;
        */
        swap(a[max_idx], a[i]);

    }
}

int main()
{
    int a[10];
    int n;
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    f(a, n);  //배열의 이름은 배열의 시작 주소다.ㅁ

    for(int i=0;i<n;i++){
        printf("%d ", a[i]);
    }

    return 0;
}