Skip to content

Commit 77a6e37

Browse files
amangit1314amangit1314
committed
#Modification 88
1 parent eb24ee8 commit 77a6e37

6 files changed

Lines changed: 249 additions & 70 deletions

File tree

‎README.md‎

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,7 @@
11

22
<<<<<<< HEAD
3-
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[177/450]
4-
=======
5-
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[176/450]
6-
>>>>>>> a2e92505513ed15ccc77cec7c41b3d05ce231144
3+
# Java Placement Preparation DSA CRACKER SHEET 💻🦸‍♂️🐱‍👤[178/450]
4+
75
🐼 This is a full fled-ged repository for learning Java Language & DSA for Placement Preparation.
86

97
💪 Here you can find the solution's of **_450 Questions of (Data Structure & Algorithms Cracker Sheet)_** By **LOVE BABBAR** Bhaiya.

miscellaneous/MergeKArr.java renamed to heap/Problem_06.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
1-
package miscellaneous;
1+
package heap;
22

33
import java.util.Arrays;
44

55
// Problem Title => Merge K sorted Array's given in form of Matrix[n*n]
6-
public class MergeKArr {
6+
public class Problem_06 {
77

88
static void merge(int[][] mat, int k, int[] temp){
99
int i,j,t=0;

‎heap/Problem_06_2.java‎

Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
package heap;
2+
3+
// Problem Title => Java program to merge k sorted arrays of size n each.
4+
5+
// A min heap node
6+
class MinHeapNode {
7+
// The element to be stored
8+
int element;
9+
10+
// index of the array from which the element is taken
11+
int i;
12+
13+
// index of the next element to be picked from array
14+
int j;
15+
16+
public MinHeapNode(int element, int i, int j) {
17+
this.element = element;
18+
this.i = i;
19+
this.j = j;
20+
}
21+
}
22+
23+
// A class for Min Heap
24+
public class Problem_06_2 {
25+
26+
// Array of elements in heap
27+
MinHeapNode[] harr;
28+
29+
// Current number of elements in min heap
30+
int heap_size;
31+
32+
// Constructor: Builds a heap from a given array a[] of given size
33+
public Problem_06_2(MinHeapNode[] a, int size) {
34+
heap_size = size;
35+
harr = a;
36+
int i = (heap_size - 1)/2;
37+
while (i >= 0) {
38+
MinHeapify(i);
39+
i--;
40+
}
41+
}
42+
43+
// A recursive method to heapify a subtree with the root at given index This method assumes that the subtrees are already heapified
44+
void MinHeapify(int i) {
45+
int l = left(i);
46+
int r = right(i);
47+
int smallest = i;
48+
if (l < heap_size && harr[l].element < harr[i].element)
49+
smallest = l;
50+
if (r < heap_size && harr[r].element < harr[smallest].element)
51+
smallest = r;
52+
if (smallest != i) {
53+
swap(harr, i, smallest);
54+
MinHeapify(smallest);
55+
}
56+
}
57+
58+
// to get index of left child of node at index i
59+
int left(int i) { return (2*i + 1); }
60+
61+
// to get index of right child of node at index i
62+
int right(int i) { return (2*i + 2); }
63+
64+
// to get the root
65+
MinHeapNode getMin() {
66+
if(heap_size <= 0) {
67+
System.out.println("Heap underflow");
68+
return null;
69+
}
70+
return harr[0];
71+
}
72+
73+
// to replace root with new node "root" and heapify() new root
74+
void replaceMin(MinHeapNode root) {
75+
harr[0] = root;
76+
MinHeapify(0);
77+
}
78+
79+
// A utility function to swap two min heap nodes
80+
void swap(MinHeapNode[] arr, int i, int j) {
81+
MinHeapNode temp = arr[i];
82+
arr[i] = arr[j];
83+
arr[j] = temp;
84+
}
85+
86+
// A utility function to print array elements
87+
static void printArray(int[] arr) {
88+
for(int i : arr)
89+
System.out.print(i + " ");
90+
System.out.println();
91+
}
92+
93+
// This function takes an array of arrays as an argument and All arrays are assumed to be sorted.
94+
// It merges them together and prints the final sorted output.
95+
static void mergeKSortedArrays(int[][] arr, int k) {
96+
MinHeapNode[] hArr = new MinHeapNode[k];
97+
int resultSize = 0;
98+
for(int i = 0; i < arr.length; i++) {
99+
MinHeapNode node = new MinHeapNode(arr[i][0],i,1);
100+
hArr[i] = node;
101+
resultSize += arr[i].length;
102+
}
103+
104+
// Create a min heap with k heap nodes.
105+
// Every heap node has first element of an array
106+
Problem_06_2 mh = new Problem_06_2(hArr, k);
107+
108+
// To store output array
109+
int[] result = new int[resultSize];
110+
111+
// Now one by one get the minimum element from min heap and replace it with next element of its array
112+
for(int i = 0; i < resultSize; i++) {
113+
// Get the minimum element and store it in result
114+
MinHeapNode root = mh.getMin();
115+
result[i] = root.element;
116+
117+
// Find the next element that will replace current root of heap.
118+
// The next element belongs to same array as the current root.
119+
if(root.j < arr[root.i].length)
120+
root.element = arr[root.i][root.j++];
121+
// If root was the last element of its array
122+
else
123+
root.element = Integer.MAX_VALUE;
124+
125+
// Replace root with next element of array
126+
mh.replaceMin(root);
127+
}
128+
129+
printArray(result);
130+
}
131+
132+
// Driver code
133+
public static void main(String[] args){
134+
int[][] arr= {
135+
{2, 6, 12, 34},
136+
{1, 9, 20, 1000},
137+
{23, 34, 90, 2000}
138+
};
139+
140+
System.out.println("Merged array is :");
141+
mergeKSortedArrays(arr,arr.length);
142+
}
143+
}

‎miscellaneous/MergeKArr2.java‎

Lines changed: 0 additions & 8 deletions
This file was deleted.

‎miscellaneous/QuickSort.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package miscellaneous;
2+
3+
import java.util.Scanner;
4+
import java.util.concurrent.ThreadLocalRandom;
5+
6+
public class QuickSort {
7+
int count = 0;
8+
9+
public static int getRandomValue(int Min, int Max) {
10+
// Get and return the random integer within Min and Max
11+
return ThreadLocalRandom.current().nextInt(Min, Max + 1);
12+
}
13+
14+
// A utility function to swap two elements
15+
static void swap(int[] arr, int i, int j) {
16+
int temp = arr[i];
17+
arr[i] = arr[j];
18+
arr[j] = temp;
19+
}
20+
21+
// A utility function to print array of size n
22+
static void printArray(int[] arr) {
23+
int n = arr.length;
24+
for (int i = 0; i < n; ++i)
25+
System.out.print(arr[i] + " ");
26+
System.out.println();
27+
}
28+
29+
public static void main(String[] args) {
30+
int Min = 1, Max = 100;
31+
32+
Scanner sc = new Scanner(System.in);
33+
int n = sc.nextInt();
34+
35+
int[] arr = new int[n];
36+
for (int i = 0; i < n; i++) {
37+
arr[i] = getRandomValue(Min, Max);
38+
System.out.print(arr[i] + " ");
39+
}
40+
System.out.println();
41+
42+
System.out.println("Given Array");
43+
printArray(arr);
44+
}
45+
}

‎sortingAlgorithms/QuickSort.java‎

Lines changed: 57 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -1,91 +1,92 @@
1-
package sortingAlgorithms;
1+
package sortingAlgorithms;
22

3-
import java.io.*;
3+
import java.util.Scanner;
4+
import java.util.concurrent.ThreadLocalRandom;
45

5-
public class QuickSort{
6+
public class QuickSort {
7+
static int count = 0;
8+
9+
public static int getRandomValue(int Min, int Max) {
10+
// Get and return the random integer within Min and Max
11+
return ThreadLocalRandom.current().nextInt(Min, Max + 1);
12+
}
613

714
// A utility function to swap two elements
8-
static void swap(int[] arr, int i, int j)
9-
{
15+
static void swap(int[] arr, int i, int j) {
1016
int temp = arr[i];
1117
arr[i] = arr[j];
1218
arr[j] = temp;
19+
// count++;
1320
}
1421

15-
/* This function takes last element as pivot, places
16-
the pivot element at its correct position in sorted
17-
array, and places all smaller (smaller than pivot)
18-
to left of pivot and all greater elements to right
19-
of pivot */
20-
static int partition(int[] arr, int low, int high)
21-
{
22-
23-
// pivot
22+
// Function to do left and right partition in the array
23+
static int partition(int[] arr, int low, int high) {
2424
int pivot = arr[high];
2525

26-
// Index of smaller element and
27-
// indicates the right position
28-
// of pivot found so far
2926
int i = (low - 1);
3027

31-
for(int j = low; j <= high - 1; j++)
32-
{
33-
34-
// If current element is smaller
35-
// than the pivot
36-
if (arr[j] < pivot)
37-
{
38-
39-
// Increment index of
40-
// smaller element
28+
for (int j = low; j <= high - 1; j++) {
29+
if (arr[j] < pivot) {
4130
i++;
4231
swap(arr, i, j);
32+
count++;
4333
}
4434
}
4535
swap(arr, i + 1, high);
4636
return (i + 1);
4737
}
4838

49-
/* The main function that implements QuickSort
50-
arr[] --> Array to be sorted,
51-
low --> Starting index,
52-
high --> Ending index
53-
*/
54-
static void quickSort(int[] arr, int low, int high)
55-
{
56-
if (low < high)
57-
{
58-
59-
// pi is partitioning index, arr[p]
60-
// is now at right place
39+
void quickSort(int[] arr, int low, int high) {
40+
if (low < high) {
41+
// pi is partitioning index, arr[p] is now at right place
6142
int pi = partition(arr, low, high);
6243

63-
// Separately sort elements before
64-
// partition and after partition
44+
// Separately sort elements before partition and after partition
6545
quickSort(arr, low, pi - 1);
6646
quickSort(arr, pi + 1, high);
6747
}
6848
}
6949

70-
// Function to print an array
71-
static void printArray(int[] arr, int size)
72-
{
73-
for(int i = 0; i < size; i++)
50+
// A utility function to print array of size n
51+
static void printArray(int[] arr) {
52+
for (int j : arr) System.out.print(j + " ");
53+
System.out.println();
54+
}
55+
56+
public static void main(String[] args) {
57+
int Min = 1, Max = 100;
58+
59+
Scanner sc = new Scanner(System.in);
60+
int n = sc.nextInt();
61+
62+
int[] arr = new int[n];
63+
for (int i = 0; i < n; i++) {
64+
arr[i] = getRandomValue(Min, Max);
7465
System.out.print(arr[i] + " ");
66+
}
67+
68+
System.out.println();
69+
System.out.println();
70+
71+
System.out.println("Given Array: ");
72+
printArray(arr);
7573

7674
System.out.println();
77-
}
7875

79-
// Driver Code
80-
public static void main(String[] args)
81-
{
82-
int[] arr = { 10, 7, 8, 9, 1, 5 };
83-
int n = arr.length;
76+
QuickSort qs = new QuickSort();
77+
qs.quickSort(arr, 0, n - 1);
8478

85-
quickSort(arr, 0, n - 1);
8679
System.out.println("Sorted array: ");
87-
printArray(arr, n);
88-
}
89-
}
80+
printArray(arr);
9081

91-
// This code is contributed by Aman Soni
82+
System.out.println();
83+
84+
System.out.println("Sorted array as input: ");
85+
printArray(arr);
86+
87+
System.out.println();
88+
89+
System.out.println("Operations: ");
90+
System.out.println(count);
91+
}
92+
}

0 commit comments

Comments
 (0)