Member Avatar for Amnah AL-Abdi

hello.....

iam new memeber,and may be my quistion is easy to ask it,but really i need to help me in my problem.

we know that the size of any array must be determined befor the running time,since it static location, my quistion is:

if i need to make aprogramme in c++ languge,that generate an array in eacg time with random size.......

for example :

at first the size of the array is 500,then 1000,then1500,then2000,then 2500,......,5000

i want if you can to sent to me a c++ programme that doing that.

the poupes of this problem:

my instructor ask me to write a c++ programme that compute the time that each of the sorting algorithms (insertion,selection,merge,heap,quick) in each time with diffrent size of

  • 3 Contributors
  • 2 Replies
  • 99 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by ithelp

Dani AI

Generated

: a repeatable test harness is the right way to measure sorting costs across sizes (500, 1000, ..., 5000). pointed toward dynamic containers; the snippet below uses a single master random array per size and copies it before each algorithm so every sort sees identical input. : this will let you post concrete numbers if you need feedback.

Use this skeleton: replace the placeholder wrappers with your actual implementations of insertion, selection, merge, heap and quick sort (placeholders call std::sort so the program compiles). The harness runs several trials and prints CSV: algorithm,size,average_microseconds.

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <functional>
#include <string>
#include <cassert>

void insertion_sort(std::vector<int>& v) { std::sort(v.begin(), v.end()); /* replace */ }
void selection_sort(std::vector<int>& v) { std::sort(v.begin(), v.end()); /* replace */ }
void merge_sort(std::vector<int>& v)     { std::sort(v.begin(), v.end()); /* replace */ }
void heap_sort(std::vector<int>& v)      { std::sort(v.begin(), v.end()); /* replace */ }
void quick_sort(std::vector<int>& v)     { std::sort(v.begin(), v.end()); /* replace */ }

int main() {
    std::vector<int> sizes = {500,1000,1500,2000,2500,3000,3500,4000,4500,5000};
    std::mt19937 rng(std::random_device{}());
    std::uniform_int_distribution<int> dist(0, 1000000);
    const int runs = 5;
    std::vector<std::pair<std::string, std::function<void(std::vector<int>&)>>> sorts = {
        {"insertion", insertion_sort}, {"selection", selection_sort},
        {"merge", merge_sort}, {"heap", heap_sort}, {"quick", quick_sort}
    };
    std::cout << "algorithm,size,avg_us\n";
    for (int n : sizes) {
        std::vector<int> master; master.reserve(n);
        for (int i=0;i<n;++i) master.push_back(dist(rng));
        for (auto &p : sorts) {
            long long total = 0;
            for (int r=0;r<runs;++r) {
                auto data = master;
                auto t0 = std::chrono::high_resolution_clock::now();
                p.second(data);
                auto t1 = std::chrono::high_resolution_clock::now();
                total += std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
                assert(std::is_sorted(data.begin(), data.end()));
            }
            std::cout << p.first << "," << n << "," << (total / runs) << "\n";
        }
    }
}

Notes and cautions: compile in release mode (g++ -O2 or -O3), run on a quiet machine, prefer median over mean if results vary, and test different input patterns (random, nearly-sorted, reversed) because some algorithms behave very differently. See std::vector and std::chrono / random utilities for details on the APIs used.

Recommended Answers

All 2 Replies

Member Avatar for Nick Evan

Do my homework for me

Narue was here? :)

Post your code and you will recieve help

Niek

Member Avatar for ithelp

There is already a class named vector, just try to get some idea how it is implemented, your homework would be easy then.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.