[c언어] 다양한 SORT 방법(insert / merge)

merge sort

 #include<stdio.h>
#include<stdlib.h>
void display(int* A, int n);
void merge(int A[], int p, int q, int r);
void mergeSort(int A[], int p, int r);
void copyArray(int *A, int *temp, int p, int r);
int main()
{
    int n;
    int *A;
    int i;
 
    printf("배열의 길이를 입력하세요:");
    scanf("%d", &n);
    A = (int*)malloc(sizeof(int) * n);
 
    for (i = 0; i < n; i++)
    {
        printf("%d번째 배열의 원소를 입력하세요:", i + 1);
 
        scanf("%d", &A[i]);
    }
 
    printf("정렬 전:\n");;
    display(A, n);
 
    mergeSort(A, 0, n - 1);
    printf("정렬 후:\n");
    display(A, n);
    free(A);
}
 
void mergeSort(int A[], int p, int r)
{
    int q;
 
    if (p == r) return;
 
    q = (p + r) / 2;
    mergeSort(A, p, q);
    mergeSort(A, q + 1, r);
    merge(A, p, q, r);
}
void merge(int A[], int p, int q, int r)
{
    int i = p, j = q + 1, k;
    int *temp = (int*)malloc(sizeof(int) * (r - p + 1));
 
    if (!temp) printf("메모리를 할당할 수 없습니다.");
    for (k = 0; k < r - p + 1; k++)
    {
        while (i > q)
        {
            if (j > r)
            {
                copyArray(A, temp, p, r);
                free(temp);
                return;
            }
            temp[k] = A[j];
            k++;
            j++;
 
        }
        while (j > r)
        {
            if (i > q)
            {
                copyArray(A, temp, p, r);
                free(temp);
                return;
            }
            temp[k] = A[i];
            k++;
            i++;
 
        }
 
        if (A[i] < A[j])
        {
            temp[k] = A[i];
            i++;
        }
        else
        {
            temp[k] = A[j];
            j++;
        }
 
    }
    copyArray(A, temp, p, r);
 
}
void display(int* A, int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}
 
void copyArray(int *A, int *temp, int p, int r)
{
    int i;
    int j = 0;
    for (i = p; i <= r; i++)
    {
        A[i] = temp[j];
        j++;
    }
}

 

 

insert sort

#include<stdio.h>
insertionSort(int *A, int n)
{
    int i, j, k, temp;
    for (i = 1; i < n; i++)
    {
        for (j = 0; j < i; j++) {
            if (A[j] > A[i]) break;//>:오름차순 <:내림차순
        }
 
       
        temp = A[i];//A[i]인지 A[j]인지 판단
        for (k = i; k > j; k--)
        {
            A[k] = A[k - 1];
 
        }
        A[j] = temp;
 
 
    }
}
void display(int* A, int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
 
    }
    printf("\n");
}
int main()
{
    int A[5] = { 3,5,4,2, 6 };
    printf("정렬 전:\n");
    display(A, 5);
    insertionSort(A, 5);
    printf("정렬 후:\n");
    display(A, 5);
}

 

quick sort

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void quickSort(struct Student s[], int p, int r);
int partition(struct Student s[], int p, int r);
void print_array(struct Student s[], int n);
void swqp(struct Student s[], int i, int j);
struct Student
{
 int id;
 int english;
 int math;
 int korean;
};

int main()
{
 struct Student* s;
 int n;
 int i;
 srand(time(NULL));
 printf("학생의 수를 입력하세요:");
 scanf("%d", &n);
 s = (struct Student*)malloc(sizeof(struct Student) * n);
 if (!s)
 {
  printf("메모리를 할당할 수 없습니다.");
  return 0;
 }
 for (i = 0; i < n; i++)
 {
  s[i].id = i + 1;
  s[i].english = rand() % 101;
  s[i].math = rand() % 101;
  s[i].korean = rand() % 101;
 }
 quickSort(s, 0, n-1);

}

void quickSort(struct Student s[], int p, int r)
{
 int q;
 if (p >= r) return;
 q = partition(s, p, r);
 quickSort(s, p, q - 1);
 quickSort(s, q + 1, r);

}
void swap(struct Student s[], int i, int j)
{
 struct Student temp;
 temp = s[i];
 s[i] = s[j];
 s[j] = temp;

}
int partition(struct Student s[], int p, int r)
{
 int i = -1, j = 0;
 while (p != r)
 {
  if (s[j].korean < s[r].korean)
  {
   swap(i + 1, j);
   i++;
   j++;
  }
  else
   j++;

 }
 swap(i + 1, r);
 return i + 1;
}

void print_array(struct Student s[], int n)
{
 int i;
 printf("        id     korean    english        math\n");
 for (i = 0; i < n; i++)
 {
  printf("%10d %10d %10d %10d", s[i].id, s[i].korean, s[i].english, s[i].math);
  printf("\n");
 }

}