Question

C++, Take this 3 pseudocode and transform them into C++ then implement them making a quick sort program using the function of the pseudocode that you changed to C++, also in the main the user need to put the array that he wants to do quick sort with. plz comment everything you do in details this is for a presentation

1. A first draft of pseudocode for the quick sort algorithm follows:

// Sorts theArray[first..last].
quickSort(theArray: ItemArray, first: integer, last: integer): void
if (first < last)
{
Choose a pivot item p from theArray[first..last]
Partition the items of theArray[first..last] about p
// The partition is theArray[first..pivotIndex..last]
quickSort(theArray, first, pivotIndex - 1) // Sort S 1
quickSort(theArray, pivotIndex + 1, last) // Sort S 2
}
// If first >= last, there is nothing to do

2. Pseudocode for function sortFIrstMidLast

if (theArray[first] > theArray[mid])
Interchange theArray[first] and theArray[mid]
if (theArray[mid] > theArray[last])
Interchange theArray[mid] and theArray[last]
if (theArray[first] > theArray[mid])
Interchange theArray[first] and theArray[mid]

3. The following pseudocode describes the partitioning algorithm for an array of at least four entries:
// Partitions theArray[first..last].
partition(theArray: ItemArray, first: integer, last: integer): integer
// Choose pivot and reposition it
mid = first + (last - first) / 2
sortFirstMiddleLast(theArray, first, mid, last)
Interchange theArray[mid] and theArray[last – 1]
pivotIndex = last - 1
pivot = theArray[pivotIndex]
// Determine the regions S 1 and S 2
indexFromLeft = first + 1
indexFromRight = last - 2
done = false
while (not done)
{
// Locate first entry on left that is ≥ pivot
while (theArray[indexFromLeft] < pivot)
indexFromLeft = indexFromLeft + 1
// Locate first entry on right that is ≤ pivot
while (theArray[indexFromRight] > pivot)
indexFromRight = indexFromRight - 1
if (indexFromLeft < indexFromRight)
{
Move theArray[firstUnknown] into S1
Interchange theArray[indexFromLeft] and theArray[indexFromRight]
indexFromLeft = indexFromLeft + 1
indexFromRight = indexFromRight - 1
}
else
done = true
}
// Place pivot in proper position between S 1 and S 2 , and mark its new location
Interchange theArray[pivotIndex] and theArray[indexFromLeft]
pivotIndex = indexFromLeft
return pivotIndex

Answer 1

Quick Sort Program in C++

#include <iostream>

using namespace std;

#include<iostream>
#include<cstdlib>

using namespace std;

// Swapping two values.
void swap(int *a, int *b)
{
   int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}

// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high)
{
   int pivot, index, i;
   index = low;
   pivot = high;

   // Getting index of pivot.
   for(i=low; i < high; i++)
   {
       if(a[i] < a[pivot])
       {
           swap(&a[i], &a[index]);
           index++;
       }
   }
   // Swapping value at high and at the index obtained.
   swap(&a[pivot], &a[index]);

   return index;
}

// Random selection of pivot.
int RandomPivotPartition(int a[], int low, int high)
{
   int pvt, n, temp;
   n = rand();
   // Randomizing the pivot value in the given subpart of array.
   pvt = low + n%(high-low+1);

   // Swapping pvt value from high, so pvt value will be taken as pivot while partitioning.
   swap(&a[high], &a[pvt]);

   return Partition(a, low, high);
}

// Implementing QuickSort algorithm.
int QuickSort(int a[], int low, int high)
{
   int pindex;
   if(low < high)
   {
       // Partitioning array using randomized pivot.
       pindex = RandomPivotPartition(a, low, high);
       // Recursively implementing QuickSort.
       QuickSort(a, low, pindex-1);
       QuickSort(a, pindex+1, high);
   }
   return 0;
}

int main()
{
   int n, i;
   cout<<"\nEnter the number of data element to be sorted: ";
   cin>>n;

   int arr[n];
   for(i = 0; i < n; i++)
   {
       cout<<"Enter element "<<i+1<<": ";
       cin>>arr[i];
   }

   QuickSort(arr, 0, n-1);

   // Printing the sorted data.
   cout<<"\nSorted Data ";
   for (i = 0; i < n; i++)
           cout<<"->"<<arr[i];

   return 0;
}

Enter the number of data element to be sorted: 4
Enter element 1: 23
Enter element 2: 56
Enter element 3: 12
Enter element 4: 3

Sorted Data ->3->12->23->56