How do you analysis the running time for this Quicksort Algorithm. What are the steps? // Include all necessary library

Business, Finance, Economics, Accounting, Operations Management, Computer Science, Electrical Engineering, Mechanical Engineering, Civil Engineering, Chemical Engineering, Algebra, Precalculus, Statistics and Probabilty, Advanced Math, Physics, Chemistry, Biology, Nursing, Psychology, Certifications, Tests, Prep, and more.
Post Reply
answerhappygod
Site Admin
Posts: 899603
Joined: Mon Aug 02, 2021 8:13 am

How do you analysis the running time for this Quicksort Algorithm. What are the steps? // Include all necessary library

Post by answerhappygod »

How do you analysis the running time for this QuicksortAlgorithm. What are the steps?
// Include all necessary library
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE1 = 8;
const int SIZE2 = 100;
const int SIZE3 = 1000;
void generateArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
arr = i + 1;
}
random_shuffle(arr, arr + size);
}
void displayArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr<< " ";
}
cout << endl << endl;
}
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
int partition(int arr[], int left, int right)
{
int j = left + 1;
for (int i = left + 1; i <= right;i++)
{
if (arr <arr[left])
{
swap(arr, arr[j++]);
}
}
if (left < j)
{
// cout <<"TEST\n";
swap(arr[left], arr[j- 1]);
if (left < j -2)
{
partition(arr, left, j - 2);
}
}
return j;
}
// Average/Worst: O(n log n)
// Best: O(n log n)
void quicksort(int arr[], int left, int right)
{
int pivot = partition(arr, left, right);
if (pivot < right)
{
// cout <<"TEST\n";
quicksort(arr, left,pivot);
quicksort(arr, pivot,right);
}
}
// Run the program
int main()
{
// Declare the local variables
int arr1[SIZE1] = { 10, 80, 3, 19, 14, 7, 5,12 };
// int arr1[SIZE1] = {1, 2, 3, 4, 5, 6, 7,8};
int arr2[SIZE2];
int arr3[SIZE3];
generateArray(arr2, SIZE2);
generateArray(arr3, SIZE3);
quicksort(arr1, 0, SIZE1 - 1);
displayArray(arr1, SIZE1);
quicksort(arr2, 0, SIZE2 - 1);
displayArray(arr2, SIZE2);
quicksort(arr3, 0, SIZE3 - 1);
displayArray(arr3, SIZE3);
// Terminate the program
return 0;
}
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!
Post Reply