526互联

cpp generate random array then sort by quick sort

发布时间 2023-04-05 21:26:28作者: Fred1987
#include <chrono>
#include <ctime>
#include <iomainp>
#include <iostream>
#include <random>
#include <sstream>

std::string get_time_now()
{
std::chrono::time_point<std::chrono::high_resolution_clock> now = std::chrono::high_resolution_clock::now();
time_t raw_time = std::chrono::high_resolution_clock::to_time_t(now);
struct tm tm_info = *localtime(&raw_time);
std::stringstream ss;
std::chrono::seconds seconds = std::chrono::duration_cast<std::chrono::seconds>(now.time_since_epoch());
std::chrono::milliseconds mills = std::chrono::duration_cast<std::chrono::milliseconds>(now.time_since_epoch());
std::chrono::microseconds micros = std::chrono::duration_cast<std::chrono::microseconds>(now.time_since_epoch());
std::chrono::nanoseconds nanos = std::chrono::duration_cast<std::chrono::nanoseconds>(now.time_since_epoch());
ss << std::put_time(&tm_info, "%Y%m%d%H%M%S")
<< std::setw(3) << std::setfill('0') << std::to_string(mills.count() - seconds.count() * 1000)
<< std::setw(3) << std::setfill('0') << std::to_string(micros.count() - mills.count() * 1000)
<< std::setw(3) << std::setfill('0') << std::to_string(nanos.count() - micros.count() * 1000);
return ss.str();
}

template <typename T>
T gen_random(T min, T max)
{
    std::random_device rd;
    std::mt19937_64 mt(rd());
    std::uniform_int_distribution<T> uid(min, max);
    return uid(mt);
}

template <typename T>
void print_t_array(T *arr, const int &len)
{
    for (int i = 0; i < len; i++)
    {
        std::cout << i << "," << arr[i] << "\t";
    }
    std::cout << std::endl;
}
template <typename T>
void swap(T *left, T *right)
{
    T temp = *left;
    *left = *right;
    *right = temp;
}

template<typename T>
void gen_T_array_len(T *arr,T min,T max,const int&len)
{
    for(int i=0;i<len;i++)
    {
        arr[i]=gen_random<std::uint32_t>(0,UINT32_MAX);
    }
}


template<typename T>
int get_partition(T *arr,int low,int high)
{
    int pivot=arr[high];
    int i=low-1;
    for(int j=low;j<high;j++)
    {
        if(arr[j]<pivot)
        {
            i=i+1;
            swap(&arr[i],&arr[j]);
        }
    } 
    swap(&arr[i+1],&arr[high]);
    return i+1;
}

template<typename T>
void quick_sort_T(T *arr,int low,int high)
{
    if(low<high)
    {
        int pivot=get_partition(arr,low,high);
        quick_sort_T(arr,low,pivot-1);
        quick_sort_T(arr,pivot+1,high);
    }
}


template<typename T>
int get_partition(T *arr,int low,int high)
{
    int pivot=arr[high];
    int i=low-1;
    for(int j=low;j<high;j++)
    {
        if(arr[j]<pivot)
        {
            i=i+1;
            swap(&arr[i],&arr[j]);
        }
    } 
    swap(&arr[i+1],&arr[high]);
    return i+1;
}

template<typename T>
void quick_sort_T(T *arr,int low,int high)
{
    if(low<high)
    {
        int pivot=get_partition(arr,low,high);
        quick_sort_T(arr,low,pivot-1);
        quick_sort_T(arr,pivot+1,high);
    }
}

void quick_sort_len(const int &len)
{
uint32_t *arr = new uint32_t[len];
gen_T_array_len<std::uint32_t>(arr, 0, UINT32_MAX, std::cref(len));
std::cout << "Before quick sort:" << std::endl;
print_t_array<std::uint32_t>(arr, std::cref(len));
std::cout << "\n\nAfter quick sort:" << std::endl;
quick_sort_T<std::uint32_t>(arr, 0, len - 1);
print_t_array<std::uint32_t>(arr, std::cref(len));
delete[] arr;
std::cout << get_time_now() << ",finish in " << __FUNCTION__ << std::endl;
}

int main(int args, char **argv)
{
quick_sort_len(atoi(argv[1]));
}
 

 

g++ -g -std=c++2a -I. *.cpp -o h1 -luuid

 

 

 

The key located at get the pivot of array iterately

template <typename T>
int get_partition(T *arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i = i + 1;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}