Question

Define a problem utilizing an efficient sorting algorithm please write code in c++ oop thnx?

Answer 1

One of the most primitive application of sorting is to apply a binary search on an array.

Below is the code in C++.

CODE

#include <cstdlib>

#include <iostream>

using namespace std;

// Implementation of efficient Quick sort

int partition(int arr[], int low, int high)

{

  int pivot = arr[low];

  int i = low - 1, j = high + 1;

  while (true) {

    do {

      i++;

    } while (arr[i] < pivot);

    do {

      j--;

    } while (arr[j] > pivot);

    if (i >= j)

      return j;

    swap(arr[i], arr[j]);

  }

}

int partition_r(int arr[], int low, int high)

{

  srand(time(NULL));

  int random = low + rand() % (high - low);

  swap(arr[random], arr[low]);

  return partition(arr, low, high);

}

void quickSort(int arr[], int low, int high)

{

  if (low < high) {

    int pi = partition_r(arr, low, high);

    quickSort(arr, low, pi);

    quickSort(arr, pi + 1, high);

  }

}

int binarySearch(int arr[], int l, int r, int x)

{

if (r >= l) {

int mid = l + (r - l) / 2;

if (arr[mid] == x)

return mid;

if (arr[mid] > x)

return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);

}

return -1;

}

int main()

{

int n = 10;

  int arr[n];

srand(time(NULL));

for (int i=0; i<n; i++) {

arr[i] = rand() % 10;

}

cout << "The array is: " << endl;

for(int i=0; i<n; i++) {

cout << arr[i] << " ";

}

cout << endl;

  quickSort(arr, 0, n - 1);

  int index = binarySearch(arr, 0, n-1, 4);

cout << "4 found at location " << index;

return 0;

}