DAA P3 merge sort, quick sort

-

 Merge Sort


#include <bits/stdc++.h>
using namespace std;

void merge(int array[], int const left, int const mid,
    int const right)
{
  int const subArrayOne = mid - left + 1;
  int 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, indexOfSubArrayTwo = 0;
  int indexOfMergedArray = left;


  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++;
  }
  delete[] leftArray;
  delete[] rightArray;
}

void mergeSort(int array[], int const begin, int const end)
{
  if (begin >= end)
    return;

  int 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 (int i = 0; i < size; i++)
    cout << A[i] << " ";
  cout << endl;
}

int main()
{
  int arr[] = { 12, 11, 13, 5, 6, 7 };
  int 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;
}


Quick Sort

#include<bits/stdc++.h>
using namespace std;

void swap(int arr[] , int pos1, int pos2){
  int temp;
  temp = arr[pos1];
  arr[pos1] = arr[pos2];
  arr[pos2] = temp;
}

int partition(int arr[], int low, int high, int pivot){
  int i = low;
  int j = low;
  while( i <= high){
    if(arr[i] > pivot){
      i++;
    }
    else{
      swap(arr,i,j);
      i++;
      j++;
    }
  }
  return j-1;
}

void quickSort(int arr[], int low, int high){
  if(low < high){
  int pivot = arr[high];
  int pos = partition(arr, low, high, pivot);
 
  quickSort(arr, low, pos-1);
  quickSort(arr, pos+1, high);
  }
}

int main()
{
  int n ;
  cout << " enter the size of array";
  cin>>n;
  int arr[n];
  for( int i = 0 ; i < n; i++){
    cin>> arr[i];
  }
  quickSort(arr, 0 , n-1);
  cout<<"The sorted array is: ";
  for( int i = 0 ; i < n; i++){
    cout<< arr[i]<<"\t";
  }
 
}

Comments

Post a Comment

Popular posts from this blog

DAA P4 bfs, dfs

-
BFS #include < bits/stdc++.h > using namespace std ; class Graph {   int V ;   vector < list <int> > adj ; public :   Graph ( int V );   void addEdge ( int v , int w );   void BFS ( int s ); }; Graph :: Graph ( int V ) {   this -> V = V ;   adj . resize ( V ); } void Graph :: addEdge ( int v , int w ) {   adj [ v ] . push_back ( w ); } void Graph :: BFS ( int s ) {   vector <bool> visited ;   visited . resize ( V , false );   list <int> queue ;   visited [ s ] = true ;   queue . push_back ( s );   while ( ! queue . empty ()) {         s = queue . front ();     cout << s << " " ;     queue . pop_front ();     for ( auto adjacent : adj [ s ] ) {       if ( ! visited [ adjacent ] ) {         visited [ adjacent ] = true ;         q...
Read more

DAA P8 graph coloring

-
  Graph coloring // A C++ program to implement greedy algorithm for graph coloring #include < iostream > #include < list > using namespace std ; // A class that represents an undirected graph class Graph {   int V ; // No. of vertices   list <int> * adj ; // A dynamic array of adjacency lists public :   // Constructor and destructor   Graph ( int V ) { this -> V = V ; adj = new list <int> [ V ]; }   ~Graph ()   { delete [] adj ; }   // function to add an edge to graph   void addEdge ( int v , int w );   // Prints greedy coloring of the vertices   void greedyColoring (); }; void Graph :: addEdge ( int v , int w ) {   adj [ v ]. push_back ( w );   adj [ w ]. push_back ( v ); // Note: the graph is undirected } // Assigns colors (starting from 0) to all vertices and prints // the assignment of colors void Graph :: greedyColoring () {   int result [ V ];   //...
Read more

Practical 8 by Karan

-
 #include <stdio.h> struct emp { int no; int sal; char name[20]; };   int binarySearch(struct emp a[], int n, int x) {        int low=0, mid, high=n-1, count = 0;    while(low <= high)    {        count++;         mid = (low + high) / 2;         if (x < a[mid].no)             high = mid - 1;         else if (x > a[mid].no)          low = mid + 1;        else {         printf("no of search = %d\n",count);       return mid;        }    } return -1; }    void printArray(struct emp array[], int size) {   for (int i = 0; i < size; ++i) {      printf("name = %s\n",array[i].name);     printf(" salary = %d\n ", array[i].sal);      printf(" number = %d...
Read more