Pivot sorter algorithm in C++!! Thank you! Pivot Sorter Algorithm Assignment: Fo

Question

Pivot sorter algorithm in C++!! Thank you!

Pivot Sorter Algorithm Assignment: For this assignment, you'll be creating a Pivot Sort (quicksort) algorithm in addition to your previously 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 selected element is referred to as the pivot. Note that as this is happening, the elements you move aren't themselves 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 passing 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' S 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 your 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 long, you could pass in '0' as the starting point, and '9' as the ending point', and then any point you wish as the location of the pivot. As last time, you'll need to display not only the sorted arrays, but also the number of actions performed. Remember, you'll count all comparisons as ONE action, and all swapping of two variables will count as THREE actions. In addition to the results of the Pivot Sort, also include the results of the Bubble Sort as well. 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. {1,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

---