C/C++ Сортировка двумерного массива

Сортировка двумерных массивов - одна из задач, которую приходится решать в программировании. В языках программирования С и С++ есть несколько способов сортировки двумерных массивов. Рассмотрим несколько из них.

Сортировка двумерного массива методом пузырька

Метод пузырька - один из самых простых алгоритмов сортировки, который можно использовать для сортировки двумерных массивов. Суть алгоритма заключается в том, что мы проходим по массиву несколько раз и каждый раз перемещаем наибольшее число в конец массива. В итоге мы получаем отсортированный массив.

void bubbleSort(int arr[][2], int n) {
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n - i - 1; j++) {
         if (arr[j][0] > arr[j + 1][0]) {
            swap(arr[j][0], arr[j + 1][0]);
            swap(arr[j][1], arr[j + 1][1]);
         }
      }
   }
}

Сортировка двумерного массива методом слияния

Метод слияния - это алгоритм, который разбивает массив на части, затем сортирует каждую из них и объединяет вместе. Этот алгоритм более эффективен, чем метод пузырька, и работает за O(n log n).

void merge(int arr[][2], int mid, int low, int high){
    int i,j,k;
    int n1=mid-low+1;
    int n2=high-mid;
    int left[n1][2],right[n2][2];
    for(i=0;i<n1;i++){
        left[i][0]=arr[low+i][0];
        left[i][1]=arr[low+i][1];
    }
    for(i=0;i<n2;i++){
        right[i][0]=arr[mid+1+i][0];
        right[i][1]=arr[mid+1+i][1];
    }
    i=0;
    j=0;
    k=low;
    while(i<n1&&j<n2){
        if(left[i][0]<=right[j][0]){
            arr[k][0]=left[i][0];
            arr[k][1]=left[i][1];
            i++;
        }
        else{
            arr[k][0]=right[j][0];
            arr[k][1]=right[j][1];
            j++;
        }
        k++;
    }
    while(i<n1){
        arr[k][0]=left[i][0];
        arr[k][1]=left[i][1];
        i++;
        k++;
    }
    while(j<n2){
        arr[k][0]=right[j][0];
        arr[k][1]=right[j][1];
        j++;
        k++;
    }
}
void mergeSort(int arr[][2], int low, int high){
    if(low<high){
        int mid=(low+high)/2;
        mergeSort(arr,low,mid);
        mergeSort(arr,mid+1,high);
        merge(arr,mid,low,high);
    }
}

Заключение

В этой статье мы рассмотрели два метода сортировки двумерных массивов - метод пузырька и метод слияния. Существует множество других алгоритмов сортировки, которые могут также использоваться для сортировки двумерных массивов в С и С++. Однако, эти два метода - надежные и широко используемые во многих приложениях программирования.