วีดีโอ

When the world's slowest language is used for the most computationally heavy applications, it's clear that python tells you nothing about what computers really do

Thanks for watching! Let me know what kind of content you'd like more of from me in the future! Here's the references for the video: Alzahrani, N., Vahid, F., Edgcomb, A., Nguyen, K., & Lysecky, R. (2018). Python Versus C++: An Analysis of Student Struggle on Small Coding Exercises in Introductory Programming Courses. Proceedings of the 49th ACM Technical Symposium on Computer Science Education, 86-91. doi.org/10.1145/3159450.3160586 Farag, W., Ali, S., & Deb, D. (2013). Does language choice influence the effectiveness of online introductory programming courses? Proceedings of the 14th Annual ACM SIGITE Conference on Information Technology Education, 165-170. doi.org/10.1145/2512276.2512293 Gupta, D. (2004). What is a good first programming language? Crossroads (Association for Computing Machinery), 10(4), 7-7. doi.org/10.1145/1027313.1027320 Koulouri, T., Lauria, S., & Macredie, R. D. (2015). Teaching Introductory Programming: A Quantitative Evaluation of Different Approaches. ACM Transactions on Computing Education, 14(4), 1-28. doi.org/10.1145/2662412 Lokkila, E., Christopoulos, A., & Laakso, M.-J. (2023). A Data-Driven Approach to Compare the Syntactic Difficulty of Programming Languages. Journal of Information Systems Education, 34(1), 84-93. Mannila, L., Peltomäki, M., & Salakoski, T. (2006). What about a simple language? analyzing the difficulties in learning to program. Computer Science Education, 16(3), 211-227. doi.org/10.1080/08993400600912384 Mannila, L., & de Raadt, M. (2006). An objective comparison of languages for teaching introductory programming. Proceedings of the 6th Baltic Sea Conference on Computing Education Research: Koli Calling 2006, 32-37. doi.org/10.1145/1315803.1315811 McMaster, K., Sambasivam, S., Rague, B., & Wolthuis, S. (2017). Java vs. Python Coverage of Introductory Programming Concepts: A Textbook Analysis. Information Systems Education Journal, 15(3), 4-. Siegfried, R. M., Herbert-Berger, K. G., Leune, K., & Siegfried, J. P. (2021). Trends Of Commonly Used Programming Languages in CS1 And CS2 Learning. 2021 16th International Conference on Computer Science & Education (ICCSE), 407-412. doi.org/10.1109/ICCSE51940.2021.9569444 Stefik, A., & Siebert, S. (2013). An Empirical Investigation into Programming Language Syntax. ACM Transactions on Computing Education, 13(4), 1-40. doi.org/10.1145/2534973 Wainer, J., & Xavier, E. C. (2018). A Controlled Experiment on Python vs C for an Introductory Programming Course: Students’ Outcomes. ACM Transactions on Computing Education, 18(3), 1-16. doi.org/10.1145/3152894

I liked your hex video, but I don't watch videos or sub to channels that use gen AI. I just wanted to mention this since there are a lot of us who absolutely do not interact or engage with anything that uses it. While you might save some time or money having it generate quick but bad thumbnails, you are losing an audience that will either ignore or hit the 'not interested' button. Normally I'd not say anything but, as I said, I enjoyed your hex video. I think your videos warrant better representation than genAI.

99+1 (in hexadecimal) is 154 (in decimal)

Brilliant video, however it is better if you add pseudo code or fragment code.

HOW ON EART DO YOU. HAVE LESS THAN 2K VIEWS😵😵😵 the quality of the video is awesome! Im terrible at math yet i understood it perfectly! Thank you sm for your work!

under rated youtuber!

this was super helpful T^T thank you

this is so cool bro i appreciate the animation

I don't seem to get the correct result with the following code: def quickSort(array, low, high): if high <= low: return initial_pivot_pos = (low + high) // 2 final_pivot_pos = partition(array, low, high, initial_pivot_pos) quickSort(array, low, final_pivot_pos - 1) quickSort(array, final_pivot_pos + 1, high) def partition(array, low, high, initial_pivot_pos): array[initial_pivot_pos], array[high] = array[high], array[initial_pivot_pos] final_pivot_pos = low for i in range(low, high): if array[i] <= array[high]: array[final_pivot_pos], array[i] = array[i], array[final_pivot_pos] final_pivot_pos += 1 array[high], array[final_pivot_pos] = array[final_pivot_pos], array[high] return final_pivot_pos numbers = [114, 70, 2, 8, 1, 3, 5, 6, 101, 99, 7] n = len(numbers) quickSort(numbers, 0, n - 1) print("Sorted numbers:", numbers) output -> Sorted numbers: [3, 7, 2, 5, 1, 6, 70, 101, 99, 8, 114]

