DAA P1 - selection, bubble, insertion sort

-

 Selection Sort


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

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;
    }

    if (min_idx != i)
      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;
}


Bubble Sort


#include <stdbool.h>
#include <stdio.h>

void swap(int* xp, int* yp)
{
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

void bubbleSort(int arr[], int n)
{
  int i, j;
  bool swapped;
  for (i = 0; i < n - 1; i++) {
    swapped = false;
    for (j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
        swapped = true;
      }
    }

    if (swapped == false)
      break;
  }
}

void printArray(int arr[], int size)
{
  int i;
  for (i = 0; i < size; i++)
    printf("%d ", arr[i]);
}

int main()
{
  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, n);
  printf("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;
  }
}

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

int main()
{
  int arr[] = { 12, 11, 13, 5, 6 };
  int N = sizeof(arr) / sizeof(arr[0]);

  insertionSort(arr, N);
  printArray(arr, N);

  return 0;
}

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