Skip to content

Commit b4374be

Browse files
AbhiTakerAbhiTaker
committed
local repo updated
1 parent 13af6a0 commit b4374be

7 files changed

Lines changed: 336 additions & 31 deletions

File tree

‎Floyd'sAlgorithm/C++/Floyd'sAlgorithm.cpp‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
#include<bits/stdc++.h>
2+
using namespace std;
3+
4+
/* Link list node */
5+
struct Node
6+
{
7+
int data;
8+
struct Node* next;
9+
};
10+
11+
void push(struct Node** head_ref, int new_data)
12+
{
13+
/* allocate node */
14+
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
15+
16+
/* put in the data */
17+
new_node->data = new_data;
18+
19+
/* link the old list off the new node */
20+
new_node->next = (*head_ref);
21+
22+
/* move the head to point to the new node */
23+
(*head_ref) = new_node;
24+
}
25+
26+
int detectloop(struct Node *list)
27+
{
28+
struct Node *slow_p = list, *fast_p = list;
29+
30+
while (slow_p && fast_p && fast_p->next )
31+
{
32+
slow_p = slow_p->next;
33+
fast_p = fast_p->next->next;
34+
if (slow_p == fast_p)
35+
{
36+
printf("Found Loop");
37+
return 1;
38+
}
39+
}
40+
return 0;
41+
}
42+
43+
//The Main function
44+
int main()
45+
{
46+
/* Start with the empty list */
47+
struct Node* head = NULL;
48+
49+
push(&head, 5);
50+
push(&head, 10);
51+
push(&head, 15);
52+
push(&head, 20);
53+
54+
/* Create a loop for testing */
55+
head->next->next->next->next = head;
56+
detectloop(head);
57+
58+
return 0;
59+
}

‎HeapSort/C++/HeapSort.cpp‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
// C++ program for implementation of Heap Sort
2+
#include <iostream>
3+
using namespace std;
4+
5+
// To heapify a subtree rooted with node i which is
6+
// an index in arr[]. n is size of heap
7+
void heapify(int arr[], int n, int i)
8+
{
9+
int largest = i; // Initialize largest as root
10+
int l = 2*i + 1; // left = 2*i + 1
11+
int r = 2*i + 2; // right = 2*i + 2
12+
13+
// If left child is larger than root
14+
if (l < n && arr[l] > arr[largest])
15+
largest = l;
16+
17+
// If right child is larger than largest so far
18+
if (r < n && arr[r] > arr[largest])
19+
largest = r;
20+
21+
// If largest is not root
22+
if (largest != i)
23+
{
24+
swap(arr[i], arr[largest]);
25+
26+
// Recursively heapify the affected sub-tree
27+
heapify(arr, n, largest);
28+
}
29+
}
30+
31+
// main function to do heap sort
32+
void heapSort(int arr[], int n)
33+
{
34+
// Build heap (rearrange array)
35+
for (int i = n / 2 - 1; i >= 0; i--)
36+
heapify(arr, n, i);
37+
38+
// One by one extract an element from heap
39+
for (int i=n-1; i>=0; i--)
40+
{
41+
// Move current root to end
42+
swap(arr[0], arr[i]);
43+
44+
// call max heapify on the reduced heap
45+
heapify(arr, i, 0);
46+
}
47+
}
48+
49+
/* A utility function to print array of size n */
50+
void printArray(int arr[], int n)
51+
{
52+
for (int i=0; i<n; ++i)
53+
cout << arr[i] << " ";
54+
cout << "\n";
55+
}
56+
57+
// Driver program
58+
int main()
59+
{
60+
int arr[] = {12, 11, 13, 5, 6, 7};
61+
int n = sizeof(arr)/sizeof(arr[0]);
62+
63+
heapSort(arr, n);
64+
65+
cout << "Sorted array is \n";
66+
printArray(arr, n);
67+
}

