#include <iostream>
#include <cstdlib>
#include <time.h>
#define N 5
using namespace std;
void quicksort(int a[], int lowIndex, int highIndex);
int partition(int a[], int i, int j);
void mergeSort(int a[], int lowIndex, int highIndex);
void merge(int a[], int lowIndex, int midIndex, int highIndex);
int binarySearch(int arr[], int l, int r, int x);
void randomArray(int arr[], int n);
void printMatrix(int arr[], int n);
int main(){
int vector[N*N] = {};
int x;
randomArray(vector, N);
printMatrix(vector, N);
cout<<endl<<"Arreglo ordenado usando QuickSort"<<endl;
quicksort(vector, 0, N*N);
printMatrix(vector, N);
cout<<endl<<"Arreglo ordenado usando MergeSort"<<endl;
mergeSort(vector, 0, N*N);
printMatrix(vector, N);
cout<<endl<<"Introduzca un número y la buscaremos en matriz: ";
cin>>x;
int result = binarySearch(vector, 0, N*N-1, x);
if(result == -1){
cout<<"El elemento no esta presente en el arreglo";
}else{
cout<<"El elemento está presente en el índice: "<<result;
}
return 0;
}
void randomArray(int arr[], int n){
srand(time(NULL));
for(int i=0; i<n*n; i++)
arr[i] = 1+rand()%100;
}
void printMatrix(int arr[], int n){
for (int i=0; i<n; i++){
for(int j=0; j<n; j++)
cout<<"["<<arr[i*N+j]<<"] ";
cout<<endl;
}
}
void quicksort(int a[], int lowIndex, int highIndex){
if (lowIndex < highIndex){
int pivotIndex = partition(a, lowIndex, highIndex);
quicksort(a, lowIndex, pivotIndex-1);
quicksort(a, pivotIndex+1, highIndex);
}
}
int partition(int a[], int i, int j){
int pivot = a[i];
int pivotIndexAux = i;
for (int k=i+1; k<=j; k++){
if (a[k] < pivot){
pivotIndexAux++;
swap(a[k], a[pivotIndexAux]);
}
}
swap(a[i], a[pivotIndexAux]);
return pivotIndexAux;
}
void mergeSort(int a[], int lowIndex, int highIndex){
if(lowIndex < highIndex){
int midIndex = (lowIndex+highIndex)/2;
mergeSort(a, lowIndex, midIndex);
mergeSort(a, midIndex+1, highIndex);
merge(a, lowIndex, midIndex, highIndex);
}else{
return;
}
}
void merge(int a[], int lowIndex, int midIndex, int highIndex){
int n = highIndex-lowIndex+1;
int b[n];
b[n] = {};
int leftIndex = lowIndex;
int rightIndex = midIndex+1;
int bIndex = 0;
while(leftIndex<=midIndex && rightIndex<=highIndex){
if(a[leftIndex] <= a[rightIndex]){
b[bIndex++] = a[leftIndex++];
}else{
b[bIndex++] = a[rightIndex++];
}
}
while(leftIndex <= midIndex)
b[bIndex++] = a[leftIndex++];
while(rightIndex <= highIndex)
b[bIndex++] = a[rightIndex++];
for(int k=0; k<n; k++){
a[lowIndex+k] = b[k];
}
}
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;
}