# Here's the Python code, as promised! # Note that this Python is indented by two spaces, not the typical four, # in order to match with the video. def quicksort(array, low, high): if high <= low: return initial_pivot_pos = (low + high)//2 final_pivot_pos = partition(array, low, high, initial_pivot_pos) quicksort(array, low, final_pivot_pos - 1) quicksort(array, final_pivot_pos + 1, high) def partition(array, low, high, initial_pivot_pos): array[initial_pivot_pos], array[high] = array[high], array[initial_pivot_pos] final_pivot_pos = low for i in range(low, high): if array[i] <= array[high]: array[final_pivot_pos], array[i] = array[i], array[final_pivot_pos] final_pivot_pos += 1 array[high], array[final_pivot_pos] = array[final_pivot_pos], array[high] return final_pivot_pos

Interesting topic and nice video. Thank you for doing it

Good animations ! Is it done with Manim ? I like the way the text is displayed. Are you using "Write(...)" ? And which font are you using ?

Here's the link to the next video in the series (about pivot choice): th-cam.com/video/dqNuN6zzYug/w-d-xo.html The end screen is not always showing up on mobile for some reason. Thanks for watching!

I've always struggled with algorithms, but you just did an amazing job helping me understand. Thanks a lot! You earned yourself another subscriber.

Nicely explained

Thanks for watching! Let me know if you have any questions. Python code: def insertion_sort(arr): for i in range(1, len(arr)): j = i while arr[j] < arr[j-1] and j > 0: arr[j], arr[j-1] = arr[j-1], arr[j] j -= 1 Java code: import java.util.Random; public class InsertionSort{ public static void insertionSort(int [] arr){ for(int i=1; i<arr.length; i++){ for(int j=i; j > 0 && arr[j] < arr[j-1]; j--){ int tmp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = tmp; } } } public static void main(String[] args){ int size = 100; int[] arr = new int[size]; Random random = new Random(); for (int i = 0; i < size; i++) { arr[i] = random.nextInt(1000); } insertionSort(arr); for (int num : arr) { System.out.print(num + " "); } } } C++ code: #include <iostream> #include <cstdlib> #include <ctime> void insertionSort(int arr[], int size){ for(int i=1; i<size; i++){ for(int j=i; j > 0 && arr[j] < arr[j-1]; j--){ int tmp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = tmp; } } } int main(){ int size = 100; int arr [size]; for (int i = 0; i < size; i++) { arr[i] = rand() % 1000; } insertionSort(arr, size); for (int i=0; i<size; i++) { std::cout << arr[i] <<" "; } std::cout<< std::endl; return 0; }

ludicrous speed is from spaceballs

So that mean miracle algorithm for sorting

MSD Radix Sort is not inherently stable. You have to MAKE IT STABLE by implementing an extra buffer with the same size as the original list, which is extremely costly for large files. LSD Radix Sort is stable right out of the gate, no ifs or buts.

The alphabet is kinda already in number order. That’s like comparing the 100’s together

underrated AF

MSD radix sort requires knowing the maximum length before hand, making it either need comparisons to find the maximum length, or will only work in static cases, like IDs or GUIDs. In professional development we chuck an index on the column and let the database keep a sorted list so we never need to sort on the fly for large enough volumes to make this optimisation worth using over quicksort. Radix sort is cool in theory though

Nice video! I was able to understand everything easily without any prior algorithms knowledge

It's nice to know that you shouldn't just default to quick sort because it's quick. I've never heard of this algorithm but it makes sence why sometimes it would be a better option. I really appreciate your effort to provide resources for a deeper understanding and keep the video simple

