Chương trình C để sắp xếp một mảng bằng cách sử dụng sắp xếp hợp nhất

Mảng là một nhóm các mục dữ liệu có liên quan có chung một tên chung. Một giá trị cụ thể trong một mảng được xác định với sự trợ giúp của "số chỉ mục" của nó.

Khai báo mảng

Cú pháp khai báo một mảng như sau -

datatype array_name [size];

Ví dụ:

float marks [50]

Nó khai báo 'mark' là một mảng chứa 50 phần tử float.

int number[10]

Nó khai báo ‘number’ là một mảng để chứa tối đa 10 hằng số nguyên.

Mỗi phần tử được xác định bằng cách sử dụng "chỉ mục mảng".

Dễ dàng truy cập các phần tử mảng bằng cách sử dụng chỉ mục mảng.

Logic chúng tôi sử dụng để sắp xếp hợp nhất như sau -

void MergeSort(int *array, int left, int right){
   int middle = (left+right)/2;
   if(left<right){
      //Sorting the left part
      MergeSort(array, left, middle);
      //Sorting the right part
      MergeSort(array, middle + 1, right);
      // Merge the two parts
      Merge(array, left, middle, right);
   }
}

Logic để hợp nhất tất cả các phần tử như sau -

void Merge(int *array, int left, int middle, int right){
   int tmp[right - left + 1];
   int pos = 0, leftposition = left, rightposition = middle + 1;
   while (leftposition <= middle && rightposition <= right){
      if (array[leftposition] < array[rightposition]){
         tmp[pos++] = array[leftposition++];
      }else{
         tmp[pos++] = array[rightposition++];
      }
   }
   while (leftposition <= middle)
      tmp[pos++] = array[leftposition++];
   while (rightposition <= right)
      tmp[pos++] = array[rightposition++];
   int i;
   for (i = 0; i < pos; i++){
      array[i + left] = tmp[i];
   }
   return;
}

Chương trình

Sau đây là chương trình C để hợp nhất sắp xếp -

#include <stdio.h>
void Merge(int * , int , int , int );
void MergeSort(int *array, int left, int right){
   int middle = (left+right)/2;
   if(left<right){
      //Sorting the left part
      MergeSort(array, left, middle);
      //Sorting the right part
      MergeSort(array, middle + 1, right);
      // Merge the two parts
      Merge(array, left, middle, right);
   }
}
void Merge(int *array, int left, int middle, int right){
   int tmp[right - left + 1];
   int pos = 0, leftposition = left, rightposition = middle + 1;
   while (leftposition <= middle && rightposition <= right){
      if (array[leftposition] < array[rightposition]){
         tmp[pos++] = array[leftposition++];
      }
      else{
         tmp[pos++] = array[rightposition++];
      }
   }
   while (leftposition <= middle)
      tmp[pos++] = array[leftposition++];
   while (rightposition <= right)
      tmp[pos++] = array[rightposition++];
   int i;
   for (i = 0; i < pos; i++){
      array[i + left] = tmp[i];
   }
   return;
}
int main(){
   int size;
   printf("\n enter size of array:");
   scanf("%d", &size);
   int array[size];
   int i, j, k;
   printf("\n enter the elements in an array:");
   for (i = 0; i < size; i++){
      scanf("%d", &array[i]);
   }
   MergeSort(array, 0, size - 1);//calling sort function
   for (i = 0; i< size; i++){
      printf("%d ", array[i]);
   }
   printf("\n");
   return 0;
}

Đầu ra

Khi chương trình trên được thực thi, nó tạo ra kết quả sau -

enter size of array:10
enter the elements in an array:
2
-10
34
-3
45
67
-89
34
23
67
-89 -10 -3 2 23 34 34 45 67 67