in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #9

Algorithm 5.2: Given a randomly ordered set of n integers, sort them into non-descending order using the selection sort.

So implementing selection sort. Should be easy, let’s see.

Was easy enough. Not quite as nice as writing it in Haskell but okay. The idea is that we take the smallest element put it in front, then repeat this until our list is empty. This is a bit different from the ‘traditional’ implementation which swaps the minimum result with that at the current lowest unsorted index. But the idea is the same.

Algorithm 5.6: Sorting by Partitioning. Implement quicksort.

I love quicksort. It’s such an easy and efficient algorithm.

Look at that beautiful algorithm. The idea is that you take a pivot – often the first element and create a new list which consists of elements smaller as the pivot, the pivot, and elements larger than the pivot. And you just apply quicksort to these other lists. That’s it.

 

Algorithm 6.1 Given a set of lines of text of arbitrary length, reformat the text so that no lines of more than n characters are printed. In each output line the maximum number of words that occupy less than n characters, should be printed and no world should extend across two lines. Paragraphs should also remain indented.

Good old textwrap. Let’s take a look at an example.

 

Imagine that we want to have n = 10. In this case the output is

 

We don’t want to break words which is problematic in case the word is longer than n.

I’m quite tired right now but a short explanation before going to bed. The software starts by splitting the current string into words and rebuilding the string with whitespaces. E.g. “ABC DEF” -> “ABC” ” ” “DEF”. Afterwards, it does two things:

a) In case the current-length of the temporary sentence is less than n -> append new word
b) In case the current-length is bigger, append the temporary sentence to the output and start with a new word

Here’s the example from above:

You can see that it forms:

Exactly like above.

Write a Comment

Comment