Sort An array using Recursion
Vložit
- čas přidán 7. 09. 2024
- Sorting and array using Recursion by using Induction-Hypothesis and Base condition Approach.
Pdf notes and code: / 38605857 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
I can't thank you enough for making these videos. I completed yours dynamic programming playlist and gained so much knowledge. I was once rejected in interview because i didn't know how to approach DP problems. But after watching your videos , I gained massive confidence and also got placed. Thanks a lot
Amazon
@Himalayan drifter google
@Himalayan drifter bhindi market
@@akashbhadouria6727 😂
@@Lalit_Shirsath System Administrator at Thakur Prasad Sao & Sons Pvt. Ltd.
Today I got selected in Flipkart all because of your videos Aditya!
Besides learning technical stuff, I got to learn from you on how to handle and approach complex problems.
Thanks a lot!
I really owe you a lot, can't msg on LinkedIn since you haven't accepted my request but I'm gonna ping you as soon as I join to thank you :)
Welcome onboard buddy 😅❤️
Glad I could help you in our journey To Flipkart !!
pleae guide
@@TheAdityaVerma please make payslist on tree and graph as well ,Your teaching style helps to grasp the concept easily & to remember it for a long time.Thank you !!
Every man must bow, every tongue must confess, this is the best recursion tutorial and Aditya is the greatest teacher of all time.
At 17:44, we can also use a binary search (recursive/iterative) to find the position in O(logN) since the left subarray is sorted. This is the most optimized version of insertion sort using recursion. Amazing explanation!
Yet, the overall time complexity will be O(n^2)
@@amitmahato4876 Practically, complexity is only the first thing you check. You have to improve overall performance of the code and asymptotic complexity is only a broad-level analysis. My code is O(N^2) but it will still be much faster than yours :)
@@matrixtoogood5601 You r right bro
@@matrixtoogood5601 share your code once bro
no man if to insert an element, in the worst case you can have have to shift all elements to make place for the given element, this is not about finding an element, it is about inserting an element in-place in a array or vector.
Boss Graph ki playlist ayegi na to lagra apka channel alag hi level pai chala jayega (graph k hard questions include karna )
It has been one year may be you were placed somewhere but the playlist didn't come yet😅😅😅
@@chiragjaiswal9387 aur bhai? xD
@@chiragjaiswal9387 student of Sri Aurobindo Vidyamandir, U remember me ?
its been 2 yrs still that series didn't come . Aditya Verma bhiya where are you ???????
I don't have words to explain how I am feeling after going through this video. Never ever thought of sorting an array using recursion. I cannot thank you enough Aditya... Every video I watched of urs taught me a new concept...
Aditya you really helped me to grasp the concept of recursion. I know recursion but after certain period of time I found myself in a position where I was not able to create a working code using recursion. Yes, I will continue to see your further lecture on recursion.
I am sharing the code which you explained in this video, so that other people can visualize more by running code on terminal.
Understand the recursion flow:
#include
using namespace std;
void InsertElem(vector &v, int tmp)
{
cout
Hey Aditiya, love your content. It's very good. I have been following you for a month now. I have a suggestion for you, If it is possible then in the description of every video, you should put at least 5 similar questions, based on the concept that you taught, from geek for geeks. That would really enhance our practice multiple folds.
I agree
agreed that will definitely increase the outcome of the video. This will help us to apply the concept by ourself in various question.
You don't have to put the questions in every video just put them in the videos which are very important.
I always struggled thinking about recursion and how it keep tracks of the variable state and kind of lost in that space. But the way you explained makes it look a hell easier now with focused mind. Thanks Aditya
The best way to learn is : while Mr. Verma is teaching parallelly you also use pen paper and write . Then you will get very clear picture.
I watched 2 times, but it was blur 50 -60 % .. I took pen paper and wrote then Trust me : in just one shot i typed the entire code. Thanks Aditya!
This is Insertion Sort using Recursion :)
yes
no paid content can also teach us this awesomely as u do.. bhai next series on backtracking
i think this is the best playlist of recursion i have seen i think this is last becoz explained this is very simple manner of how to think about any recursive function and how to implement that thank you sir for such a great video
//Thanku Aditya sir -----> for removing the fear of recursion from our head
#include
using namespace std;
void insert(vector&a,int k){
int n=a.size();
//base case
if(n==0 || a[n-1]
Finally...a guy who knows what he's teaching.
@theprogrammer change array to vector
thanks for such an amazing explanation, Here's the python code for this problem:
def arr_insert(a,b):
if len(a)==0 or b>=a[len(a)-1]:
a.append(b)
return
temp=a.pop()
arr_insert(a,b)
a.append(temp)
def arr_sort(a):
if len(a)
how abt bubble sort or selection sort using length=len(are)
#include
using namespace std;
void Insert(vector &v, int temp){
if(v.size() == 0 || v[v.size()-1]
Thanks
Thanks !
Thanks for amazing explanation :) Kudos to learning recursion. Enclosed java Solution:
package recursion;
import java.util.ArrayList;
import java.util.List;
public class SortAnArray {
public static void main(String[] args) {
List l = new ArrayList();
l.add(1);
l.add(0);
l.add(5);
l.add(2);
l = sort(l);
for(int i : l)
System.out.println(i);
}
private static List sort(List l) {
if(l.size() == 1)
return l;
//hypothesis
Integer temp = l.get(l.size()-1);
l.remove(l.size()-1);
l = sort(l);
//induction
return l = insert(l, temp);
}
private static List insert(List l, int i) {
if(l.size() == 0 || i >= l.get(l.size()-1))
{
l.add(i);
return l;
}
//hypothesis
int val = l.get(l.size() - 1);
l.remove(l.size()-1);
l = insert(l, i);
//induction
l.add(val);
return l;
}
}
I did got Time Limit Exceeded when I submitted the code for this approach on Leetcode. But the satisfaction lied in the fact that I understood recursion, implemented it and wrote the code on my own. Thanks a lot for an amazing content! :)
Recursion always need optimization..follow his DP series..
void insort(vector&v, int temp){
if(v.size()==0 || v[v.size()-1]< temp){
v.push_back(temp);
return;
}
int value=v[v.size()-1];
v.pop_back();
insort(v,temp);
v.push_back(value);
}
void sort(vector&v){
if(v.size()==0) return;
int temp=v[v.size()-1];
v.pop_back();
sort(v);
insort(v, temp);
}
int main() {
vectorv;
v.push_back(2);
v.push_back(1);
v.push_back(5);
v.push_back(4);
sort(v);
for(int i=0; i
Bro i will never hesitate calling u the best teacher of recursion
Aditya I like you explanations and thank you.. I noticed in this video that you started with the question of "sorting an ARRAY" and by the time you started discussing insert function you moved to speaking about sorting a vector.
Java code for recursiely sorting an arrar:
public class Main {
public static void main(String[] args) {
ArrayList arr = new ArrayList(
Arrays.asList(3,2,1,4,5,6,7)
);
arr = sort(arr);
System.out.println(arr);
}
public static ArrayList sort(ArrayList arr){
if(arr.size()==1){
return arr;
}
int temp = (int)arr.get(arr.size()-1);
arr.remove(arr.size()-1);
arr = sort(arr);
arr = insert(arr,temp);
return arr;
}
public static ArrayList insert(ArrayList arr,int temp){
if(arr.size()==0 ){//|| (int)arr.get(arr.size()-1)temp){
arr.add(temp);
return arr;
}else if((int)arr.get(0)>=temp){
arr.add(0,temp);
return arr;
}else if((int)arr.get(arr.size()-1)
thanks
Thanks man video wasn't clear to me but I'll figure it out form the code
Thanks for this.now I got the clear picture 👍
Thanks I tried by myself ,and couldn't figure out if should use a list or not
thank you bro
Your way of teaching is just awesome. Thanks for your efforts.
This is one of the most conceptual videos I have ever seen. Kudos to you, man!
sir program k sath uska time complexity v discuss kr dia kro plz... rest all is awesome😍😍😍😍
What would be the time complexity of this problem? Anyone wants to guess?
@@vishalc6658 O(n^2) i guess
That's an insertion sort.. With recursion stack space complexity
Just wanna to say l0ve you Aditya Verma.... what confidence I gained in this question was just awesome......... BiG tHanks
After a long time .. after seeing this, maza aaya.. Thanks for teaching in a different way
I implemented bubble sort in recursion.... Thanks to you sir..
leetcode ka example poora dry run karke khud se samajh aaya code ka logic
thank you bhai !!
for those who are in need of Python code :-
arr = [2, 3, 5, 4, 10, 3, 4, 5, 2, 1, -10, 0]
class Sorting:
def insert(self, arr, temp):
if len(arr) == 0 or arr[len(arr) - 1]
this question may seem silly, but when i tried your code and made a change where i defined n=len(arr) and replace len(arr) with n, and i get the error: list index out of range. can you tell me why is that?
@@prativadas4794
class Sorting:
def insert(self,arr,temp):
n=len(arr)
if n==0 or arr[n-1]
i have the same code but in gfg this in only passing two test cases :/
Bhai bohot bohot dhanyavaad, mujhe bohot ache se samaj aagaya yeh rha mera code
. Yeh bas mere reference keliye kuch galat hoto crct karo bhaiya....
#include
using namespace std;
Void insert(vector &v, int val)
{
//base case
if(v.size() ==0 || v[v.size()-1]
"Increasing, Decreasing, Ascending, Descending Orders" are relative. That's a great point to note. Sometimes, we know these observations but neglect them solving the problem. Awesome Observation Sir...🙌🙌
Hey can you tell me in short what does hypothesis and induction means?
@@MilindGupta hypothesis is time when we write our main function and induction is where we decided how do we want to print our function
example in "print the array from 1 to n"
we solve it in two ways first printing from "1 to n" and then "n to 1" .... if you have watched both the video then you must have seen that just by changing the print position we were able to print it differently . So that's what the induction is
Hope this help!
this really feels like magic
bhai msst padhata hai tu sach mai. ek alag way mai sochna sikhaata hai . thanks yaar
bro, you are god of programming
def insert(arr, temp):
size = len(arr)
# base - if arr is empty or we need to add in the end
if size == 0 or arr[size -1 ] sorting the smaller array
sort_arr(arr)
# induction -> inserting the element in the right position
insert(arr, temp)
God-Level Explanation
code:
#include
using namespace std;
#include
void insert(vector &v, int value){
if(v.size()==0 || v[v.size()-1]
Happy Teachers days Bhaiya ❤️❤️❤️❤️❤️really you are one of best Teacher please make more video on graph and others stuff for placement
3
This was a tuff video, it means we are growing.🔥
Hi Aditya, your Videos are great and they are helping me a lot. Please keep on posting more content on your channel and interesting problems.
Thank you Vatsala, I will !!
Excellent explanation with full patience !!!
Hey can you tell me in short what does hypothesis and induction means?
@@MilindGupta I will try my best to explain :
Hypothesis - Call your function but with smaller valid input, you do it to make sure if your function works let suppose for N then it will work for N-1. Recursively it will work till that smallest valid input and gives you desired output.
Induction - After your hypothesis returns you a valid output then you can logically do some other stuff in induction.
Base Condition - This condition will ensure you reach that valid smallest input which you thought of and then you can start returning from there ! It is very crucial part in code, if you miss this then your code can end up in infinite recursive calls and can lead to memory overflow.
Hope this will help to some extent otherwise @Aditya Verma is here to rescue :)
code for this in java(try to solve and then refer, also let me know if any error is there)
import java.util.*;
public class MyClass {
public static void main(String args[]) {
LinkedList ll = new LinkedList();
ll.add(2);
ll.add(1);
ll.add(-7);
ll.add(5);
ll.add(33);
System.out.println(ll);
sort(ll);
System.out.println(ll);
}
static void sort(LinkedList ll){
if(ll.size() == 1)
return;
int lastEement = ll.removeLast();
sort(ll);
insert(ll, lastEement);
}
static void insert(LinkedList ll, int element){
if(ll.size() == 0 || ll.getLast()
Loved this, the flow 🌞
Thanks a lot...
Your thinking is next level..highly appreciated
I actually thought of another method to sort recursively and its relatively simpler. You work the other way round. you go sorting the array from the 1st element. So, the hypothesis becomes sort(a)-> a[0] + sort(a[1] to a[n-1]).
Now in this case the base condition becomes the stage in which you hit the last element of the array cuz there are no more elements to sort.
To form the induction you have the 1st and the 2nd element of the array. if the 1st elem > 2nd elem then before removing a[0] and sorting the rest of the array you swap a[0] and a[1] so that its sorted till the 1st position.
void sortr(vector &a, int i){
if(i==a.size()-1)
return;
if(a[i]>a[i+1])
swap(a[i], a[i+1]);
sortr(a, i+1);
}
it won't workk
#include
#include
#include
using namespace std;
void sortr(vector &a, int i){
if(i==a.size()-1)
return;
if(a[i]>a[i+1])
swap(a[i], a[i+1]);
sortr(a, i+1);
}
int main()
{
vectora={5,4,3,2,1};
sortr(a,0);
for(auto it:a)
cout
Killer content. Man I regret being this late🥴
arr=[2,3,1,8,5]
def sor(s,n):
if n==0:
return 1
#hypothesis
sor(s,n-1)
#induction
a=max(s)
print(a,end=" ")
s.remove(a)
sor(arr,5)
#updated as used recursion for finding max also:)
arr=[2,3,1,8,5]
def fun(a, i=0, largest=0):
if i==0:
largest=a[0]
if i==len(a):
return largest
if largest
hands down to your teaching skills🙌
31:29 Subscribe wagera karna he to kaar lena . He knows he is creating a difference.
For anyone new here, if you don't want to solve the induction problem (inserting an element in a sorted array) using recursion, then you can use *Binary Search* to find its correct position in sorted array. This will boil down the time complexity from O(N^2) to O(NlogN) and space complexity from O(N^2) to O(N) (if we are considering recursive stack space in the solution, if we're not then it'll be O(1) for both cases)
One more possible iterative way is possible :
We find the minimum element using 'for' loop & swap it with the 0th index. And then call the sort() function on the array of size = n - 1, where n is the size of the original array
When I see ur videos I will keep aside all my distraction calm that much intrest in ur vds
superb explaination.. I was able to write the perfect code in an single attempt.. Thanks for the lecture
Can you share the code here? I am getting some error
coded on by understanding logic gives tle : is there any changes required ?
class Solution {
public:
void insert(vector&nums,int ele){
// base case
if(nums.size()==0 || nums[nums.size()-1]
Thank you brother!!!
please make a video graphs as well, your way of teaching is amazing
This is some next level content.
def insert_in_sorted_array(arr, n):
# Base case: If n is the first element or the correct position is found
if n
12:14 Recursive leap of faith
Assasin's Creed ke side effects!!!!
@@workandearnwithshubhi9050 nah its miles morals (spiderman)effect
Thanks @Aditya Verma
Java impl
import java.util.ArrayList;
import java.util.List;
public class SortArray {
void sort(List arr){
if(arr.size() == 1){
return;
}
int lastVal = arr.remove(arr.size()-1);
sort(arr);
insert(arr, lastVal);
}
void insert(List arr, int elem){
if(arr.isEmpty() || arr.get(arr.size()-1)
Dude switch back to DP playlist format. That suits your!.
Code for C++:
#include
#include
using namespace std;
void sortArray(vector&);
void insertTemp(vector&,int);
int main() {
int n;
cin>>n;
vectorarr;
for(int i=0; i>val;
arr.push_back(val);
}
sortArray(arr);
for(int i=0; i
bro, this code didnt work on my compiler
@@ManishKumarSahu-jd2ww Is it showing any error or not giving correct output ? Because I checked it again it's working.
1. If you are running it on online compiler (onlinegdb) then do select language as C++.
2. First enter size of the array -> then enter elements of the array. It will work.
Hope this sorts your problem.
@@aakritisingh399 I was running it on vscode IDE. I tried many times, and even did some variations, but didn't work, everytime am getting wrong output😭. And also the stack question (just after this one) is giving wrong output, lol. I would be glad, if you could help with that one as well :)
I would try to run it on online IDE once.
Thank you so much for your suggestion!
Best part about your videos is that at least you try your best to explain...
bhai dp m ek topic add kardoge plzz..longest increasing subsequence..
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
self.sort(nums)
return nums
def sort(self,nums):
if len(nums)==1:
return
temp = nums.pop()
self.sort(nums)
self.insert(nums,temp)
def insert(self,nums,temp):
if len(nums)==0 or nums[-1]
Very very very informative and doubt clearing problem.
Thank you aditya bhaiya😍
I think in InSort method there is a correction if i am correct, you have to include the condition for first element in list That is =>
if(v.size() == 0 || v[v.size()-1] = temp){
v.insert(v.begin(),temp);
return;
}
=================================All Code===================================
#include
using namespace std;
void insort(vector& v,int temp)
{
if(v.size() == 0 || v[v.size()-1] = temp){
v.insert(v.begin(),temp);
return;
}
int val = v[v.size()-1];
v.pop_back();
insort(v,val);
return;
}
void sort(vector& arr)
{
if(arr.size() == 1){
return;
}
int temp = arr[arr.size() -1];
arr.pop_back();
sort(arr);
insort(arr,temp);
}
int main(){
vector arr = {3,2,4,5,10,1};
sort(arr);
for(int i=0;i< arr.size();i++){
cout
I don't think the correction is mandatory because sir's code works perfectly for the output :
[1,2,3,4,5,7,-1]
thankyou
@@sayantaniguha8519 don't just take the last element to sorted instead make the complete array/vector unsorted it will not work for eg take {2,1,7,3}
i did the same thing, but in reverse,
void arraySort(vector &arr, int n, int i){
// base condition
if(i == n-1){
return ;
}
// hypothesis
arraySort(arr, n, i+=1); // O(n)
// induction
if(arr[i-1] > arr[i])
swap(arr[i], arr[i-1]);
// hypothesis
arraySort(arr, n, i); // O(n)
}
oh man you are genius thanx for this awesome explanation
javascript code :-
function insert(array, temp) {
if (array.length == 0) {
array.push(temp)
return
} else if (array[array.length - 1]
Python Code:
#a is array/list
def sorta(a):
if len(a)==1:
return
temp=a.pop()
sorta(a)
insert(a,temp)
def insert(a,temp):
if len(a)==0 or a[-1]
👍
@AdityaVerma,
Tree and graph lessons would be much appreciated. Recursion se to pyar ho hi gaya hai. Tree aur Grpah se bhi karwa do boss.
lghta h iss week my recursion series puree ho jayegyi pls bhaiya add some questions for us to solve in the end of video
your videos are awesome..these videos help me to improve my knowledge of recursion ...please make a videos on backtracking also.
Hi Aditya,
I really enjoyed watching your video on [topic]. It was very informative and helpful. I have a suggestion that I think could make the video even more valuable to your viewers. Would you consider including some practice questions in the description of the video? This could be a great way for viewers to test their understanding of the material and reinforce their learning. It could also be helpful for those who are studying for a test or exam and want to see how well they can apply their knowledge.
I think this would add an interactive and engaging element to the video, and I believe it would be beneficial for your viewers.
Thanks for considering my suggestion!
Best regards,MR_King_KK
agree
What an explanation man!
You are jitu bhaiya 🙌🏻 of kota factory
I am still having difficulty understanding this especially the insert part? can someone help me, what exactly is the temp variable being used ?
JavaScriptCode For Recursive SortArray:-
function sortArray(arr, s, end) {
if (s >= end) {
return arr;
}
let lastVal = arr.pop();
sortArray(arr, s, end - 1);
insertVal(arr, lastVal);
}
function insertVal(arr, lastVal) {
if (arr.length === 0 || arr[arr.length - 1]
Thanks 😊😊 bhai itna sahi se samjhane ke liye
Bhaiya time complexity bhi dicuss karliya karo 2min k liye ..... though these videos focuses on recursion
Insert() wala part sahi se nhi samjhaya chief!
Hypothesis likhne me dikkat ho rhi thi
Hypothesis : insert() will add the element in its correct position & resultant array will be sorted.
One thing to observe that , insert() will always get sorted vector as its input.
Javascript code:
const insert = (arr,temp) =>{
if(arr.length===0 || arr[arr.length-1] {
if(arr.length===1){
return
}
let temp = arr.pop();
sort(arr);
insert(arr,temp)
}
let arr = [1,5,0,2]
sort(arr)
console.log(arr) //[0,1,2,5]
What about i find the max element in the array and swap it with the last element and then call the sorty fn again this time with size of array -1 as parameter ?
bhai bhot accha pdhaya .. Kuch smjh nhi arha tha kahan se start kru practise .. yh woh ....
Maja aagya Bas please practise krne k lie Ques attach krdo sort of ki kahan ka h yh to yaaar Maja hi ajaye
kudos!!!!! very detail and beautifully explained.
The video explanation was very good🔥🔥
Great explanation
Real education is not what to think , its how to think..that what is recursion (how to think) in coding , that what you taught here..
Java code :
public class SortArray {
public static void main(String[] args) {
List list = new ArrayList(Arrays.asList(3,2,1,4,5,6,7));
System.out.println(sort(list));
}
public static List sort(List list) {
if (list.size() == 1) return list;
int temp = list.remove(list.size() - 1);
sort(list);
insert(list, temp);
return list;
}
public static List insert(List list, int temp) {
if (list.isEmpty() || list.get(list.size() - 1)
Just copying here in case anyone is wondering how to implement recursive on an array
func main() {
arr := []int{7, 5, 0, 1}
sort(arr, len(arr))
fmt.Println("Sorted:", arr)
}
func sort(arr []int, n int) {
if n = arr[pos-1] {
arr[pos] = val
return
}
t := arr[pos-1]
insert(arr, val, pos-1)
arr[pos] = t
}
thank you.
Thank you bhaiya for making these videos
Bhaiya please linked list ki series bhi le aao kaafi mushkil hoti hai.. Aap samjhate ho toh feel aa jati hai topic ki
Working Code:
#include
#include
using namespace std;
void insertTemp(vector&v, int temp){
//base condition
if(v.size()==0 || v[v.size()-1]>n;
vectorarr;
for(int i=0;i>d;
arr.push_back(d);
}
sortArray(arr);
for(int i=0;i
Please include TOH and if you can add TC of the explained code at the end of the video it will be great.
if i use the simple array do-not use the vector then condition will change for insertion
Very good explanation
Thnx for making high quality content