Language: C++ Write a Program with Comments for your code to improve quick sort. The quick sort algorithm presented in the ClassNotes-Sorting, it selects the first element in the list as the pivot.Revise it by selecting the median among the first, middle, and last elements in the list.Explain your Outputs or Answers for the following:(A) Analyze your algorithm, and give the results using order notation.(B) Give a list of n items (for example, an array of 10 integers) representing a scenario.Please compile your answers in a file including all source code with comments, Explain your running Outputs or Answers in (A) and (B). Can you label which one is for (A) and (B). Code that was mentioned:#include <iostream>using namespace std;// Function prototypesvoid quickSort(int list[], int arraySize);void quickSort(int list[], int first, int last);int partition(int list[], int first, int last);void quickSort(int list[], int arraySize){quickSort(list, 0, arraySize - 1);}void quickSort(int list[], int first, int last){if (last > first){int pivotIndex = partition(list, first, last);quickSort(list, first, pivotIndex - 1);quickSort(list, pivotIndex + 1, last);}}// Partition the array list[first..last]int partition(int list[], int first, int last){int pivot = list[first]; // Choose the first element as the pivotint low = first + 1; // Index for forward searchint high = last; // Index for backward searchwhile (high > low){// Search forward from leftwhile (low <= high && list[low] <= pivot)low++;// Search backward from rightwhile (low <= high && list[high] > pivot)high--;// Swap two elements in the listif (high > low){int temp = list[high];list[high] = list[low];list[low] = temp;}}while (high > first && list[high] >= pivot)high--;// Swap pivot with list[high]if (pivot > list[high]){list[first] = list[high];list[high] = pivot;return high;}else{return first;}}int main(){const int SIZE = 9;int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2};quickSort(list, SIZE);for (int i = 0; i < SIZE; i++)cout << list[i] << " ";return 0;} **Educational Text: Quick Sort Algorithm Improvement**In this exercise, you are required to write a program with comments to improve the quick sort algorithm. The version presented in the ClassNotes-Sorting selects the first element in the list as the pivot. Your task is to modify this by selecting the median among the first, middle, and last elements in the list.**Tasks:**1. **Analyze Your Algorithm:** - Provide an analysis of your algorithm with an explanation using order notation.2. **Normal Scenario:** - Create a list of n items (e.g., an array of 10 integers) representing a general case scenario.3. **Worst-Case Scenario:** - Create a list of n items (e.g., an array of 10 integers) representing the worst-case scenario.4. **Best-Case Scenario:** - Create a list of n items (e.g., an array of 10 integers) representing the best-case scenario.Please include all your answers and explanations in a file with complete source code and comments. Ensure you explain the outputs or answers for each of the tasks above. ```cpp#include using namespace std;// Function prototypesvoid quickSort(int list[], int arraySize);void quickSort(int list[], int first, int last);int partition(int list[], int first, int last);void quickSort(int list[], int arraySize){ quickSort(list, 0, arraySize - 1);}void quickSort(int list[], int first, int last){ if (last > first) { int pivotIndex = partition(list, first, last); quickSort(list, first, pivotIndex - 1); quickSort(list, pivotIndex + 1, last); }}// Partition the array list[first..last]int partition(int list[], int first, int last){ int pivot = list[first]; // Choose the first element as the pivot int low = first + 1; // Index for forward search int high = last; // Index for backward search while (high > low) { // Search forward from left while (low <= high && list[low] <= pivot) low++; // Search backward from right while (low <= high && list[high] > pivot) high--; // Swap two elements in the list if (high > low) { int temp = list[high]; list[high] = list[low]; list[low] = temp; } } while (high > first && list[high] >= pivot) high--; // Swap pivot with list[high] if (pivot > list[high]) { list[first] = list[high]; list[high] = pivot; return high; } else { return first; }}int main(){ const int SIZE = 9; int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2}; quickSort(list, SIZE); for (int i = 0; i < SIZE; i++) cout << list[i] << " "; return 0;}```**Explanation:**This C++ code implements the Quick Sort algorithm, which is a well-known sorting algorithm. The code is divided into several parts:1. **Function Prototypes:** - `

Quick sort: Quicksort has a couple of other differences from merge sort. Quicksort works in place.…

Language: C++ Write a Program with Comments for your code to improve quick sort. The quick sort algorithm presented in the ClassNotes-Sorting, it selects the first element in the list as the pivot. Revise it by selecting the median among the first, middle, and last elements in the list. Explain your Outputs or Answers for the following: (A) Analyze your algorithm, and give the results using order notation. (B) Give a list of n items (for example, an array of 10 integers) representing a scenario. Please compile your answers in a file including all source code with comments, Explain your running Outputs or Answers in (A) and (B). Can you label which one is for (A) and (B). Code that was mentioned: #include using namespace std; // Function prototypes void quickSort(int list[], int arraySize); void quickSort(int list[], int first, int last); int partition(int list[], int first, int last); void quickSort(int list[], int arraySize) { quickSort(list, 0, arraySize - 1); } void quickSort(int list[], int first, int last) { if (last > first) { int pivotIndex = partition(list, first, last); quickSort(list, first, pivotIndex - 1); quickSort(list, pivotIndex + 1, last); } } // Partition the array list[first..last] int partition(int list[], int first, int last) { int pivot = list[first]; // Choose the first element as the pivot int low = first + 1; // Index for forward search int high = last; // Index for backward search while (high > low) { // Search forward from left while (low <= high && list[low] <= pivot) low++; // Search backward from right while (low <= high && list[high] > pivot) high--; // Swap two elements in the list if (high > low) { int temp = list[high]; list[high] = list[low]; list[low] = temp; } } while (high > first && list[high] >= pivot) high--; // Swap pivot with list[high] if (pivot > list[high]) { list[first] = list[high]; list[high] = pivot; return high; } else { return first; } } int main() { const int SIZE = 9; int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2}; quickSort(list, SIZE); for (int i = 0; i < SIZE; i++) cout << list[i] << " "; return 0; }