Question

C++ Нужно придумать два массива натуральных чисел (первый – близки по значению и с повторениями, второй – далеки и без повторений). Построить 3 алгоритма на C++: быстрый, средний и медленный. Выполнить сортировку придуманных двух массивов тремя методами

Answer 1

Ответ:Первый массив (близкие значения с повторениями): {1, 2, 1, 3, 2} Второй массив (далекие значения без повторений): {10, 20, 30, 40}

Вот примеры трех алгоритмов сортировки на C++:

Быстрый алгоритм - быстрая сортировка (QuickSort):

void quickSort(int arr[], int low, int high) {

   if (low < high) {

       int pi = partition(arr, low, high);

       quickSort(arr, low, pi - 1);

       quickSort(arr, pi + 1, high);

   }

}

int partition (int arr[], int low, int high) {

   int pivot = arr[high];

   int i = (low - 1);

   for (int j = low; j <= high- 1; j++) {

       if (arr[j] <= pivot) {

           i++;

           swap(&arr[i], &arr[j]);

       }

   }

   swap(&arr[i + 1], &arr[high]);

   return (i + 1);

}

void swap(int* a, int* b) {

   int t = *a;

   *a = *b;

   *b = t;

}

Средний алгоритм - сортировка вставками (Insertion Sort):

void insertionSort(int arr[], int n) {

  for (int i = 1; i < n; i++) {

      int key = arr[i];

      int j = i-1;

      while (j >=0 && arr[j] > key) {

          arr[j+1] = arr[j];

          j--;

      }

      arr[j+1] = key;

  }

}

Медленный алгоритм - сортировка пузырьком (Bubble Sort):

void bubbleSort(int arr[], int n) {

  for (int i=0; i<n-1; i++)      

      for (int j=0; j<n-i-1; j++)

          if (arr[j] > arr[j+1])

             swap(&arr[j], &arr[j+1]);

}

Продолжение примера использования алгоритмов сортировки для придуманных массивов:

int main() {

  // Первый массив

  int firstArray[] = {1, 2, 1, 3, 2};

  int n = sizeof(firstArray)/sizeof(firstArray[0]);

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

  quickSort(firstArray, 0, n-1);

  insertionSort(firstArray, n);

  bubbleSort(firstArray, n);

  // Второй массив

  int secondArray[] = {10, 20, 30, 40};

  int m = sizeof(secondArray)/sizeof(secondArray[0]);

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

  quickSort(secondArray, 0, m-1);

  insertionSort(secondArray,m);

  bubbleSort(secondArray,m);

   return 0;

}

В этом примере оба массива сортируются тремя разными методами: быстрой сортировкой (QuickSort), сортировкой вставками (Insertion Sort) и сортировкой пузырьком (Bubble Sort).

Объяснение:

Answer 2

Вот примеры трех алгоритмов сортировки и применение их к двум придуманным массивам: один массив будет содержать близкие числа с повторениями, а другой массив будет содержать удаленные числа без повторений.

1. Быстрый алгоритм сортировки (Quick Sort):

cppCopy code
#include <iostream>

// Рекурсивная функция быстрой сортировки
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }

        std::swap(arr[i + 1], arr[high]);

        int partitionIndex = i + 1;

        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}

int main() {
    // Первый массив: близкие числа с повторениями
    int arr1[] = {4, 2, 7, 5, 2, 8, 4};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);

    // Применение быстрой сортировки к первому массиву
    quickSort(arr1, 0, size1 - 1);

    // Вывод отсортированного первого массива
    std::cout << "Отсортированный первый массив: ";
    for (int i = 0; i < size1; i++) {
        std::cout << arr1[i] << " ";
    }
    std::cout << std::endl;

    // Второй массив: удаленные числа без повторений
    int arr2[] = {9, 1, 6, 3, 10};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);

    // Применение быстрой сортировки ко второму массиву
    quickSort(arr2, 0, size2 - 1);

    // Вывод отсортированного второго массива
    std::cout << "Отсортированный второй массив: ";
    for (int i = 0; i < size2; i++) {
        std::cout << arr2[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

2. Средний алгоритм сортировки (Merge Sort):

cppCopy code
#include <iostream>

// Слияние двух подмассивов
void merge(int arr[], int low, int mid, int high) {
    int i, j, k;
    int n1 = mid - low + 1;
    int n2 = high - mid;

    // Создание временных подмассивов
    int L[n1], R[n2];

    // Копирование данных во временные подмассивы L[] и R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[low + i];
    for (j = 0; j < n2; j++)
        R[j