title
7.12 Counting Sort (Analysis and Code) | Easiest Explanation | Data Structure Tutorials

description
Discussed Counting Sort Algorithm with its Code. Step by step guide showing how to Sort an Array using Count Sort. Analysis of Counting Sort (Time Complexity) DSA Full Course: https: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU ****************************************** See Complete Playlists: C Programming Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31a8UcMN9-35ghv8qyFWD9_S C++ Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YU5Wx1dopka58teWP9aCee Python Full Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bZSiqiOL5ta39vSnBxpOPT Printing Pattern in C: https://www.youtube.com/playlist?list=PLdo5W4Nhv31Yu1igxTE2x0aeShbKtVcCy DAA Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31ZTn2P9vF02bkb3SC8uiUUn Placement Series: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YvlDpJhvOYbM9Ap8UypgEy Dynamic Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31aBrJE1WS4MR9LRfbmZrAQu Operating Systems: //www.youtube.com/playlist?list=PLdo5W4Nhv31a5ucW_S1K3-x6ztBRD-PNa DBMS: https://www.youtube.com/playlist?list=PLdo5W4Nhv31b33kF46f9aFjoJPOkdlsRc *********************************************** Connect & Contact Me: Facebook: https://www.facebook.com/Jennys-Lectures-CSIT-Netjrf-316814368950701/ Quora: https://www.quora.com/profile/Jayanti-Khatri-Lamba Instagram: https://www.instagram.com/jayantikhatrilamba/ #countingsort #jennyslectures #dsa

