I need help revising this code to improve quick sort. I need to understand the time complexity of the code too. Please. #include using namespace std; // Function prototypes void quickSort(int list[], int arraySize); void quickSort(int list[], int middle, int last); int partition(int list[], int middle, int last); void quickSort(int list[], int arraySize) { quickSort(list, 0, arraySize - 1); } void quickSort(int list[], int middle, int last) { if (last > middle) { int pivotIndex = partition(list, middle, last); quickSort(list, middle, pivotIndex - 1); quickSort(list, pivotIndex + 1, last); } } // Partition the array list[first..last] int partition(int list[], int middle, int last) { int pivot = list[middle]; // Choose the first element as the pivot int low = middle + 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 > middle && list[high] >= pivot) high--; // Swap pivot with list[high] if (pivot > list[high]) { list[middle] = list[high]; list[high] = pivot; return high; } else { return middle; } } int main() { const int SIZE = 10; int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2,10 }; quickSort(list, SIZE); for (int i = 0; i < SIZE; i++) cout << list[i] << " "; return 0;
I need help revising this code to improve quick sort. I need to understand the time complexity of the code too. Please.
#include <iostream>
using namespace std;
// Function prototypes
void quickSort(int list[], int arraySize);
void quickSort(int list[], int middle, int last);
int partition(int list[], int middle, int last);
void quickSort(int list[], int arraySize)
{
quickSort(list, 0, arraySize - 1);
}
void quickSort(int list[], int middle, int last)
{
if (last > middle)
{
int pivotIndex = partition(list, middle, last);
quickSort(list, middle, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
// Partition the array list[first..last]
int partition(int list[], int middle, int last)
{
int pivot = list[middle]; // Choose the first element as the pivot
int low = middle + 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 > middle && list[high] >= pivot)
high--;
// Swap pivot with list[high]
if (pivot > list[high])
{
list[middle] = list[high];
list[high] = pivot;
return high;
}
else
{
return middle;
}
}
int main()
{
const int SIZE = 10;
int list[] = {1, 7, 3, 4, 9, 3, 3, 1, 2,10 };
quickSort(list, SIZE);
for (int i = 0; i < SIZE; i++)
cout << list[i] << " ";
return 0;
}
Step by step
Solved in 2 steps with 2 images
