Question

Quick sort func in C++

#include <iostream>

#include <stdlib.h>

#include <string>

using namespace std;

void MyFunc ( int *array ) {

// Code here

}

int main(int argc,char **argv) {

int *Sequence;

int arraySize;

// Get the size of the sequence

cin >> arraySize;

// Allocate enough memory to store "arraySize" integers

Sequence = new int[arraySize];

  

// Read in the sequence

for ( int i=0; i<arraySize; i++ )

cin >> Sequence[i];

// Run your algorithms to manipulate the elements in Sequence

MyFunc(Sequence);

  

// Output the result

for(int i=0; i<arraySize; i++)

cout << Sequence[i] << endl;

  

// Free allocated space

delete[] Sequence;

}

Answer 1

The required function is implemented in the below source code:

#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

//swap method
void swap(int* first, int* second)
{
int t = *first;
*first = *second;
*second = t;
}

//method for partition
int partition(int a[], int l, int h)
{
int pvt = a[h];
int i = l - 1;
  
for (int j = l; j <= h - 1; j++)
{
if (a[j] < pvt)
{
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i + 1], &a[h]);
return i + 1;
}

//mthod for quick sort
void MyFunc(int *a, int l, int h)
{
if (l < h)
{

int p = partition(a, l, h);
MyFunc(a, l, p - 1);
MyFunc(a, p + 1, h);
}
}

int main(int argc,char **argv)
{
int *Sequence;
int arraySize;
  
// Get the size of the sequence
cin >> arraySize;
  
// Allocate enough memory to store "arraySize" integers
Sequence = new int[arraySize];
  
// Read in the sequence
for ( int i=0; i<arraySize; i++ )
cin >> Sequence[i];
  
// Run your algorithms to manipulate the elements in Sequence
MyFunc(Sequence, 0, arraySize-1);
  
// Output the result
for(int i=0; i<arraySize; i++)
cout << Sequence[i] << endl;
  
// Free allocated space
delete[] Sequence;
}

OUTPUT:

5
10 30 20 40 25
10
20
25
30
40