this video presents a very simple example of pointer arrays in C and the example is taken from the textbook so this example basically implements a program as follows first the program will get a sequence of strings from mail line and it stores that in this data structure the static structure is basically an alley of Charter Stars here I have an area of three chart Stars each of those chart stars or pointer chart pointers are pointing to an array and the the array is an area of character so each Charter star points to a chart array or a string the first string let's say the user enters is D fghi the second one is jkfo Elemento pqrst the last one is ABC The Next Step we're going to sort this area of strings alphabetically and basically ABC comes first after sorting the second one is the fghi and the last one is jkh lmnopqrst and at the very end of the program we're going to print the sorted list of strings on this screen all right so let's take a look at how the program looks like let's assume that we have the definition of read lines function write lines function and Q sorts in a different place I'll show you those functions later but for now let's say those are implemented and I'll show you the main function uh first of all before I show you the main function I just want to briefly tell you what each function does the read lines basically receive up to end lines from a standard input which is the keyboard and store all of them in a charter star array called line PTR this is the same array that I showed you in the previous Slide the outline of this array is basically uh a sequence of Charter Stars each one pointing to a string and uh the right line basically prints a given list of strings on on the string on the on the screen and the last one which is quick sort or Q sort basically grabs a list of or gets a list of strings a left and right index which basically specifies a sub array of that list or a sub array of the array line PTR and it sorts that subarray the reason we pass left and right is because Q sort is recursive those of you who know how quick sort Works basically it's a recursive sorting algorithm and it needs to get the left and right index so that it always sort the sub array starting from late left and ending it right and using that we implement the Q sort or quick sword in a recursive fashion so those are the functions we call but let's take a look at the main in the main first we are going to call the read lines and receive a sequence of let's say 3 4 10 20 100 lines from the from the standard input or keyboard after that we're going to call the quick sort online PTR to sort all the lines we're gonna start from index 0 the left is zero and the right is number of lines minus one that means I'm gonna sort the whole array and uh then after it's sorted then I'm gonna write all the lines on the screen using right lines and that's it now if the read lines ended up at the [Music] at the narrow by an error or if read lines return with the with an errors then it returns a negative number then we get to the else part and we print input uh too big to sort I'll show you uh how read line returns a negative number that's an exceptional case but if that happens we're going to print an error message on this screen and that would be the end of this program all right now let's take a quick look at the read lines function the body of field lines function uh here what we do is in a while loop we get a new line by calling get line that's a function that is used in the textbook but the more common way of getting a line is by calling a function called f get s that's much more common but you know we'll follow the book examples so get line will get a new line and uh the length of that line would be LAN if the line is not received or if there's no new line this function returns zero or I should say it turns a non-positive value and that's why we get out of the while loop and we simply return the number of lines that has been successfully entered but let's say the user wants to enter like 20 lines so in the first 20 iteration of this while loop this is going to be true that means a line will be received from keyboard or from Stellar input after you receive the line it is going to be stored in line where line is an area of length max length where max length is a thousand that means you can have up to 999 characters the reason I said 999 is because when the length of when the capacity of line array is a thousand the last one is reserved for a package like zero which ends a string so the number of actual characters in The String would be 9.99 so in any case after you get the line you check whether uh the number of lines is not exceeding the maximum number of lines that we have that's a limit that's just for the sake of um practical reasons and because we want to make sure that the user doesn't enter too many lines and then uh if the number of lines exceeds a maximum or malloc cannot allocate more memory let's say the memory is full then we're going to return negative one and that's an error case that's where in the main if you remember we return we print an error message on the screen but that these are not common situations like like malloc always returning on negative value unless there's no space in the Heap and by the way the book instead of malloc we use alloc which is a function made up by the authors and uh that's basically a simplified version of meloc so anywhere you see alloc just replace it by malloc in your mind Malak means memory allocation function which basically allocates memory in the heat how much this much the length of the line whatever the length of the line is that's the number of whites that you're going to allocate in any case after um we allocate it's uh memory for the line that we just received from the keyboard we are going to do this first of all get line adds a new line at the end of the line so we're going to get it gets rid of it by doing this uh by setting the index then minus one of the array line equal to zero zero basically is a sign for the end of the string then we're going to copy line into p p is pointing to the Heap because p is the return value of malloc and we're using we use a strcpy to copy the line into that space and then what I have is um uh this line which basically um copies the reference of the new line into the list of all the lines that we have which is line PTR that's the first thing with parameter of the function and it's going to refer to all the lines that the user enters in order from the oldest to the newest and then at the end I return the number of lines and that's the whole body of read lines next we have a very simple function they read the right lines which basically gets the area of charge stars that I showed you and the number of lines and in a for Loop it goes over all the elements of the line PTR array and prints them all using percent s so there's nothing special about this function and next we have the Q sort for those of you who don't know what Q sort is Q sort is a quick sort of operation I'll try to briefly explain it but if you have taken let's say data structures you know how it works let's say you have an area of I'm going to start with I'm going to show you the example of quick circuit numbers not with strings because it's easier let's say I have a 10 here I have five here I have seven here I have six here I have two here I have three here and I have eight here so what is uh what does this quick sort do first we pick up pivots that pivot would be the middle elements let me give it a pivot that's called pivot the middle element which is six the next step after picking the pivot in a quick sort is to move everything less than pivot to the left side of pivot and move everything greater than pivot to the right side of the pivot for example this is in the left side of pivot and is greater than pivot this is in the right side of pivot and it's less than pivot so this should be swapped so we're going to swap 10 and 2 after swapping 10 and 2 we have two two here instead of ten and 10 here instead of 2. uh also 7 is greater than six but is in the left side 3 is less than six but it's in the right side so we're gonna swap seven and three after doing this swap three comes here and seven comes here so after reordering elements based on the pivot which is six the array looks like this we have two in the first cell five in the second so 3 is in the third song six is in the middle so then I have 10 7 and 8. in the next level of recursion quick sort is normally implemented recursively we're gonna only focus on the left hand side of pivot as a sub array and right hand side of the pivot as a sub array so you see this quick sort with the left and the right index that represents the the range of or the window that we're going to focus to sort in each function call you need to recursive function call for example here left is zero because we started index 0 up to index two and in the other call we start left at index forward and right is at index six again for the left side the pivot is five toward the right side the pivot is seven we have to move three to the left side of pivot because 3 is less than five we need to move ten to the right side of pivot because pivot is 7 and 10 is greater than 7. and uh after you're doing these uh the orderings and swaps what you get is you get two three five the left side six in the middle and the right side we have seven eight n and that's basically makes things sorted that's how quicksort works if I want to give you a very brief overview so this quick sort uses a function called swap that swaps the if index and jth index of array V this quick sort is not sorting an array of integers in a stead Source scenario of charge Stars and in C when you want to compare two strings you use SD or CMP this is kind of similar to the string.char that dot s dot St dots once again it is similar to a string that's compared to in Java basically if two strings are equal compared to what's returning zero same as this strcmp returns zero strcmp gets two parameters if the first one is less than the second one it returns a negative number and if the first one is greater than the second one that means if it's alphabetically after the second one then it returns a positive number so using Str CMP and swap which swaps two indices of the same array we're gonna write down the Q sort every time that you want to do a recursive function you need to take care of the base case first and the base case is where where you have the smallest subarray possible because as I told you this Q sort each time sort the subarray the sub array starts from left and ends at right so the best case is when left is greater than or equal to right that means you either have one element in your sub array or you have no element in your summary in that case you don't need to sort it just return do nothing because that's the base case base case means the sub problem is too small that you don't even need to call any function recursively you don't need to do anything just return and then after that after you take care of their base case uh you need to start picking the pivot which is at index left plus right over two you temporarily move pivot to the left most cell and then you define a last which is always pointing to the last element um of the left summary that we're gonna construct and then starting from left plus one all the way to the end of the sub array all the way to right compare the ice element with the left if it's less we're going to swap we're gonna swap the if element with the last plus one index and then after this for Loop ends all the swap operation happens and everything before last is less than pivot and everything after last is greater than pivent we're gonna move the pivot to the right location we're gonna do the the correct appropriate position by swapping left and last then at this point you have to call the function recursively we call Quick Q sort twice the first time it's gonna sort the left subarray and the second time it's going to sort the right sub array and that's it that's the end of a quick sort operation in C it's a little bit too complicated because of the nature of quick sort but you know if you want to use any quick sort operation just copy this and use that in your project you don't need to re-implement this as you may have noticed inside the Q sort we use swap with two apps basically two indices I and J are the same same array B this is how the swap looks like you need to First Define a choice start temp temp equals Viv equals VI equals v j and V J equals 10. that's how this web operation works and that's going to be the end of this example so as I showed you in this example uh we had a program that gets a sequence of lines from standard input it stores them in an area of charge stars and then it calls a squeak sort on it sorts the the area of strings alphabetically using Q sort and then eventually it prints them out on the screen so on the screen you will see a sorted list of strings