Partioning an Array | Time and Space | Data Structure and Algorithms in JAVA
ฝัง
- เผยแพร่เมื่อ 6 ก.พ. 2025
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we have explained how to partion an array in Time and Space in Java.
For a better experience and more exercises, VISIT: www.pepcoding....
#pepcoding #java #programming
Have a look at our result:
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Join us on Telegram: t.me/joinchat/...
Watched the tutorial it was at it's best. One thing I would like to mention that, this solution will work perfectly if pivot value is not present in given array, as mentioned in problem but if pivot value is present in array itself, it will not partition properly. i.e. arr = {8,5,1,3,7,6,2,9}, pivotValue = 6, output should be : {5,1,3,2,6,8,7,9} but we will get output : {5,1,3,6,2,8,7,9}.
So we just need to maintain pivot index and at last swap if any element present at j is less than our pivot value.I have added few lines in already implemented code.
public class PartitioningArray {
public static void main(String[] args) {
int[] array = {8,5,1,3,7,6,2,9};
int pivot = 6;
partition(array,pivot,0,array.length-1);
System.out.println(Arrays.toString(array));
}
private static void partition(int[] array, int pivot,int low,int high) {
// we have start point = 0, and end point = arr.length
// We will take two pointers i & j ,
// items from 0 to j-1 pivot
int pivotIndex = -1;
int i = low;
int j = low;
while (i array[j-1]){
swap(array,pivotIndex,(j-1));
}
}
public static void swap(int[] arr, int i, int j) {
System.out.println("Swapping " + arr[i] + " and " + arr[j]);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Please let me know If I am wrong anywhere.
bhai itna bda ku bna dia tumne
sir k code m bs ek chhota sa change krna hai bs
p(int a[],int n,int pivot)
{
int temp=0;
int i=0;
int j=0;
while(i
Yes. i checked your analysis
this code will fail if in the end, the output consists of these elements somewhere {6, 5, 5} in case of 6 pivot
(what if there are 2 or more elements, only one if block cant take care of that)
also in your code, you have maintained a pivot index according to fault in algo, the smaller than pivot number will end up in front of pivot and you've checked pivot and arr[j - 1] (which should've been arr[j + 1] )
Amazing explanation sir, I haven't found such a great explanation anywhere else on youtube. Thank your sir for teaching us in such an amazing way for free.
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
th-cam.com/users/Pepcodingabout?view_as=subscriber
@@Pepcoding This algo fails at this input:
arr size 7
7 3 8 -2 6 5 9
pivot: 6
expected output: 3 -2 5 6 7 8 9
actual output: 3 -2 6 5 7 8 9
in fact it'll fail in all cases where number smaller than pivot value is present after pivot it self
i.e.
6
10 4 8 5 1 3
5
actual output 4 5 1 3 8 10
@@pranjalbajpai9956 we don't need to sort the sort the array.. the actual output is true and it is what expected... Just separate them..don't sort the separated elements
Itni Shiddat se agar koi pada sakta he to vo hai sumeet malik... :)
Hamesha video dekh k lagta hai ki ye college me ku nahi padaya gaya..
but fortunate to watch your content now as well, ku ki mujhe abi b kisi aur ki explanation samajh nahi aati hai :)
Wish PepCoding becomes India's best Education/Coding Platform
Best Mentor And Teacher Ever
Thankyou beta!
kassh mere college mai apke jese teacher hote to alag hi baat hoti .......kher apka explaination to alag hi level ka hai thanku you so much sir
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
@@Pepcoding ok i will give
aap mahaan ho sir thank you for this video
Aap logo ki he vja se hu, jo bhi hu main aaj😊
Keep loving and keep supporting🙏
bhai isse acha nhi hoo sakta aur....bahut underrated channel hai...iss channel ka video jyada view ka haqdar hai
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Sumit sir, your explanation and teaching skill is magnificent and highly adorable 🙏🙏... Thanks to u sir for making a perfect grip for me over data structure
Thanks for letting us know these driven questions as well , that is so helpful. It will be great if you can tell these types of driven questions as well whenever explaining any concept. Thank you so much.
amazing expeprience sir great concept and well explained
you are a brilliant teacher sir
Great explanation Sir...
Thanks and welcome. Please subscribe and share the channel around.
i understood every point! thnku so much for the best content sir🙌🙌
Most welcome 😊. Can you write about our channel on your facebook or linkedin?
It's very helpful video
kaise sir kaise itna aacha explain krr lete h
wah mja aa gya
We are glad that you liked it. keep watching and hit the notification bell icon to be updated.
Don't forget to follow us on Instagram instagram.com/pepcoding/
Excellent explanation!! Thank you sumeet sir! ❤️❤️
Gem content. ❤️
Glad it helped!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
Neat and clean explanation sir👍👍👍
Thankyou beta!
I am glad you liked it. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Hi, I love watching your videos, I was wondering if we can use this approach to segregate odd-even nodes in linked lists?
Very nicely explained...thank you very much!!!
Best
// sir I guess idhar pivot zaroori nahi hai ki sort ho jaaye. only when the pivot is the last element to get swapped it gets sorted
public static void partition(int arr[], int pivot){
int j = 0 ;
int i = 0 ;
while(i < arr.length){
if(arr[i]
wonderful work
Keep learning, Keep growing and keep loving Pepcoding!😊
you r best
Thankyou beta!
I am glad you liked it. I also hope that you are watching till the end and trying to understand the what, how, and especially why of the problem. If you like our efforts, will you like to review us here - g.page/Pepcoding/review?rc
Tq, sumeet sir again🙏
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Awesome
Thankyou beta!
I am glad you liked it. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Great explanation sir
Thankyou beta!
keep watching and keep learning😊
Sir ek baat ar agar mujhe big tech giant me Jana h to agar me codchef ya codforce par rating aach kar lu chane bash jayenge
Bhagwan wale guru ho ap
Thanks beta ji !! bhut bddi btt
Nice explanation ..
Ty Sir:)
So nice of you and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Done!
Bhaiya , please tell me when pepcoding is hiring for SDE/SE role via NADOS :p
I wanna apply........
sir bas partition hi karna hoga, like koi specific order ko follow nahi karna hoga toh iske multiple algorithms ho sakte hai na? maine aise solve kiya aur less swaps me answer aa raha hai, but in a different order.
int i = 0, j = a.length - 1;
while (i= pivot && a[j]
Beta, I regret to inform you that, I won't be able to take the personal doubts of each and every student over here. Therefore, we have a premium facility available for the students in which you can get the 12 hours doubt support facility. Jisme aap agar kisi bhi question main kahin bhi faste ho to aap doubt support par reach kar skte ho aur aapko TA assign ho jayega and you can get your doubt resolved from them.
naruto aise bhi kar sakte hai... :
void Partition(int arr[] , int n , int num) //basic DNF se ho gaya O(n) mai
{
int start=0 , end=n-1;
int temp;
while(start < end)
{
if(arr[start] < num)
{
start++;
}
if(arr[start] > num)
{
temp = arr[end];
arr[end] = arr[start];
arr[start] = temp;
end--;
}
}
}
No it fails for this case
{ 2 5 3 1 4 7 8 6}
Pivot=7
maine bhi aise hi kiya... shi h ya nhi bta skte ho ??
@@anubhavgupta4412 hold a little change in sir's function
p(int a[],int n,int pivot)
{
int temp=0;
int i=0;
int j=0;
while(i
arr=[7,9,8,3,2,6,5,3] yadi me pivot ko 6 manu to output ye aa raha h sir 3 2 6 5 3 8 7 9 isme 5 6 se chhota he to 6 (pivot) ke left me ana chaiye lkn nahi aa raha !!
void partition(int a[],int n,int pivot)
{
int i=0,j=0;
while(ipivot)
i++;
else
{
swap(a[i],a[j]);
i++;
j++;
}
}
}
after this code if m trying to print the array than i m getting op =[3 2 6 5 3 8 7 9] which is wrong according to me !! and i have taken pivot element as "6" please help me !
I m facing same problem ...if u have got the solution help me out
@@anubhavgupta4412 okay bro just try to implement the another one !
@@sunnykakrani7830dusra wala konsa bhai ???
@@sunnykakrani7830 ??
p(int a[],int n,int pivot)
{
int temp=0;
int i=0;
int j=0;
while(i
***summary***
if ith element is greater do nothing and then just i++
if ith element is smaller swap and then just i++, j++
three really important regions
i to end -> unknown
0 to j - 1 -> > pivot
It gives wrong output with input - 5 5 4 3 2 1 3.
Actual output - 3 2 1 4 5 .
Expected - 2 1 should be on left of 3
I think one swap is missing in code.
bhai ek baar dry run karke dekho
you are doing some mistake, the actual output is correct
Ye Algo Bas Partion Karta hai, sort nahi karta hai. So Order Matter Nahi karega but voh Pivot value se chote wale left mein aur badhe right mein aa jaayenge. (Order Kuch Bhi Ho Sakta hai)
ye meme clips ki vol low rakha kro
beech me ek dum se high vol me aa jati hai
Point noted.
Sir 2 alag array bnayenge ek me jo bda hai usko dalnge ek me jo chota hai usko dalenge and usko merge ker denge reverse print ker denge ye bhi shi hai na recursion me jate time count ker lenge kitne bde hai kitne chotr hai utne ka arraysize bna lenge uske bad en dono array me recursion me return kerte time bde chote value ko add ker denge uske bad merge ker denge aur reverse print ker denge
Haan Kar sakte hai but, ye space aur time consuming hoga for Large Data. Sir ne jo Algo Bataya voh O(N) mein kar dega and just using pointers.
@@gauravsingh4355 O(1)*
Please help with correction where the pivot present in the array.
sorry working
This algo fails at this input:
arr size 7
7 3 8 -2 6 5 9
pivot: 6
expected output: 3 -2 5 6 7 8 9
actual output: 3 -2 6 5 7 8 9
in fact it'll fail in all cases where number smaller than pivot value is present after pivot it self
i.e.
6
10 4 8 5 1 3
5
actual output 4 5 1 3 8 10
You can use dnf sort also
Sir ye question site se gayab h
will be update soon
this solution fails for input 5
7 3 1 9 2 3. Its giving the output 3 1 2 9 7.
Sir partitioning ki ek aur bhi algorithm hoti hai naa, pehle pivot ko uski sahi position pe rakh de(by counting no. of elements less than pivot), uske baad 2 pointer rakhe , ek starting mein and ek end mein
while(i< j){
if(arr[i] < pivot){
i++
}else if(arr[j] > pivot{
j--
}else{
swap(arr[i],arr[j])
i++
j--
}
}
ye bhi shi chalegi na sir??
hanji
why so less views? its very saddening :(
One of the sexiest and lusty explanatio n ever!!😅😅😂
Sir itna high knowledge kaise each point has a why
will tell you a little secret practice more and more :)
sir please run this code for input
-5 6 2 1 5 0 6 10
and pivot - 5
it is giving result - -5 2 1 5 0 6 6 10 which is wrong
please help sir to solve this doubt
visit naods.pepcoding.com
You can post such queries on community tab.
for the input 3, 2, 1, 5, 6, 4 and pivot being 6, the logic produces 3, 2, 1, 5, 6, 4 which is wrong
Really? I will also check.
I checked. it is giving wrong answer.
I simply extracted out the common part i.e. i++ :
public static void paritionArr(int[] arr, int totalLength, int pi) {
int i = 0, j = 0;
while(i < totalLength) {
if(arr[i] < pi) {
swap(arr, i, j);
j++;
}
i++;
}
}
This one seems to work fine for the mentioned input.
Sir pr iss method se pivot, less and greater no k bich m nhi aayega, a simple change could do it.guys look at this
p(int a[],int n,int pivot)
{
int temp=0;
int i=0;
int j=0;
while(i