Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

 Goal: Sort numbers without comparing themRespond to the prompts in your notes:1. How can we sort an array of single digit numbers without comparing the values to eachother?          Hint: This can be done in linear time!2. Would this work with double digit numbers?3. When would this method no longer be viable? / Why?The radix sort is a non-comparative sort! We never compare two values to eachother.If we were to use a stable sort on each digit of the numbers in a list:-Start with the least significant digit and sort by that-Move to the next significant digit and sort by that (repeat until no more digits in any of the numbers)Note: Since the sort is stable, we retain the order of the less significant digits each time. -After each pass, look to the left of the current digit, and notice that if that were the entire number the list would be sorted.Some simpler examples:If we had  `[5xx, 4xx, 2xx, 3xx, 7xx]`Since there are no duplicates in the most significant digit, the list would be ultimately sorted by the hundreds digits:`[2xx, 3xx, 4xx, 5xx, 7xx]`If we had duplicates they would use the order of the highest different value: eg ` [133, 123]`When sorting by the one's place would remain in the same order.When sorting by the ten's place they would flip to  ` [123, 133]`When sorting by the hundreds place, they woudld remain in the same order. (the tens place determines the order)end result : `[123, 133]`Write at least part of the question, AND the answer to each in your notes.4. [How many passes] do you need to make for this algorithm?5. [What operations do you want to be fast] for this algorithm to work quickly?6. [What is the runtime] of this algorithm?