Предмет: Информатика, автор: mikrob4928

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

Ответы

Автор ответа: wantwedead
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).

Объяснение:


mikrob4928: спасибо, очень помогли
Похожие вопросы