Here is some Python code that goes with the video. It wouldn't fit into the show description. from itertools import chain, product import random from math import log, ceil from collections import deque from copy import deepcopy """ The sorting functions below go with the video, and are meant to provide accessible examples. They are not optimized for performance. Also, the simple function breaks for cases with negative numbers, as mentioned in the video. Please comment if you have questions or suggestions! """ #NOTE: Doesn't work for negatives or shorter numbers. See the video and the completed, 'fixed' version below def msd_radix_sort_simple(nums: list[int], radix: int = 10): if not nums: return nums num_digits = get_num_digits(nums, radix) # use a deque/queue to keep buckets in order rather than using recursion q = deque() # So we're going to append a 3-tuple of starting index, ending index, # and which_digit we are currently bucketing on. # [start, end) for the range of values in nums to process on this pass # which_digit for which digit to do (0 is ones place, then counting up) q.append((0, len(nums), num_digits-1)) while q: start, end, which_digit = q.popleft() if which_digit < 0 or end - start <= 1: continue # Put into buckets, which start as empty lists. Shouldn't # need more than O(n) additional memory. # You can use O(1) additional memory by pre-counting and # then just swapping in the original array, but that's not # stable. buckets = [[] for i in range(radix)] for num in nums[start:end]: which_bucket = get_digit_at(num, which_digit) buckets[which_bucket].append(num) next_round_start = start # generate indexes to put into queue, so that I know where # to start and end on next round/digit for bucket in buckets: next_round_end = next_round_start + len(bucket) q.append((next_round_start, next_round_end, which_digit-1)) next_round_start = next_round_end # flatten buckets and copy back into original space (can combine with above loop?) for i, num in enumerate(chain.from_iterable(buckets)): nums[start + i] = num return nums def msd_radix_sort_negatives(nums: list[int], radix: int = 10): if not nums: return nums num_digits = get_num_digits(nums, radix) q = deque() # using a queue instead of recursion # Split pos/neg into two buckets. You could also do this step last, # but that's not really in the spirit of msd_radix_sort. num_negatives = 0 # Process into positive buckets and negative buckets first. if min(nums) < 0: neg_bucket, pos_bucket = [], [] for num in nums: neg_bucket.append(num) if num < 0 else pos_bucket.append(num) num_negatives = len(neg_bucket) for i, num in enumerate(neg_bucket+pos_bucket): nums[i] = num q.append((0, num_negatives, num_digits-1)) q.append((num_negatives, len(nums), num_digits - 1)) else: q.append((0, len(nums), num_digits-1)) # Main action of radix sort, similar to simpler example above while q: start, end, which_digit = q.popleft() if which_digit < 0 or end - start <= 1: continue buckets = [[] for i in range(radix)] for num in nums[start:end]: which_bucket = get_digit_at(num, which_digit) buckets[which_bucket].append(num) next_round_start = start for bucket in buckets: next_round_end = next_round_start + len(bucket) q.append((next_round_start, next_round_end, which_digit-1)) next_round_start = next_round_end for i, num in enumerate(chain.from_iterable(buckets)): nums[start + i] = num # reverse negative portion if more than 1 negative if num_negatives > 1: for i, num in enumerate(reversed(nums[0:num_negatives])): nums[i] = num return nums def lsd_radix_sort(nums, radix: int = 10): if not nums or len(nums) == 1: return nums num_digits = get_num_digits(nums, radix) for i in range(num_digits): buckets = [[] for i in range(radix)] for num in nums: which_bucket = get_digit_at(num, i, radix) buckets[which_bucket].append(num) nums = chain.from_iterable(buckets) # Handle negatives pos_bucket, neg_bucket = [], [] for num in nums: if num < 0: neg_bucket.append(num) else: pos_bucket.append(num) # reverse negative bucket, append positive bucket, and return return neg_bucket[::-1]+pos_bucket # digits 'numbered' starting with 0 on the right/ones place def get_digit_at(num: int, which_digit: int, radix: int = 10) -> int: # Next line is necessary due to Python's idiosyncracies with modulus # and integer division on negative integers. # You can skip the next line if you're using a different langauge num = num if num >= 0 else -num return num//radix**which_digit % radix def get_num_digits(nums, radix=10): # the + 1 and - 1 handle cases like a max of 1000, # which gives 3 for number of digits when it should have 4. max_num, min_num = max(nums) + 1, min(nums) - 1 if min_num < 0: min_num = -min_num return (ceil(log(max(max_num, min_num), radix))) if __name__ == "__main__": simple = [128, 371, 941, 212, 419, 882, 141, 194, 832, 753, 555] negatives_1 = [3, 128, 100, 742, -233, 178, 22, -777, -321, -4, -7, -12, -120, -872, -412] presorted = [123, 333, 444, 555, 666, 777, 888, 999] reversed_sorted = list(reversed(presorted)) c_1 = [] c_2 = [-1] c_3 = [-100] c_4 = [-323, -324] c_5 = [2] c_6 = [782] c_7 = [731, 2] c_8 = [889, 890] c_9 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] c_10 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] c_11 = [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] c_12 = [999, 1000] c_13 = [1000, 999] c_14 = [128, 371, 941, 212, 419, 882, 0, -1, 23123123242, 141, 194, 832, 753, 555] c_15 = [128, 371, 941, 212, 419, 882, 0, -1, -23123123242, 141, 194, 832, 753, 555] c_16 = [-324, -123, -114, -41824, -1232, -123, -1, -3, 32, -81923] test_cases = [simple, negatives_1, presorted, reversed_sorted, c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8, c_9, c_10, c_11, c_12, c_13, c_14, c_15, c_16] functions = [lsd_radix_sort, msd_radix_sort_simple, msd_radix_sort_negatives] for case, function in product(test_cases, functions): result = function(case) comparison = sorted(deepcopy(case)) if result != comparison: print(f"{function.__name__}") print(result) print("Test cases finished")

