Please help, C++ - Algorithm Comparison: Pivot Sorter Pivot Sorter Algorithm Ass

Question

Please help, C++ - Algorithm Comparison: Pivot Sorter

Pivot Sorter Algorithm Assignment For this assignment, you'll be creating a Pivot Sort (guicksort) algorithm in addition to your eviously made Bubble Sort assignment from last week. A Pivot Sort works recursively, by making an algorithm that picks some element in an array, and shuffles all the other elements around so that all those elements LESS than the selected element are on the left, and all elements MORE than the selected element are on the right. The elected element is referred to as the pivot Note that as this is happening, the elements you move aren't themseves sorted with regards to one another, just to if they re more or less than the pivot. Once they're arranged in this manner, you take the chunk of the array that's to the left of the pivot, and pass that back to ANOTHER Pivot Sort Similarly, you take the chunk of the array that's to the right of the pivot, and pass it to another Pivot Sort as well. The Pivot Sort will continue sing until it's given a chunk of array that's two elements or fewer, at which point it will quickly sort those, and then signal all the previous Pivot Sorts that called it that it's done You can imagine it as shown in the attached image, where '4' is chosen as the first pivot In your examples you won't have to worry about repeating numbers. My suggestion for each of you is that our Pivot Sort Algorithm works on a global array, and that it takes as its input a starting point in an array, an ending point in an array, and the point in an array a pivot is at. For example, if your starting array is 10 elements ng, you ”uld pass in 'O, as the starting point, and '9, as the ending point, and then any point you wish as the tion of the pivot As last time, you'll need to display not only the sorted arrays, but also the number of actions performed ember, you'll count all comparisons as ONE action, and all swapping of two variables will count as THREE tions. In addition to the results of the Pivot Sort, also include the results of the Bubble Sort as wel Your results should not only display the sorted version of the array, but also a count of the total number of actions that took place while sorting. Please sort the following three lists 11,3,4,5,2,4,6,8,9,10) (10,9,8,7,6,5,4,3,2,1) 2,4,6,8,10,9,7,5,3,1)

Explanation / Answer

#include<iostream>
using namespace std;

int steps = 0;

int Partition(int a[], int beg, int end) //Function to Find Pivot Point
{
int p=beg, pivot=a[beg], loc;

for(loc=beg+1;loc<=end;loc++)
{
   steps ++;

if(pivot>a[loc])
{
a[p]=a[loc];
a[loc]=a[p+1];
a[p+1]=pivot;

p=p+1;

steps = steps + 3;
}

steps ++;
}

steps ++;
return p;
}

void QuickSort(int a[], int beg, int end)
{
if(beg<end)
{
int p=Partition(a,beg,end); //Calling Procedure to Find Pivot

QuickSort(a,beg,p-1); //Calls Itself (Recursion)
QuickSort(a,p+1,end);           //Calls Itself (Recursion)
}
steps ++;
}

void print(int arr[], int n)
{
   int i;
   cout<<" After Sorting : ";
for(i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl<<"And steps taken are: "<<steps;
cout<<" ";
}
void main()
{
int a[100],i,n1, n2, n3, beg,end;

int arr1[] = {1, 3, 4, 5, 2 ,4, 6, 8, 9, 10};
n1 = 9;

int arr2[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
n2 = 9;

int arr3[] = {2, 4, 6, 8, 10, 9, 7, 5, 3, 1};
n3 = 9;

QuickSort(arr1, 1, n1);     //Calling of QuickSort Function
print(arr1, n1);

steps= 0;
QuickSort(arr2, 1, n2);
print(arr2, n2);

steps= 0;
QuickSort(arr3, 1, n3);
print(arr3, n3);

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---