# Untitled

unknown
plain_text
2 years ago
2.8 kB
68
Indexable
Never
```#include <iostream>
using namespace std;

void printArray(int * arr, int n){

for(int i=0; i <n; i++){
cout << arr[i] << ", ";
}
cout << endl;
}

void bubbleSort(int * arr, int n){

// n-1 iterations n = 5
for(int itr =1; itr<=n-1; itr++){ // n-1 times

// jth element with j+1th element
for(int j=0; j < n - itr; j++){ // n-i times

cout << "comparing " << arr[j] << " with " << arr[j+1] << endl;
if(arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
}
}
}

}

void optimisedBubbleSort(int * arr, int n){

// n-1 iterations n = 5

for(int itr =1; itr<=n-1; itr++){ // n-1 times

bool isSwapped = false;

// jth element with j+1th element
for(int j=0; j < n - itr; j++){ // n-i times

cout << "comparing " << arr[j] << " with " << arr[j+1] << endl;
if(arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
isSwapped = true;
}
}

if(!isSwapped) {
break;
}
}

}

int minIndexInArray(int * arr, int start, int end){

int min = start;
for(int i=start+1; i<end; i++){

if(arr[i] < arr[min]){
min = i;
}
}

return min;

}

void selectionSort(int * arr, int n){

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

// find min element and swap
int minIndex = minIndexInArray(arr, i, n);
swap(arr[minIndex], arr[i]);
}
}

void insertionSort(int * arr, int n){

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

// int j = i-1;

// while(j>=0 && arr[j] > arr[j+1]){
// 	cout << "comparing " << arr[j] << " with " << arr[j+1] << endl;
// 	swap(arr[j], arr[j+1]);
// 	j--;
// }

for(int j = i-1; j>=0; j--){
if(arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}

}

int * mergeTwoSortedArrays(int * arr1, int n, int * arr2, int m){

// create a new array
int * newArray = new int[n+m];

int i=0, j=0, k=0;
while(i < n && j < m){

if(arr1[i] > arr2[j]){
newArray[k] = arr2[j];
j++;

} else {
newArray[k] = arr1[i];
i++;
}

k++;
}

while(i < n){
newArray[k] = arr1[i];
i++;
k++;
}

while(j < m){
newArray[k] = arr2[j];
j++;
k++;
}

return newArray;
}

int * mergeSort(int * arr, int start, int end){
// base case
if(start == end){
int * newArray = new int[1];
newArray[0] = arr[start];
return newArray;
}

// divide and conquer
int mid = (start + end)/2;
int * lsh = mergeSort(arr, start, mid);
int * rsh = mergeSort(arr, mid+1, end);

int * finalArray = mergeTwoSortedArrays(lsh, mid-start+1, rsh, end - mid);
return finalArray;

}

int main() {

int n;
cin >> n;

int arr[n];
for(int i=0; i<n; i++){
cin >> arr[i];
}

printArray(arr, n);
int * sortedArray = mergeSort(arr, 0, n-1);
// bubbleSort(arr, n);
// cout << "=======" << endl;
// optimisedBubbleSort(arr, n);
printArray(sortedArray, n);
return 0;
}```