00:00The next question which we will talk about next algorithm is Quicksort
00:04Quicksort is a merge sort of time complexity
00:06but only in average cases
00:08but in average cases there is also a time complexity
00:12Quicksort is a good thing
00:14it doesn't take extra space in merge sort
00:18we will sort our array
00:21Quicksort is the best thing
00:24Quicksort in average case
00:26which comes from time complexity
00:28that is equal to
00:30n log in
00:32yes, in the worst case
00:33Quicksort's time complexity
00:35n square
00:36and here the space complexity
00:39comes from constant space
00:40which is 0 of 1
00:42so we don't use extra space
00:43so in which questions we should have
00:45average time complexity
00:49but we don't have extra space
00:51in those cases
00:52we can use Quicksort
00:54this is the worst case
00:55this is the worst case
00:56we don't hit in most cases
01:00so let's talk about Quicksort
01:02Quicksort is on our pivot and partition approach
01:06pivot and partition
01:07divide and conquer
01:11we have called pivot and partition
01:13we have called pivot and partition
01:15we have called pivot and partition
01:16now the first step
01:18which we have to perform in quicksort
01:20is to choose a pivot
01:22what is the pivot
01:23if we have studied physics in 11-12
01:25pivot is a center point
01:27which rotates around
01:29like if I put this pencil
01:31here
01:31so if it rotates this way
01:33then this is my pivot point
01:36this is my pivot point
01:38which is around things
01:39so which element around
01:42I will rotate my array
01:44or change my array
01:47or sort my pivot element
01:51that will be my pivot element
01:54which means
01:54if I take out any random element
01:56I have removed 8
01:58so I will sort this array
02:01so I will sort this array
02:028 from small elements
02:038 from small elements
02:058 from small elements
02:068 from small elements
02:07so this is 3, 6, 2, 5
02:10so here will be 6, 3, 2 and 5
02:13and my 9 is bigger than 8
02:15so my 9 will come here
02:16so what happened here
02:17what happened here?
02:18it was 8
02:188 which I have to sort
02:21so we can take pivot
02:22we can take everyone
02:23there are many approaches
02:24to choose pivot element
02:26you can take a random element
02:28you can take a random element
02:30you can take a pivot
02:30and pivot
02:31we can take our first element
02:33we can take our last element
02:35but we can take our maximum
02:38quicksort
02:39we can take our last element
02:41we can take our last element
02:42and we can take our last element
02:43and solve it
02:45but in any way
02:46you can solve it
02:46the answer is the same
02:48what we can do here?
02:49we can take our last element
02:52we can take our last element
02:52so this will be my step 1
02:53step 1
02:54what did I do?
02:55I took 5 as a pivot
02:56after that
02:57my step 2
02:58what will I do?
03:00I will do partition
03:01partition
03:01partition means
03:03that I divide the array
03:04in parts
03:07how do I divide?
03:09this pivot around
03:10I have 5
03:12what will I do?
03:12I will draw your세요
03:13in theے 좋을
03:17so 1
03:24I will use 5
03:26here
03:28then 3
03:29I will make it
03:339
03:343
03:378
03:37So, I will take 8 to 8. Then, I will take 2 to 2. So, I will take 2 to
03:425. So, I will take 2 to 5. So, what happened?
03:46My pivot was around which I have taken the elements. I took the small elements to it and took the
03:53big elements to it.
03:54This is the process that is the quicksort. This is the most important process.
03:58So, I will store the small elements after pivot and store the big elements after pivot. This is the main
04:07step.
04:07Now, we will talk about how the partition will actually be. But, as I have my partition, what will I
04:14do?
04:14Now, I will call the quicksort recursively for this part and recursively for my right part.
04:20I will call the quicksort. So, the third step will be to call the quicksort for my left part.
04:28And call the quicksort for my right part. And, what happened in the mod sort?
04:34The big problem was that the small parts of the mod sort were recursively.
04:38They will also be small parts. And, in the last, we will hit the base condition.
04:42What will my base case come? My base case will come.
04:45When I have a single element, what will happen in the case?
04:49In a single element case, I have no work.
04:53So, my array is sorted. So, I will have a base case.
04:57So, I have to do three things. First, I have to select pivot.
05:01Then, I have to partition. I have to divide parts.
05:04And then, I have to find the right position of pivot.
05:08Now, I have to write this array here. But, if the array is sorted, what is the right position?
05:12First, all the small elements. Then, all the big elements.
05:16This is the partition step. Then, I will sort the left recursively and right recursively.
05:21The base case, I have to figure out.
05:23Now, let's discuss this partition in a little detail.
05:26What do I have to do for partition?
05:28I always know that I have to merge sort.
05:30So, in this way, my original array will be starting index and ending index.
05:36Starting index will be 0 and ending index will be 5.
05:40Now, I have to select pivot. What is my pivot? My pivot is 5.
05:44And what is this pivot index? Now, this pivot index is 5.
05:48So, my ending index is 5.
05:51So, what will I do? I will use an iterator.
05:53I will initialize it from minus 1.
05:56And what will I do?
05:58It will create a place in my area.
06:00Who will create a place?
06:01For my elements.
06:04For my elements.
06:04For the small pivot, I will create a place in my area.
06:11The I will create a place in my area.
06:12The I is working to create a place in my area.
06:15So, I have initialized it from minus 1.
06:19So, I can say that I will now be minus 1.
06:21If it is 0, 1, 2, 3, 4, 5.
06:24So, I will point here.
06:27I will not point any valid index.
06:29Now, what will I do?
06:30I have created an iterator.
06:31This is my original area.
06:33This is not a temporary area.
06:34I am talking about original.
06:36In the original area, there are already elements stored.
06:38Here, there are 6 stored.
06:39Here, there are 3 stored.
06:40Here, there are 9 stored.
06:41Here, there are 8 stored.
06:42Here, there are 2 stored.
06:42Here, there are 5 stored.
06:44They are already stored.
06:44These areas are filled.
06:45I have only told from the perspective of the I.
06:48I don't know where the areas are filled.
06:49I think it is empty.
06:51So, I can store new elements.
06:54Now, what will I do?
06:55I will traverse the original area.
06:56First of all, I will ask from 6.
06:58I will compare with 5.
07:00Is 6 bigger from 5 or small?
07:026 bigger from 5.
07:04So, what will I do?
07:04I will make the same here or here.
07:06So, what will I do?
07:07I will not do any work.
07:08I will make the same place for 6.
07:10I will make the same place for 6.
07:10Because I will make the same place for small elements.
07:14So, I will not do any work.
07:16I will not do anything.
07:17Then, I will ask from 3.
07:20Will my 3 be small or big?
07:22Obviously, 3 is smaller than my pivot.
07:24So, I will make the same place for this.
07:26How will I make the same place for this?
07:27What will I do?
07:28First, I will increase my value.
07:30I plus plus, my pointer will come from here.
07:34That means, where 6 is now.
07:36Then, what will I do?
07:37I will swap the values.
07:39How will I swap the same place?
07:41I will raise the same place from here.
07:47I'll use the same place.
07:48How will I swap the same place?
07:49That set 3 as I made the same place from here.
07:54And where I came from while I was from here.
08:00I will raise the same place.
08:00How will I swap the same place for that?
08:02I asked for x in there.
08:07What value had been out of
08:14I will store the value of array of j. I will store the value of array of i and i
08:27will store the value of i.
08:35We will swap the values in this way
08:36So what will I do?
08:38We will swap values
08:39After that, we will go further
08:42J will increase the value of 2
08:45So you will compare 9 with 5
08:46It will increase 9 with 5
08:48So there will no work here
08:49I will increase the value of minus 1
08:51After that, the iterator will increase 8
08:54We will compare 8 with 5
08:55Is the value of 5? Yes, it will increase
08:58In this case, there will also be no swap
09:00J is equal to 3
09:01There will also be no swap
09:02Then the iterator will increase J is equal to 4
09:04If the value of 2 is greater than 5
09:07It is small
09:08So now I will make 2
09:10How will I make the place?
09:12What will I do?
09:13I will make plus plus
09:15It will be equal to 1
09:18If I is equal to 1
09:19Then I will change the place
09:21There will already be 6
09:24So I will pick up 6
09:25Who will put 2?
09:27So there will be 2
09:28And where there was 2
09:30Which means J is equal to 4
09:31There will be 2
09:35So this will be swap
09:36Now my final array
09:38How will I become the original array?
09:41How will I become the array?
09:43I will become the array
09:44First of all, 3
09:45Then 2
09:46Then 9
09:48Then 8
09:49Then 6
09:50Then 5
09:51Then 5
09:51I have copied the same elements here
09:52Then 2
09:54Then 9
09:55Then 8
09:56Then 6
09:58Then 6
09:58Here is my pivot
10:00Now I will make the pivot
10:01To take the pivot
10:02To take the pivot
10:03So to take the pivot
10:04To take the pivot
10:05This is the same thing
10:06Swapping
10:06Once again
10:09So it will be I plus plus
10:10I will come here
10:11which means index is equal to 2
10:13index is equal to 2
10:15what will swap in 9
10:17swap in 9
10:18swap in 5
10:20pivot
10:219
10:24swap in 9
10:27swap in 9
10:28last time we will see what will happen
10:315 pivot
10:325 elements will come here
10:345 elements will come here
10:36partition
10:37how magically
10:39this i
10:40worked
10:41i
10:41made small elements
10:45and 5
10:46stored
10:49so in this way
10:51my partition will work
10:53and we are going to convert
10:54the same logic in code
10:56we are going to separate
10:57cut本
10:57cut
10:57cut
10:57cut
10:57cut
10:57cut
10:57cut
10:57cut
10:57cut
