Написать программу, в которой реализуются различные методы сортировки массивов

@LoneProphet · Регистрация: 08.10.2016

Здравствуйте! Да, тема сортировка массивов, но не всё так просто. Получил такое задание:
Написать программу, в которой реализуются различные методы сортировки (для одинаковых массивов случайных чисел в диапазоне от 0 до 100).
Сравнить реализованные методы по быстродействию. Провести исследование быстродействия для различного числа элементов в массиве (n=1000, 3000, 9000, 27000, 81000). Результаты исследования отразить в отчете в виде таблицы и графика зависимости (t/n) от n.
Каждый из методов сортировки, а также генерацию массива, необходимо реализовать в виде отдельной функции. Глобальных переменных не использовать!
Для оценки быстродействия можно использовать функцию clock() из библиотеки <time.h>, возвращающую число тактов процессора, прошедшее с момента запуска приложения. Возвращаемые значения функции clock() следует присваивать переменной типа unsigned long.
Виды сортировок:BubbleSort,HeapSort,Radix.
Я сделал всё для Bubble Sort и всё работает, но я неправильно создал массив, т.е. его нужно через функцию и глобальные переменные не использовать. Покажите как или объясните, пожалуйста.
Вот код:

C++

#include <stdio.h>
#include <cstdlib> 
#include <iostream>
#include <iomanip>
#include <ctime>
#include <time.h>
using namespace std;
 
void bubbleSort(int *, int); // прототип функции сортировки пузырьком
 
int main(int argc, char* argv[])
{ 
system("mode con cols=150 lines=120"); 
system("pause » void"); 
    {  
    int t = clock();
    srand(time(NULL));
    cout << "Input 1001, 3001, 9001, 27001 or 81001, please:";
    int size_array;
    cin >> size_array;
 
    int *sorted_array = new int [size_array];
    for (int counter = 0; counter < size_array; counter++)
    {
        sorted_array[counter] = rand() % 101; // заполняем массив случайными числами
        cout << setw(2) << sorted_array[counter] << "  "; // вывод массива на экран
    }
    cout << "\n\n";
 
    bubbleSort(sorted_array, size_array); // вызов функции сортировки пузырьком
 
    for (int counter = 0; counter < size_array; counter++)
    {
        cout << setw(2) << sorted_array[counter] << "  "; // печать отсортированного массива
    }
    cout << '\t';
    cout << "CPU cycles: " << t << "; Done parsing in " << ((float)t) / CLOCKS_PER_SEC << " seconds.";
    system("pause");
    return 0;
    }
}
 
void bubbleSort(int* arrayPtr, int length_array) // сортировка пузырьком
{
 int temp = 0; // временная переменная для хранения элемента массива
 bool exit = false; // болевая переменная для выхода из цикла, если массив отсортирован
 
 while (!exit) // пока массив не отсортирован
 {
  exit = true;
  for (int int_counter = 0; int_counter < (length_array - 1); int_counter++)
    if (arrayPtr[int_counter] > arrayPtr[int_counter + 1])
    {
     temp = arrayPtr[int_counter];
     arrayPtr[int_counter] = arrayPtr[int_counter + 1];
     arrayPtr[int_counter + 1] = temp;
     exit = false;
    }
 }
}

@amaralikyr · 03.12.2016, 14:32

Глобальные переменные объявляются за пределами функции, у вас таких я не заметил.

Добавлено через 6 минут

C++

#include <iostream>
#include <ctime>
using namespace std;
 
void arrGen(int* arr, int N)
{ 
    for (int i = 0; i < N; i++)
        arr[i] = rand() % 101;
}
 
int main() 
{   
    int N = 5;
    int* arr = new int[N];
    
    arrGen(arr, N);
 
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
 
}

самое банальное что можно было придумать)

@LoneProphet · 03.12.2016, 20:16 **[ТС]**

Спасибо. А как это отсортировать и вывести пусть без оценки быстродействия

Добавлено через 44 минуты

Сообщение от LoneProphet

Спасибо. А как это отсортировать и вывести пусть без оценки быстродействия

Сделал. Осталось разобраться с остальными сортировками
Вот код на будущее, для других:

C++

#include <iostream>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <stdio.h>
#include <cstdlib> 
using namespace std;
 
void bubbleSort(int *, int);
 
void arrGen(int* arr, int N)
{ 
    for (int i = 0; i < N; i++)
        arr[i] = rand() % 101;
}
 
int main() 
{   
    int t = clock();
    int N = 1001;
    int* arr = new int[N];
    
    arrGen(arr, N);
 
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
cout << "\n\n";
 
bubbleSort(arr, N);
 
    for (int i = 0; i < N; i++)
    {
        cout << setw(1) << arr[i] << "  ";
    }
    cout << '\t';
cout << "\n\n";
    cout << "CPU cycles: " << t << "; Done parsing in " << ((float)t) / CLOCKS_PER_SEC << " seconds.";
    system("pause");
    return 0;
    }
    void bubbleSort(int* arr, int N)
{
 int temp = 0;
 bool exit = false;
 
 while (!exit)
 {
  exit = true;
  for (int i = 0; i < (N - 1); i++)
    if (arr[i] > arr[i + 1])
    {
     temp = arr[i];
     arr[i] = arr[i + 1];
     arr[i + 1] = temp;
     exit = false; 
    }
 }
}

Опции темы