Question

C++. This program is giving me a wrong quicksort sorting plz fix. use the function that it already have. don't add new function comment everything that you do thanks

#include<iostream>
#include<cstdlib>

using namespace std;

// Intercambiar dos valores.
// Arranges the first, middle, and last entries in an array into ascending order.

void sortFirstMiddleLast(int a[], int first, int mid, int last) {
  
   if (a[first] > a[mid])
   {
       int temp;
       temp = a[first];
       a[first] = a[mid];
       a[mid] = temp;
   }

   if (a[mid] > a[last])
   {
       int temp;
       temp = a[mid];
       a[mid] = a[last];
       a[last] = temp;
   }

   if (a[first] > a[mid])
   {
       int temp;
       temp = a[first];
       a[first] = a[mid];
       a[mid] = temp;
   }

}

int Partition(int a[], int first, int last)
{
   int pivot, index,indexFromLeft,indexFromRight, i,done,temp;
   index = first;
   pivot = last;
       // Choose pivot and reposition it
   int mid = first + (last - first) / 2;
   sortFirstMiddleLast(a, first, mid, last);
   // interchange theArray[mid] and theArray[last – 1]
   if (a[mid] > a[last - 1])
   {
      
       temp = a[mid];
       a[mid] = a[last - 1];
       a[last - 1] = temp;
   }

   index = last - 1;
   pivot = a[index];
       // Determine the regions S 1 and S 2
   indexFromLeft = first + 1;
   indexFromRight = last - 2;
   done = false;
       while (!done)
       {
           // Locate first entry on left that is ≥ pivot
           while (a[indexFromLeft] < pivot)
               indexFromLeft = indexFromLeft + 1;
               // Locate first entry on right that is ≤ pivot
           while (a[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*/
               a[first] = indexFromLeft;
               temp = a[indexFromLeft];
               a[indexFromLeft] = a[indexFromRight];
               a[indexFromRight] = temp;
               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]
           temp = a[index];
           a[index] = a[indexFromLeft];
           a[indexFromLeft] = temp;
           index = indexFromLeft;
           return index;
      
  
}

// Implementacion QuickSort.
int QuickSort(int a[], int first, int last)
{
   //tomaremos el array lo particiamos (lo dividimos) y aplicaremos el mismo método de forma recursiva.
   int pindex;
   if (first < last)
   {
       // particion del array usando el pivot que se cogio al azar.
       pindex = Partition(a, first, last);
       // se implementa el QuickSort de forma recursiva.
       QuickSort(a, first, pindex - 1);
       QuickSort(a, pindex + 1, last);
   }
   // el tipo de retorno de esta funcion es int se returna 0
   return 0;
}

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

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

   QuickSort(arr, 0, n - 1);

   // La data guardada que ya esta sorted.
   cout << "\nSorted Data ";
   for (i = 0; i < n; i++)
       cout << "->" << arr[i];

   return 0;
}

Answer 1

#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: 67
Enter element 3: 45
Enter element 4: 34

Sorted Data ->23->34->45->67