Algorithm Design C++ Help! C++ code needed to Apply quickselect to find the medi

Question

Algorithm Design C++ Help!

C++ code needed to Apply quickselect to find the median of the list of numbers 9, 12, 5, 17, 20, 30, 8.

Base C++ Code off of PSUEDO CODE:

ALGORITHM Quickselect(A[l..r], k)

//Solves the selection problem by recursive partition-based algorithm

//Input: Subarray A[l..r] of array A[0..n 1] of orderable elements and

// integer k (1 k r l + 1)

//Output: The value of the kth smallest element in A[l..r]

s LomutoPartition(A[l..r]) //or another partition algorithm

if s = k 1 return A[s]

else if s > l + k 1 Quickselect(A[l..s 1], k)

else Quickselect(A[s + 1..r], k 1 s)

Explanation / Answer

#include<iostream>
using namespace std;
////Solves the selection problem by recursive partition-based algorithm
//Input: Subarray A[l..r] of array A[0..n - 1] of orderable elements and
// integer k (1= k = r - l + 1)
//Output: The value of the kth smallest element in A[l..r]
//s ?LomutoPartition(A[l..r]) //or another partition algorithm

//lomutopartition
int lomuto_partition(int a[], int low, int high)
{
int p= a[high]; // pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (a[j] <= p)
{
i++; // increment index of smaller element
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[high]);
return (i + 1);
}

int Quickselect(int A[],int k,int l,int r)
{
   int s = lomuto_partition(A,l,r);//partition algorithm
  
   if(s==k-1)return A[s];//returning element
   else if(s>l+k-1) Quickselect(A,k,l,s-1);
   else Quickselect(A,k-1-s,s+1,r);

  
}

int main()
{
   int a[7]={9, 12, 5, 17, 20, 30, 8};
   int k=2;//smallest element
   int r = Quickselect(a,k,0,6);//function calling
   cout<<k<<" th smallest:"<<r<<endl;
   return 0;
}

output:

2 th smallest:8

Process exited normally.
Press any key to continue . . .

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.