‎Kadane's/Java/Kadanes.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
import java.io.*;
2+
// Java program to print largest contiguous array sum
3+
import java.util.*;
4+
5+
class Kadanes
6+
{
7+
public static void main (String[] args)
8+
{
9+
int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};
10+
System.out.println("Maximum contiguous sum is " +
11+
maxSubArraySum(a));
12+
}
13+
14+
static int maxSubArraySum(int a[])
15+
{
16+
int size = a.length;
17+
int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
18+
19+
for (int i = 0; i < size; i++)
20+
{
21+
max_ending_here = max_ending_here + a[i];
22+
if (max_so_far < max_ending_here)
23+
max_so_far = max_ending_here;
24+
if (max_ending_here < 0)
25+
max_ending_here = 0;
26+
}
27+
return max_so_far;
28+
}
29+
}

‎LongestPath/C++/LongestPath.cpp‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
#include<bits/stdc++.h>
2+
using namespace std;
3+
vector<vector<int>> g;
4+
int dist[1000006];
5+
int vis[1000006];
6+
int bfs(int source){ // returns furthest node from source node
7+
memset(vis,0,sizeof(vis));
8+
memset(dist,0,sizeof(dist));
9+
queue<int> q;
10+
q.push(source);
11+
int last=source;
12+
while(!q.empty()){
13+
int front=q.front();
14+
q.pop();
15+
if(vis[front]) continue;
16+
last=front;
17+
for(auto i : g[front]){
18+
if(vis[i]) continue;
19+
dist[i]=dist[front]+1;
20+
q.push(i);
21+
}
22+
}
23+
return last;
24+
}
25+
int longest_path(int nodes,int edges){ // returns length of longest path
26+
int source=bfs(1);
27+
return dist[bfs(source)];
28+
}
29+
int main(){
30+
int nodes,edges;
31+
cin>>nodes>>edges;
32+
g.resize(nodes+1);
33+
for(int i=0;i<edges;i++){
34+
int u,v;
35+
cin>>u>>v;
36+
g[u].push_back(v);
37+
g[v].push_back(u);
38+
}
39+
int ans=longest_path(nodes,edges);
40+
cout<<ans<<endl;
41+
}

‎MergeSort/C++/MergeSort.cpp‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
#include <iostream>
2+
3+
using namespace std;
4+
5+
// A function to merge the two half into a sorted data.
6+
void Merge(int *a, int low, int high, int mid)
7+
{
8+
// We have low to mid and mid+1 to high already sorted.
9+
int i, j, k, temp[high-low+1];
10+
i = low;
11+
k = 0;
12+
j = mid + 1;
13+
14+
// Merge the two parts into temp[].
15+
while (i <= mid && j <= high)
16+
{
17+
if (a[i] < a[j])
18+
{
19+
temp[k] = a[i];
20+
k++;
21+
i++;
22+
}
23+
else
24+
{
25+
temp[k] = a[j];
26+
k++;
27+
j++;
28+
}
29+
}
30+
31+
// Insert all the remaining values from i to mid into temp[].
32+
while (i <= mid)
33+
{
34+
temp[k] = a[i];
35+
k++;
36+
i++;
37+
}
38+
39+
// Insert all the remaining values from j to high into temp[].
40+
while (j <= high)
41+
{
42+
temp[k] = a[j];
43+
k++;
44+
j++;
45+
}
46+
47+
48+
// Assign sorted data stored in temp[] to a[].
49+
for (i = low; i <= high; i++)
50+
{
51+
a[i] = temp[i-low];
52+
}
53+
}
54+
55+
// A function to split array into two parts.
56+
void MergeSort(int *a, int low, int high)
57+
{
58+
int mid;
59+
if (low < high)
60+
{
61+
mid=(low+high)/2;
62+
// Split the data into two half.
63+
MergeSort(a, low, mid);
64+
MergeSort(a, mid+1, high);
65+
66+
// Merge them to get sorted output.
67+
Merge(a, low, high, mid);
68+
}
69+
}
70+
71+
int main()
72+
{
73+
int n, i;
74+
cout<<"\nEnter the number of data element to be sorted: ";
75+
cin>>n;
76+
77+
int arr[n];
78+
for(i = 0; i < n; i++)
79+
{
80+
cout<<"Enter element "<<i+1<<": ";
81+
cin>>arr[i];
82+
}
83+
84+
MergeSort(arr, 0, n-1);
85+
86+
// Printing the sorted data.
87+
cout<<"\nSorted Data ";
88+
for (i = 0; i < n; i++)
89+
cout<<"->"<<arr[i];
90+
91+
return 0;
92+
}

0 commit comments

Comments
 (0)