detail
{'title': '7.12 Counting Sort (Analysis and Code) | Easiest Explanation | Data Structure Tutorials', 'heatmap': [{'end': 1026.782, 'start': 967.798, 'weight': 0.938}], 'summary': 'Explains the concept and implementation of counting sort algorithm, emphasizing its linear time complexity, demonstrating sorting, counting, and positioning elements in an array, building arrays, maintaining stability, revealing time complexity of n plus k, and discussing its limitations, suggesting the use of radix sort.', 'chapters': [{'end': 93.942, 'segs': [{'end': 49.186, 'src': 'embed', 'start': 0.149, 'weight': 0, 'content': [{'end': 1.81, 'text': 'this sorting algorithm?', 'start': 0.149, 'duration': 1.661}, {'end': 6.652, 'text': 'fine, see, first of all, we have discussed many sorting algorithms.', 'start': 1.81, 'duration': 4.842}, {'end': 15.772, 'text': 'all those sorting algorithms are comparison, sort, bubble selection, merge, quick, heap all, all are comparison sorts.', 'start': 6.652, 'duration': 9.12}, {'end': 20.916, 'text': 'we are going to compare the values given and, after comparing the values,', 'start': 15.772, 'duration': 5.144}, {'end': 24.919, 'text': 'either we are going to swap the values or we are not going to swap the values.', 'start': 20.916, 'duration': 4.003}, {'end': 28.662, 'text': 'fine, but this sorting algorithm is not a comparison sort.', 'start': 24.919, 'duration': 3.743}, {'end': 31.504, 'text': 'we are not going to compare the values.', 'start': 28.662, 'duration': 2.842}, {'end': 33.466, 'text': 'then how we are going to sort?', 'start': 31.504, 'duration': 1.962}, {'end': 39.671, 'text': 'see, we are going to sort the values according to the keys, the key value given.', 'start': 33.466, 'duration': 6.205}, {'end': 49.186, 'text': 'fine, or you can say, the main fun time this sorting algorithm is, you are going to count, see, as the name suggests, counting.', 'start': 40.913, 'duration': 8.273}], 'summary': 'The sorting algorithm discussed is not a comparison sort; it is a counting sort based on key values.', 'duration': 49.037, 'max_score': 0.149, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE149.jpg'}], 'start': 0.149, 'title': 'Counting sort algorithm', 'summary': 'Explains the concept of counting sort algorithm, a non-comparison sort that allows sorting in linear time, unlike comparison sorts such as merge, quick, and heap sort with a time complexity of n log n.', 'chapters': [{'end': 93.942, 'start': 0.149, 'title': 'Counting sort algorithm', 'summary': 'Explains the concept of counting sort algorithm, which is a non-comparison sort and allows sorting in linear time, unlike comparison sorts like merge, quick, and heap sort with a time complexity of n log n.', 'duration': 93.793, 'highlights': ['The counting sort algorithm is a non-comparison sort, allowing sorting in linear time, unlike merge, quick, or heap sort with a time complexity of n log n.', 'The algorithm involves counting the number of elements with distinct key values to sort the array, providing a more efficient sorting approach compared to comparison sorts.', 'The chapter discusses the limitations of comparison sorts such as merge, quick, and heap sort, which have a best time complexity of n log n, but cannot achieve sorting in linear time like counting sort algorithm.']}], 'duration': 93.793, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE149.jpg', 'highlights': ['The counting sort algorithm is a non-comparison sort, allowing sorting in linear time, unlike merge, quick, or heap sort with a time complexity of n log n.', 'The algorithm involves counting the number of elements with distinct key values to sort the array, providing a more efficient sorting approach compared to comparison sorts.', 'The chapter discusses the limitations of comparison sorts such as merge, quick, and heap sort, which have a best time complexity of n log n, but cannot achieve sorting in linear time like counting sort algorithm.']}, {'end': 600.417, 'segs': [{'end': 152.048, 'src': 'embed', 'start': 116.392, 'weight': 2, 'content': [{'end': 124.828, 'text': 'fine, and all the elements are in the range of see from zero to 0.', 'start': 116.392, 'duration': 8.436}, {'end': 125.128, 'text': 'to see.', 'start': 124.828, 'duration': 0.3}, {'end': 127.209, 'text': 'minimum element is 0, maximum element.', 'start': 125.128, 'duration': 2.081}, {'end': 129.169, 'text': 'find out the maximum element in this array.', 'start': 127.209, 'duration': 1.96}, {'end': 131.73, 'text': 'maximum element is, I guess, 7..', 'start': 129.169, 'duration': 2.561}, {'end': 135.43, 'text': 'So range is from 0 to 7 fine.', 'start': 131.73, 'duration': 3.7}, {'end': 140.412, 'text': 'So you can say here k value is 7.', 'start': 135.851, 'duration': 4.561}, {'end': 147.013, 'text': 'So here you can say we have an array having k different elements right.', 'start': 140.412, 'duration': 6.601}, {'end': 152.048, 'text': 'maybe in this array values can be duplicate, values can be there.', 'start': 148.607, 'duration': 3.441}], 'summary': 'The array contains elements ranging from 0 to 7, with a maximum element of 7.', 'duration': 35.656, 'max_score': 116.392, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE116392.jpg'}, {'end': 333.356, 'src': 'embed', 'start': 243.867, 'weight': 0, 'content': [{'end': 245.848, 'text': 'index is from 0 to 16.', 'start': 243.867, 'duration': 1.981}, {'end': 251.247, 'text': 'fine, and k value is what the range you can check out.', 'start': 245.848, 'duration': 5.399}, {'end': 252.309, 'text': 'the minimum is 0.', 'start': 251.247, 'duration': 1.062}, {'end': 254.892, 'text': 'the maximum element is 9.', 'start': 252.309, 'duration': 2.583}, {'end': 257.096, 'text': 'fine. so range is from 0 to 9.', 'start': 254.892, 'duration': 2.204}, {'end': 261.903, 'text': 'or you can say the k value is 9, fine.', 'start': 257.096, 'duration': 4.807}, {'end': 266.276, 'text': 'now, the first step is what we are going to count.', 'start': 261.903, 'duration': 4.373}, {'end': 273.418, 'text': 'see, i have told you counting the elements having distinct key values key is key value means this this two.', 'start': 266.276, 'duration': 7.142}, {'end': 274.978, 'text': 'this is the key value one.', 'start': 273.418, 'duration': 1.56}, {'end': 276.499, 'text': 'this is the key value.', 'start': 274.978, 'duration': 1.521}, {'end': 279.099, 'text': 'fine. how many times this two is there in this array?', 'start': 276.499, 'duration': 2.6}, {'end': 284.781, 'text': 'you are going to count that thing one, two, three, four, fine.', 'start': 279.099, 'duration': 5.682}, {'end': 287.281, 'text': 'how many times one is there in this array?', 'start': 284.781, 'duration': 2.5}, {'end': 296.044, 'text': 'one, two and three, three times like this, you are going to count the elements, fine, and after counting,', 'start': 287.281, 'duration': 8.763}, {'end': 300.225, 'text': 'obviously you are going to store those elements in somewhere.', 'start': 296.044, 'duration': 4.181}, {'end': 311.588, 'text': 'so for storing that count, we are going to take another array and i am going to take the name of the array as count.', 'start': 300.225, 'duration': 11.363}, {'end': 318.01, 'text': 'right now, the size of this count array would be this k plus 1.', 'start': 311.588, 'duration': 6.422}, {'end': 319.29, 'text': 'so 9 is there.', 'start': 318.01, 'duration': 1.28}, {'end': 321.231, 'text': 'see, range is from 0 to 9.', 'start': 319.29, 'duration': 1.941}, {'end': 322.671, 'text': 'so 10 elements would be there.', 'start': 321.231, 'duration': 1.44}, {'end': 326.211, 'text': 'range this size would be k plus 1.', 'start': 323.789, 'duration': 2.422}, {'end': 329.213, 'text': 'or you can say range plus 1.', 'start': 326.211, 'duration': 3.002}, {'end': 330.374, 'text': 'so let us suppose this array.', 'start': 329.213, 'duration': 1.161}, {'end': 333.356, 'text': 'is there another array?', 'start': 330.374, 'duration': 2.982}], 'summary': 'Count distinct key values in array, store in count array of size k+1', 'duration': 89.489, 'max_score': 243.867, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE243867.jpg'}], 'start': 93.942, 'title': 'Counting sort implementation', 'summary': 'Discusses the implementation and time complexity of counting sort for an array of 17 elements with a range of 0 to 9, emphasizing the process of counting distinct key values and storing their frequencies in a separate array with a size of k+1, and explains the process of initializing and incrementing values in a count array through a detailed example.', 'chapters': [{'end': 389.72, 'start': 93.942, 'title': 'Counting sort for array with range', 'summary': 'Discusses the time complexity and implementation of counting sort for an array of 17 elements with a range of 0 to 9, emphasizing the process of counting distinct key values and storing their frequencies in a separate array with a size of k+1.', 'duration': 295.778, 'highlights': ['Counting distinct key values and storing their frequencies in a separate array with a size of k+1 is crucial for implementing counting sort. Distinct key values, frequencies, array size', "Illustrates the process of counting and storing the frequencies of distinct key values in the 'count' array, providing a clear example for understanding the implementation. Counting process, storing frequencies, example illustration", 'Emphasizes the importance of ensuring no negative values in the array and the values being within the range of 0 to k for the successful implementation of counting sort. No negative values, range constraint']}, {'end': 600.417, 'start': 389.72, 'title': 'Count array initialization and increment', 'summary': 'Explains the process of initializing and incrementing values in a count array through a detailed example, highlighting the specific steps and outcomes, leading to a clear understanding of the coding process.', 'duration': 210.697, 'highlights': ['The chapter explains the process of initializing and incrementing values in a count array through a detailed example. Understanding the process of initializing and incrementing values in a count array, detailed example provided.', 'The specific steps and outcomes are highlighted, leading to a clear understanding of the coding process. Detailed explanation of specific steps and outcomes, aiding in a clear understanding of the coding process.', 'The transcript provides a step-by-step demonstration of accessing and modifying values in the count array. Step-by-step demonstration of accessing and modifying values in the count array.']}], 'duration': 506.475, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE93942.jpg', 'highlights': ['Counting distinct key values and storing their frequencies in a separate array with a size of k+1 is crucial for implementing counting sort. Distinct key values, frequencies, array size', "Illustrates the process of counting and storing the frequencies of distinct key values in the 'count' array, providing a clear example for understanding the implementation. Counting process, storing frequencies, example illustration", 'Emphasizes the importance of ensuring no negative values in the array and the values being within the range of 0 to k for the successful implementation of counting sort. No negative values, range constraint', 'The chapter explains the process of initializing and incrementing values in a count array through a detailed example. Understanding the process of initializing and incrementing values in a count array, detailed example provided.', 'The specific steps and outcomes are highlighted, leading to a clear understanding of the coding process. Detailed explanation of specific steps and outcomes, aiding in a clear understanding of the coding process.', 'The transcript provides a step-by-step demonstration of accessing and modifying values in the count array. Step-by-step demonstration of accessing and modifying values in the count array.']}, {'end': 914.308, 'segs': [{'end': 656.179, 'src': 'embed', 'start': 600.417, 'weight': 0, 'content': [{'end': 605.241, 'text': 'so count brackets a and i, and now we will do plus plus.', 'start': 600.417, 'duration': 4.824}, {'end': 606.702, 'text': 'so here you can write plus plus.', 'start': 605.241, 'duration': 1.461}, {'end': 611.785, 'text': 'or here you can write plus plus post increment or pre increment.', 'start': 608.624, 'duration': 3.161}, {'end': 615.347, 'text': 'in this case both will be same.', 'start': 611.785, 'duration': 3.562}, {'end': 617.368, 'text': 'this is what you have done at starting.', 'start': 615.347, 'duration': 2.021}, {'end': 628.273, 'text': 'only when you are going to take this array, you are going to initialize this array with zeros, for i is equal to zero, i less than equal to k,', 'start': 617.368, 'duration': 10.905}, {'end': 631.494, 'text': 'k and count of i is equal to zero.', 'start': 628.273, 'duration': 3.221}, {'end': 639.327, 'text': 'so now, next step is now you have, you have counted the elements, the frequency of the elements, fine,', 'start': 631.494, 'duration': 7.833}, {'end': 646.312, 'text': 'but now you are supposed to find out the actual position of these elements in the sorted array.', 'start': 639.327, 'duration': 6.985}, {'end': 655.218, 'text': 'see after sorting the array would be something like this see after sorting after sorting, array would be something like this fine,', 'start': 646.312, 'duration': 8.906}, {'end': 656.179, 'text': 'this is unsorted array.', 'start': 655.218, 'duration': 0.961}], 'summary': 'Initial array initialized with zeros, frequency counted, and position of elements to be found in sorted array.', 'duration': 55.762, 'max_score': 600.417, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE600417.jpg'}, {'end': 775.38, 'src': 'embed', 'start': 712.908, 'weight': 1, 'content': [{'end': 721.07, 'text': 'fine, such that this count array contains the actual position of the elements.', 'start': 712.908, 'duration': 8.162}, {'end': 723.591, 'text': 'fine, see how we are going to do that.', 'start': 721.07, 'duration': 2.521}, {'end': 726.272, 'text': 'we are going to update this array.', 'start': 723.591, 'duration': 2.681}, {'end': 730.653, 'text': 'I am going to update this count array.', 'start': 726.272, 'duration': 4.381}, {'end': 733.556, 'text': 'this is same count array.', 'start': 732.335, 'duration': 1.221}, {'end': 735.357, 'text': 'we are going to update in the same array.', 'start': 733.556, 'duration': 1.801}, {'end': 744.041, 'text': 'fine, see, first, first value would be, as it is, the value at index zero.', 'start': 735.357, 'duration': 8.684}, {'end': 745.082, 'text': 'that would be as it is.', 'start': 744.041, 'duration': 1.041}, {'end': 751.225, 'text': 'we are going to start a loop from here only from the first index.', 'start': 745.082, 'duration': 6.143}, {'end': 758.869, 'text': 'fine, after these three zeros, after three zeros for next three, for next three positions, one would be there.', 'start': 751.225, 'duration': 7.644}, {'end': 764.513, 'text': 'fine, so the position of one would be see after these three zeros.', 'start': 760.37, 'duration': 4.143}, {'end': 765.654, 'text': 'so three plus three.', 'start': 764.513, 'duration': 1.141}, {'end': 769.396, 'text': 'that is six up to six.', 'start': 765.654, 'duration': 3.742}, {'end': 772.698, 'text': 'see, index is five, but position is six.', 'start': 769.396, 'duration': 3.302}, {'end': 775.38, 'text': 'one, two, three, four, five, six.', 'start': 772.698, 'duration': 2.682}], 'summary': 'Updating count array based on element positions', 'duration': 62.472, 'max_score': 712.908, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE712908.jpg'}], 'start': 600.417, 'title': 'Sorting, counting, and positioning elements', 'summary': 'Discusses counting the frequency of elements in an array, determining their positions in the sorted array, updating array positions using specific rules, and demonstrating the process with specific index examples and explanations.', 'chapters': [{'end': 745.082, 'start': 600.417, 'title': 'Counting and positioning sorted elements', 'summary': 'Discusses counting the frequency of elements in an array and determining their positions in the sorted array, demonstrating the process with specific index examples and explaining the updating of the count array.', 'duration': 144.665, 'highlights': ["The sorted array's positions for specific elements are demonstrated, such as the index range for 0 being 0 to 2, for 1 being 3 to 5, and for 2 being 6 to 9.", 'The process of updating the count array to contain the actual position of elements is explained, starting with the value at index zero remaining unchanged.']}, {'end': 914.308, 'start': 745.082, 'title': 'Updating array positions', 'summary': 'Explains the process of updating array positions based on a given algorithm by incrementing positions using specific rules, resulting in an updated count array reflecting the actual position of elements in the sorted array.', 'duration': 169.226, 'highlights': ['Explaining the process of updating array positions by incrementing positions using specific rules, resulting in an updated count array reflecting the actual position of elements in the sorted array with count of i being count of i plus previous value.', 'Detailing the algorithm for updating array positions by incrementing positions using specific rules, resulting in an updated count array reflecting the actual position of elements in the sorted array with count of i being count of i plus previous value.']}], 'duration': 313.891, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE600417.jpg', 'highlights': ['The process of updating the count array to contain the actual position of elements is explained, starting with the value at index zero remaining unchanged.', 'Explaining the process of updating array positions by incrementing positions using specific rules, resulting in an updated count array reflecting the actual position of elements in the sorted array with count of i being count of i plus previous value.', 'Detailing the algorithm for updating array positions by incrementing positions using specific rules, resulting in an updated count array reflecting the actual position of elements in the sorted array with count of i being count of i plus previous value.', "The sorted array's positions for specific elements are demonstrated, such as the index range for 0 being 0 to 2, for 1 being 3 to 5, and for 2 being 6 to 9."]}, {'end': 1308.874, 'segs': [{'end': 1026.782, 'src': 'heatmap', 'start': 959.772, 'weight': 4, 'content': [{'end': 966.196, 'text': 'so what you have to do in count, in count array, you just you just go.', 'start': 959.772, 'duration': 6.424}, {'end': 967.798, 'text': 'see, this is our updated count array.', 'start': 966.196, 'duration': 1.602}, {'end': 969.499, 'text': 'we are going to see this array now.', 'start': 967.798, 'duration': 1.701}, {'end': 971.3, 'text': 'we are not going to see this one.', 'start': 969.499, 'duration': 1.801}, {'end': 974.142, 'text': 'so see, just go to the index 9.', 'start': 971.3, 'duration': 2.842}, {'end': 976.707, 'text': 'this is index 9.', 'start': 974.142, 'duration': 2.565}, {'end': 978.108, 'text': 'right, value is 9.', 'start': 976.707, 'duration': 1.401}, {'end': 980.809, 'text': 'go to index 9 in count array.', 'start': 978.108, 'duration': 2.701}, {'end': 986.212, 'text': "right, but we cannot store 9 at 17 because we don't have 17.", 'start': 980.809, 'duration': 5.403}, {'end': 987.092, 'text': 'this is the count.', 'start': 986.212, 'duration': 0.88}, {'end': 989.734, 'text': 'but we are actually working on the index na.', 'start': 987.092, 'duration': 2.642}, {'end': 1003.181, 'text': 'so, first of all, we are going to decrement this by 1, 17 minus 1, that is 16, and in the output array, go to the index 16 and store this 9.', 'start': 989.734, 'duration': 13.447}, {'end': 1005.572, 'text': 'this is the actual place for this 9.', 'start': 1003.181, 'duration': 2.391}, {'end': 1007.453, 'text': 'fine, now, decrement i.', 'start': 1005.572, 'duration': 1.881}, {'end': 1008.754, 'text': 'now i is at this place.', 'start': 1007.453, 'duration': 1.301}, {'end': 1012.196, 'text': 'find out the value at this, that is 1.', 'start': 1008.754, 'duration': 3.442}, {'end': 1013.997, 'text': 'now go to the index 1.', 'start': 1012.196, 'duration': 1.801}, {'end': 1020.601, 'text': 'in this counter index, 1 value is 6, but we are not going to store 1 here.', 'start': 1013.997, 'duration': 6.604}, {'end': 1023.523, 'text': 'why? so because this is count value, but we are.', 'start': 1020.601, 'duration': 2.922}, {'end': 1026.782, 'text': 'we are going to store at index 5.', 'start': 1023.523, 'duration': 3.259}], 'summary': 'Decrement count and place values at respective indices.', 'duration': 27.32, 'max_score': 959.772, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE959772.jpg'}, {'end': 1042.497, 'src': 'embed', 'start': 1013.997, 'weight': 2, 'content': [{'end': 1020.601, 'text': 'in this counter index, 1 value is 6, but we are not going to store 1 here.', 'start': 1013.997, 'duration': 6.604}, {'end': 1023.523, 'text': 'why? so because this is count value, but we are.', 'start': 1020.601, 'duration': 2.922}, {'end': 1026.782, 'text': 'we are going to store at index 5.', 'start': 1023.523, 'duration': 3.259}, {'end': 1034.95, 'text': 'fine, so first of all, we are going to decrement this by 1, that is 5, and now we are going to store at 5.', 'start': 1026.782, 'duration': 8.168}, {'end': 1035.57, 'text': 'here we got 1.', 'start': 1034.95, 'duration': 0.62}, {'end': 1040.694, 'text': 'fine, why we have started from here.', 'start': 1035.57, 'duration': 5.124}, {'end': 1042.497, 'text': 'see, you can start from here.', 'start': 1040.694, 'duration': 1.803}], 'summary': 'Counter index 1 value is 6, storing at index 5 after decrementing by 1.', 'duration': 28.5, 'max_score': 1013.997, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE1013997.jpg'}, {'end': 1133.131, 'src': 'embed', 'start': 1073.175, 'weight': 0, 'content': [{'end': 1077.559, 'text': 'so in sorted array, this 9 should be before this 9.', 'start': 1073.175, 'duration': 4.384}, {'end': 1082.783, 'text': 'only the position of this 9 should be before this 9.', 'start': 1077.559, 'duration': 5.224}, {'end': 1083.844, 'text': 'that is the stability.', 'start': 1082.783, 'duration': 1.061}, {'end': 1089.649, 'text': 'that is the stable sort, although we can write in the sorting in the sorted array.', 'start': 1083.844, 'duration': 5.805}, {'end': 1096.759, 'text': 'you can write this 9 here and this 9 at this place, but the value is same.', 'start': 1089.649, 'duration': 7.11}, {'end': 1102.323, 'text': 'obviously the array would be sorted, but this will not maintain the stability of the sorting algorithm.', 'start': 1096.759, 'duration': 5.564}, {'end': 1104.385, 'text': 'fine if you start from here only.', 'start': 1102.323, 'duration': 2.062}, {'end': 1109.208, 'text': 'that is why, to maintain just the stability, i am going to start from here.', 'start': 1104.385, 'duration': 4.823}, {'end': 1110.97, 'text': 'now, decrement i.', 'start': 1109.208, 'duration': 1.762}, {'end': 1111.31, 'text': 'now here.', 'start': 1110.97, 'duration': 0.34}, {'end': 1112.951, 'text': 'value is 0.', 'start': 1111.31, 'duration': 1.641}, {'end': 1114.512, 'text': 'go to the index 0.', 'start': 1112.951, 'duration': 1.561}, {'end': 1115.413, 'text': 'value is 3.', 'start': 1114.512, 'duration': 0.901}, {'end': 1117.334, 'text': 'first decrement this value.', 'start': 1115.413, 'duration': 1.921}, {'end': 1118.435, 'text': 'that is 2.', 'start': 1117.334, 'duration': 1.101}, {'end': 1124.204, 'text': 'now in this output array, at index 2 store 0.', 'start': 1118.435, 'duration': 5.769}, {'end': 1125.625, 'text': 'Next decrement i.', 'start': 1124.204, 'duration': 1.421}, {'end': 1126.826, 'text': 'value is 2.', 'start': 1125.625, 'duration': 1.201}, {'end': 1128.327, 'text': 'go to the index 2.', 'start': 1126.826, 'duration': 1.501}, {'end': 1129.868, 'text': 'value is 10.', 'start': 1128.327, 'duration': 1.541}, {'end': 1131.87, 'text': 'but first of all, decrement this.', 'start': 1129.868, 'duration': 2.002}, {'end': 1133.131, 'text': 'that is 9.', 'start': 1131.87, 'duration': 1.261}], 'summary': 'Stability in sorted array is maintained by starting from the beginning and decrementing values.', 'duration': 59.956, 'max_score': 1073.175, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE1073175.jpg'}], 'start': 914.308, 'title': 'Updating, building arrays, and sorting stability', 'summary': 'Details the process of updating and building arrays, emphasizing the importance of starting at a specific index and decrementing the count array. it also explains maintaining stability in sorting through stable sort algorithms while updating values in a count array.', 'chapters': [{'end': 1042.497, 'start': 914.308, 'title': 'Updating and building arrays', 'summary': 'Explains the process of updating and building an array, detailing the steps involved and emphasizing the importance of starting the process at a specific index. it emphasizes the importance of decrementing the count array and storing the elements in the output array based on specific calculations.', 'duration': 128.189, 'highlights': ['The chapter emphasizes the importance of starting the process from a specific index, using the example of starting from the value 9 in the array.', 'It explains the process of decrementing the count array and storing the elements in the output array based on specific calculations, such as decrementing by 1 and storing at a different index.']}, {'end': 1308.874, 'start': 1042.497, 'title': 'Maintaining stability in sorting', 'summary': 'Explains the concept of stable sort in maintaining the stability of sorting algorithms while decrementing and updating values in a count array.', 'duration': 266.377, 'highlights': ['The stability of a sort is maintained by ensuring that elements with the same value retain their relative positions, demonstrated with the example of two 9s at positions 12 and 16 in the sorted array.', 'The process involves decrementing and updating values in the count array to maintain stability and ensure the correct positioning of elements in the sorted array.', 'Step-by-step explanation of decrementing and updating values in the count array to maintain stability and achieve the correct positioning of elements in the sorted array.']}], 'duration': 394.566, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE914308.jpg', 'highlights': ['The process involves decrementing and updating values in the count array to maintain stability and ensure the correct positioning of elements in the sorted array.', 'Step-by-step explanation of decrementing and updating values in the count array to maintain stability and achieve the correct positioning of elements in the sorted array.', 'The chapter emphasizes the importance of starting the process from a specific index, using the example of starting from the value 9 in the array.', 'It explains the process of decrementing the count array and storing the elements in the output array based on specific calculations, such as decrementing by 1 and storing at a different index.', 'The stability of a sort is maintained by ensuring that elements with the same value retain their relative positions, demonstrated with the example of two 9s at positions 12 and 16 in the sorted array.']}, {'end': 1662.102, 'segs': [{'end': 1388.77, 'src': 'embed', 'start': 1351.945, 'weight': 2, 'content': [{'end': 1364.73, 'text': 'fine, so i value would be n minus 1 till i, greater than equal to 0, and i minus minus.', 'start': 1351.945, 'duration': 12.785}, {'end': 1370.172, 'text': 'fine, now, within this for loop, what you will write.', 'start': 1364.73, 'duration': 5.442}, {'end': 1374.346, 'text': 'see, first of all, what we have done.', 'start': 1371.465, 'duration': 2.881}, {'end': 1383.608, 'text': 'we are going to take this value and you are going to place this value in the sorted array after finding proper position using this count array.', 'start': 1374.346, 'duration': 9.262}, {'end': 1387.43, 'text': 'fine, so take this value, this value.', 'start': 1383.608, 'duration': 3.822}, {'end': 1388.77, 'text': 'how to take this value?', 'start': 1387.43, 'duration': 1.34}], 'summary': 'Using a for loop, place a value in a sorted array after finding its proper position using a count array.', 'duration': 36.825, 'max_score': 1351.945, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE1351945.jpg'}, {'end': 1570.024, 'src': 'embed', 'start': 1542.253, 'weight': 0, 'content': [{'end': 1545.376, 'text': 'or if you will not pass the k value here you can calculate.', 'start': 1542.253, 'duration': 3.123}, {'end': 1547.898, 'text': 'within this function you can calculate the k value.', 'start': 1545.376, 'duration': 2.522}, {'end': 1552.202, 'text': 'just find out the maximum element from the given array.', 'start': 1547.898, 'duration': 4.304}, {'end': 1553.763, 'text': 'that could be the k value.', 'start': 1552.202, 'duration': 1.561}, {'end': 1559.491, 'text': 'fine. and just take, initialize a array, count.', 'start': 1553.763, 'duration': 5.728}, {'end': 1567.3, 'text': 'I guess you can take this one, this, sorry, the size would be k plus one, something like this.', 'start': 1559.491, 'duration': 7.809}, {'end': 1570.024, 'text': 'take another array, that is b and the.', 'start': 1567.3, 'duration': 2.724}], 'summary': 'Calculate k value by finding maximum element from given array and use it to initialize an array of size k+1.', 'duration': 27.771, 'max_score': 1542.253, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE1542253.jpg'}], 'start': 1308.874, 'title': 'Array sorting algorithm and count sort logic', 'summary': 'Explains the process of sorting an array using a counting algorithm and discusses the logic and implementation of count sort, revealing a time complexity of order of n plus k.', 'chapters': [{'end': 1515.607, 'start': 1308.874, 'title': 'Array sorting algorithm', 'summary': 'Explains the process of sorting an array using a counting algorithm, including decrementing values, finding proper positions, and copying elements, with specific examples and step-by-step instructions.', 'duration': 206.733, 'highlights': ['The algorithm involves decrementing values at specific indices and placing them in the sorted array while using a counting array to find proper positions, with detailed examples and step-by-step instructions.', 'The process also includes copying elements from one array to another using a for loop, providing a comprehensive understanding of the array sorting algorithm.', 'The explanation demonstrates the use of specific array indices and values, such as decrementing and storing values at calculated indexes, offering practical insights into the sorting process.']}, {'end': 1662.102, 'start': 1515.607, 'title': 'Count sort logic and time complexity', 'summary': 'Discusses the logic and implementation of count sort, covering the function structure and time complexity analysis, revealing a time complexity of order of n plus k.', 'duration': 146.495, 'highlights': ['The time complexity for count sort is analyzed to be order of n plus k, where k is the range and n is the number of elements in the array.', 'The main logic involves writing four for loops in a function, including the initialization and declaration of count array and b array, with the time complexity calculated to be order of n plus k.', 'The count sort function involves four for loops, with the time complexity calculated to be 3n plus k, or order of n plus k, where k is the range and n is the number of elements in the array.']}], 'duration': 353.228, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE1308874.jpg', 'highlights': ['The time complexity for count sort is analyzed to be order of n plus k, where k is the range and n is the number of elements in the array.', 'The count sort function involves four for loops, with the time complexity calculated to be 3n plus k, or order of n plus k, where k is the range and n is the number of elements in the array.', 'The algorithm involves decrementing values at specific indices and placing them in the sorted array while using a counting array to find proper positions, with detailed examples and step-by-step instructions.']}, {'end': 1899.9, 'segs': [{'end': 1690.155, 'src': 'embed', 'start': 1662.102, 'weight': 0, 'content': [{'end': 1664.804, 'text': 'you can sort the elements.', 'start': 1662.102, 'duration': 2.702}, {'end': 1669.546, 'text': 'one drawback of this count sort algorithm can be say this k value should be feasible.', 'start': 1664.804, 'duration': 4.742}, {'end': 1671.856, 'text': 'What does that mean?', 'start': 1671.055, 'duration': 0.801}, {'end': 1678.603, 'text': 'Let us suppose you are taking an array A and having 100 elements in the array.', 'start': 1672.296, 'duration': 6.307}, {'end': 1683.388, 'text': 'Here we have taken 17 only and in that array we have 100 elements.', 'start': 1678.783, 'duration': 4.605}, {'end': 1689.374, 'text': 'And let us suppose K value is 10, 000.', 'start': 1683.828, 'duration': 5.546}, {'end': 1690.155, 'text': 'Now what will happen?', 'start': 1689.374, 'duration': 0.781}], 'summary': 'The count sort algorithm with a k value of 10,000 is discussed in the context of a 100-element array.', 'duration': 28.053, 'max_score': 1662.102, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE1662102.jpg'}, {'end': 1784.894, 'src': 'embed', 'start': 1755.06, 'weight': 2, 'content': [{'end': 1758.002, 'text': 'fine. so this is the bound for this k.', 'start': 1755.06, 'duration': 2.942}, {'end': 1760.464, 'text': 'this k should be order of n.', 'start': 1758.002, 'duration': 2.462}, {'end': 1767.148, 'text': 'and second topic is this count sort will not work for negative values and floating point values.', 'start': 1760.464, 'duration': 6.684}, {'end': 1770.69, 'text': 'you can modify this count sort for negative values.', 'start': 1767.148, 'duration': 3.542}, {'end': 1772.912, 'text': 'after modification it can work.', 'start': 1770.69, 'duration': 2.222}, {'end': 1778.76, 'text': 'maybe you can apply some normalization methods like see minus.', 'start': 1772.912, 'duration': 5.848}, {'end': 1779.822, 'text': 'negative values are there?', 'start': 1778.76, 'duration': 1.062}, {'end': 1784.894, 'text': 'So how you can normalize this, how you can apply, how you can modify this count sort.', 'start': 1780.404, 'duration': 4.49}], 'summary': 'Bound k = order of n; count sort not for negatives; normalize with modification.', 'duration': 29.834, 'max_score': 1755.06, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE1755060.jpg'}], 'start': 1662.102, 'title': 'Count sort limitations', 'summary': 'Explains count sort limitations, including an upper bound for the k value being order of n, its inability to work for negative and floating point values, and its inability to be applied when values are different in any range, suggesting the use of radix sort instead.', 'chapters': [{'end': 1899.9, 'start': 1662.102, 'title': 'Count sort and its limitations', 'summary': 'Explains the limitations of count sort, such as the upper bound for the k value being order of n, its inability to work for negative and floating point values, and its inability to be applied when the values are different in any range, suggesting the use of radix sort instead.', 'duration': 237.798, 'highlights': ['The upper bound for the k value in count sort should be order of n, where n is the number of elements in the array.', 'Count sort will not work for negative values and floating point values, but it can be modified by applying normalization methods like adding a constant to all values to make them positive.', 'Count sort cannot be applied if the values are different in any range, making radix sort a better alternative for such scenarios.']}], 'duration': 237.798, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/pEJiGC-ObQE/pics/pEJiGC-ObQE1662102.jpg', 'highlights': ['The upper bound for the k value in count sort should be order of n, where n is the number of elements in the array.', 'Count sort will not work for negative values and floating point values, but it can be modified by applying normalization methods like adding a constant to all values to make them positive.', 'Count sort cannot be applied if the values are different in any range, making radix sort a better alternative for such scenarios.']}], 'highlights': ['The counting sort algorithm is a non-comparison sort, allowing sorting in linear time, unlike merge, quick, or heap sort with a time complexity of n log n.', 'The algorithm involves counting the number of elements with distinct key values to sort the array, providing a more efficient sorting approach compared to comparison sorts.', 'The chapter discusses the limitations of comparison sorts such as merge, quick, and heap sort, which have a best time complexity of n log n, but cannot achieve sorting in linear time like counting sort algorithm.', 'Counting distinct key values and storing their frequencies in a separate array with a size of k+1 is crucial for implementing counting sort. Distinct key values, frequencies, array size', 'The time complexity for count sort is analyzed to be order of n plus k, where k is the range and n is the number of elements in the array.', 'The count sort function involves four for loops, with the time complexity calculated to be 3n plus k, or order of n plus k, where k is the range and n is the number of elements in the array.', 'The upper bound for the k value in count sort should be order of n, where n is the number of elements in the array.', 'Count sort will not work for negative values and floating point values, but it can be modified by applying normalization methods like adding a constant to all values to make them positive.', 'Count sort cannot be applied if the values are different in any range, making radix sort a better alternative for such scenarios.']}