[go: up one dir, main page]
Scribd
Upload
89 views8 pages

(Prog 3)

Uploaded by

Mandeep Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
89 views8 pages

(Prog 3)

Uploaded by

Mandeep Das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 8

NAME MOHIT

ROLL NO-11813009
SEC-IT-1

IMPLEMENT MERGE SORT

#include <iostream>
using namespace std;

void merge(int array[], int const left, int const mid, int const right)
{
auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;

auto *leftArray = new int[subArrayOne],


*rightArray = new int[subArrayTwo];

for (auto i = 0; i < subArrayOne; i++)


leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];

auto indexOfSubArrayOne = 0, // Initial index of first sub-array


indexOfSubArrayTwo = 0; // Initial index of second sub-array
int indexOfMergedArray = left; // Initial index of merged array

while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {


if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}

while (indexOfSubArrayOne < subArrayOne) {


array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}

while (indexOfSubArrayTwo < subArrayTwo) {


array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
}

void mergeSort(int array[], int const begin, int const end)


{
if (begin >= end)
return; // Returns recursivly

auto mid = begin + (end - begin) / 2;


mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}

void printArray(int A[], int size)


{
for (auto i = 0; i < size; i++)
cout << A[i] << " ";
}

// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
auto arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is \n";


printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \n";


printArray(arr, arr_size);
return 0;
}
IMPLEMENT SELECTION SORT

#include <bits/stdc++.h>

using namespace std;

void swap(int *xp, int *yp)

int temp = *xp;

*xp = *yp;

*yp = temp;

void selectionSort(int arr[], int n)

int i, j, min_idx;
for (i = 0; i < n-1; i++)

min_idx = i;

for (j = i+1; j < n; j++)

if (arr[j] < arr[min_idx])

min_idx = j;

swap(&arr[min_idx], &arr[i]);

void printArray(int arr[], int size)

int i;

for (i=0; i < size; i++)

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

cout << endl;

int main()

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr)/sizeof(arr[0]);

selectionSort(arr, n);
cout << "Sorted array: \n";

printArray(arr, n);

return 0;

INSERTION SORT

#include <bits/stdc++.h>

using namespace std;

void insertionSort(int arr[], int n)

int i, key, j;

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


{

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key)

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

// A utility function to print an array of size n

void printArray(int arr[], int n)

int i;

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

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

cout << endl;

/* Driver code */

int main()

int arr[] = { 12, 11, 13, 5, 6 };

int n = sizeof(arr) / sizeof(arr[0]);


insertionSort(arr, n);

printArray(arr, n);

return 0;

You might also like