I really like your videos, I was reading now about 1.58 bits quantization, and this video is perfect for learning it easier😃.

Cool vid! :D

it's quite simple to see why it works, but let's add, that it doesn't necessarily catch a loop at it's entry point. Just tell you that you're in one. I myself never would have tought of such a solution though, pretty interesting. minimized ram usage, and I'm pretty confident that the amount of checks we have to perform is also decreased compared to the first shown way, if the list is sufficiently long.

cool

I would have expected a discussion of a) types of cycles (ie, not all go back to #1 but may re-join at a later node). b) how fast does this actually find that there is a loop. based on: odd/even number of nodes in the cyclic bit (and how many non-cyclic nodes were there before the cycle starts), and how many nodes are there i a cycle. a 4- or 5-node cycle in teh examples are just best cases. How many turns through the cycle would one expect before both hare and turtle meet again in any cycles of 100, 101, 300, 356876 nodes, and how does that change when there is a non-cyclic set of 'lead-in' nodes and its length? Also, would there be an advantage in making the hare use 3 or more steps for each of the turtle, and why (and which accellerator to use when)?

Hmm. Intersection. Which way? Right looks the popular opinion...

So... how do you escape it, as promised by the video title? :P

This is awful

This is sometimes used as a programmer interview question. And if you've never run into the problem or this solution before, good f-cking luck solving it on the spot. It took PhD computer scientists six years to originally find the solution. And thus: why most white board coding interview puzzles are bad.

In your final example, you have a pointer back to an earlier segment of data, which is nice to illustrate that it doesn’t have to literally go all the way back, but the visual deviates from what you described… the final move onto eight, fast only moves one square and then waits for slow. When really, it should have moved on to nine. I don’t doubt that the algorithm works, but your example doesn’t seem to be quite accurate

If node 15 points back to node 0, your algorithm would be searching the entire list assuming that you didn't write code to remember the very first node and check to see if the first node was hit again each time the fast node moves once. Would the time it takes to perform the comparison be worth it? An evil thing to do would be to have node 15 point back to node 14.

As some constructive feedback on what I understood from this video. In these examples you could also just store the "first node" and then follow it until you reach it again, or the end. The real "strength" of this algorithm is that no matter 'when' the loop starts - you can detect it - without using an insane amount of memory. Otherwise, amazing video though !

But if the hare is moving 2 squares, couldn't it end up in a loop where it steps over tortoise every lap and never see it?

You could change the number of the tile your on, either by multiplying it with -1 or adding n (the total number of tiles). this way you still preserve the value of each tile but the moment you arrive on a tile with value greater then n or a negative one, you know you have been there.

Cool video

Ok, but how long will that algorithm allow you to remain in a cycle before it catches on?

I suppose everyone was able to escape is at long as it knows you can store something. It does not really explain the benefits of it and properly compare it to other results. In fact, this does only work for simple and single directed nodes. The example also leaks. Why can you store what is sort of ahead but not where have you been? That does not really make sense. If you can store one you can also store the other.

I confirm I can’t escape this loop.

Haha, I knew bilocation would be useful in my life.

I'm happy what I read that text

Rainworld. That is all.

Nice video but I didn't like how the question was presented. Ie: who was I? Was I a node or was I a spectator? The way its presented made it seem to me as though I was a node trying to figure out the nodes around me and I cannot have a memory. Anyways, thanks for the video I enjoyed it

i thought it was a bit different not the exact same but just base 16, tysm this was really easy!

Great video. Essentially the trade off is memory vs loop detection time