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;
}
How do you analysis the running time for this Quicksort Algorithm. What are the steps? // Include all necessary library
-
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am