Merge sort (Сортировка слиянием) - исправить ошибки в коде - C (СИ)
Формулировка задачи:
Privet dami i gospoda. Ne poluchaetsa realisovat' Merge sort. Proga kompiliruetsa no sorting ne rabotaet. Help please.
#include <stdio.h> #include <stdlib.h> #include <time.h> void merge(int *A, int p, int q, int r) { int i, j; int n1 = q - p + 1; int n2 = r - q; int *L, *R; L = (int *)malloc(sizeof(int) * n1); R = (int *)malloc(sizeof(int) * n1); for ( i = 0; i < n1; i++ ) { L[i] = A[p + i]; } for ( j = 0; i < n2; i++ ) { R[j] = A[q + 1 + j]; } int k; for ( k = p; k < r; k++ ) { if ( L[i] <= R[j] ) { A[k] = L[i]; i++; } else { A[k] = L[j]; j++; } } } void mergeSort(int *A, int p, int r) { int q; if ( p < r ) { q = ( p + r ) / 2; mergeSort(A, p, q); mergeSort(A, q + 1, r); merge(A, p, q, r); } } int main() { srand(time(NULL)); const int n = 8; int i; int *arr; arr = (int *)malloc(sizeof(int) * n); for ( i = 0; i < n; i++ ) { arr[i] = rand()%10 + 1; } for ( i = 0; i < n; i++ ) { printf("%d ", arr[i]); } printf("\n"); mergeSort(arr, 0, n - 1); for ( i = 0; i < n; i++ ) { printf("%d ", arr[i]); } return 0; }
Решение задачи: «Merge sort (Сортировка слиянием) - исправить ошибки в коде»
textual
Листинг программы
#include <stdio.h> #include <iostream> using namespace std; //Слияние void merge(int *a, int *b, int low, int pivot, int high) { int h, i, j, k; h = low; i = low; j = pivot + 1; while ((h <= pivot) && (j <= high)) { if (a[h] <= a[j]) { b[i] = a[h]; h++; } else { b[i] = a[j]; j++; } i++; } if (h > pivot) { for (k = j; k <= high; k++) { b[i] = a[k]; i++; } } else { for (k = h; k <= pivot; k++) { b[i] = a[k]; i++; } } for (k = low; k <= high; k++) a[k] = b[k]; } //Сортировка слиянием void mergesort(int *a, int*b, int low, int high) { int pivot; if (low < high) { pivot = (low + high) / 2; mergesort(a, b, low, pivot); mergesort(a, b, pivot + 1, high); merge(a, b, low, pivot, high); } } int main() { //Инициализируем массивы размерностью n int n = 8; int *a = new int[n]; int *b = new int[n]; //Записываем рандомные числа в массив А и заодно выводим в консоль for (int i = 0; i < n; i++) { a[i] = rand() % 10 + 1; cout << a[i] << " "; } cout << endl; //Сортируем mergesort(a, b, 0, n - 1); //Выводим на экран отсортированный массив А for (int i = 0; i < n; i++) cout << a[i] << " "; cout << endl; system("pause"); return 0; }
Объяснение кода листинга программы
- В функции
merge
происходит слияние двух отсортированных половин массива в один отсортированный массив. - В функции
mergesort
происходит рекурсивная сортировка массива с помощью функцииmerge
. - Если размер массива больше 1, то массив разбивается на две равные части, каждая из которых сортируется отдельно, затем происходит их слияние в отсортированный массив.
- В функции
main
создаются два указателя на массивы размером 8, в которые записываются случайные числа от 1 до 10, затем вызывается функция сортировкиmergesort
для сортировки массиваa
. - После сортировки выводится на экран отсортированный массив
a
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д