Makes sense, what are you referring to with pursuits? i have many 
Oh, い is the onyomi of the zero width space in Japanese…
2 Likes
You’re incredibly close. I think you’ve got the idea, you just don’t have the knowledge to write it out completely - which makes sense if you’re not a programmer.
The solution if you want it
What you’re looking for is what’s called a bubble sort.
What this means is:
- you start at the left side of the list
- you traverse the list, which is a fancy word for walking across it one element at a time, and for each element you:
- Compare the element you’re on with the next element in the list if there is one
- If the next element in the list is less than the element you’re currently on, swap their positions (otherwise do nothing)
- You check if the list is sorted. If the list is sorted, you’re done. If not, repeat from step 1.
Checking if the list is sorted is simple, you just walk across the list, compare every element with the next element, if at any point the next element is less than the current element, it’s not sorted and you stop. If you reach the end of the list, that means it’s sorted.
Or, if you don’t want to do the extra walk across the list (making it more efficient), you can keep track of whether you had to do any swaps. If you reach the end of the list without having to swap anything, it’s sorted and you’re done.
It’s one of many sorting algorithms, and it’s actually comparatively slow, but it’s quite simple so it works well for educational purposes.
It outperforms a bogosort though 
If I were to quickly write this up in Python (could likely be done better but I can’t be arsed):
def bubble_sort(list_to_sort):
swap_done = False
list_length = len(list_to_sort)
for i in range(list_length - 1):
if list_to_sort[i + 1] < list_to_sort[i]:
swap_done = True
list_to_sort[i + 1], list_to_sort[i] = list_to_sort[i], list_to_sort[i + 1]
if swap_done:
return bubble_sort(list_to_sort)
return list_to_sort
4 Likes
I will check it only because you told me I’m incredibly close and don’t have technical knowledge 
Fuck, I even thought about just doing a shorter version of the first steps and just go though the list many times but for some reason I believed I wasn’t allowed to and had to sort them all before arriving at the end 
but I feel quite satisfied honestly for where I got.
One thing I don’t understand is why doing it that way? Simplicity?
Can’t wait to start doing this stuff
1 Like
Basically. You’ll never find this one used “in the wild” so to speak - it’s horribly inefficient, and you’ll only really see it as a teaching tool.
A more often used algorithm is merge sort or a variation thereof, which is also quite simple:
- if your list is one element long, it’s sorted
- if your list is more than one element long, split it into two
- merge sort both lists (as in, feed both the resulting lists through this whole thing starting at step 1)
- compare the first element of both lists, take the lowest of the two off its list and tack it onto a new list
- repeat step 4 until one list is empty, then just tack the remainder of the other list onto the result
You’ll notice you’re basically going through this whole checklist a bunch of time as part of step 3. That’s called recursion, and it’s pretty common (you can do it without recursion, but using recursion makes for an easier to read algorithm).
The reason this works is in the innermost merge sort, you just have two lists of length 1. Those are sorted, they get handled in the merge sort on top of that, meaning you just tack them onto a new list in sorted order. Then the layer on top of that has two list of length 2, which you know to be sorted (because they just came out of a sorting algorithm), so you can efficiently construct a sorted list from those two lists. That sorted list then gets passed up one more level along with another one, and so on, until your whole list is sorted.
Or, in python, for comparison (fair warning, it’s a quick writeup and I’ve put it through all of a single test case, so it might be broken as hell):
def merge_sort(list_to_sort):
length = len(list_to_sort)
if length == 1:
return list_to_sort
mid_point = int(length / 2)
left = list_to_sort[:mid_point]
right = list_to_sort[mid_point:]
left = merge_sort(left)
right = merge_sort(right)
result = []
while len(left) > 0 and len(right) > 0:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result += left
result += right
return result
As you can see, that’s a fair bit more code (I could shorten it but that wouldn’t help the readability - and besides the same is true for the bubble sort), but it’s way more efficient because you don’t end up walking over the whole list every time comparing each element to the next, instead splitting the list into smaller chunks to sort and then handling those efficiently afterwards because you know the chunks are sorted already so you can treat them as such.
I think most modern programming languages offering a sorting function perform either a quicksort or a timsort because they’re even faster, but they both operate under the same principle of “divide the data into chunks, make sure you know those chunks are sorted, and merge them back into a single list”.
4 Likes
@mariodesu algorithms which rely on any sort of data splitting are often referred to as divide & conquer. That’s a part of your new curriculum, though oddly at the very end in chapter 4.
3 Likes
…which is another CS-vs-programming thing, by the way. If you’re writing a program to do something, you just assume your language’s sort implementation is fine, and use it. CS is interested in things like “how does the runtime of this algorithm go up as the number of items being sorted increases?”, “is there a theoretical upper limit to how well any sort algorithm can scale? can we prove that?” and other maths-type reasoning.
5 Likes
Yeah, programming saves those types of questions for when you really don’t have anywhere else to look. Out of all the things that could affect performance, your sorting algorithm is one of the least likely culprits.
I mean, if I had a program that I knew would be sorting billions of lists continuously but not doing much in the way of I/O or whatever, I might consider it, but with anything I’ve encountered in my career so far there hasn’t been a performance improvement I could’ve made with a sorting algorithm that I couldn’t have made tenfold with a database index.
4 Likes
Not to mention the times one actually needs a sorting algorithm .
4 Likes
Fairly regularly if you count an ORDER BY clause in your query
Sorting data is super common, but it’s also something you probably want to leave to whatever you’re using unless you have a good reason not to
3 Likes
Pretty much. I haven’t been interacting with SQL databases for a longer while and in the scripts and tooling I write on a daily basis I rarely use sorting and only care about the order of data being deterministic.
3 Likes
Most of my software is either user-facing or outputs data that is going to be user-facing at some point, so sorting becomes a pretty common thing, whether it’s by some timestamp or by name or whatever.
Though there are definitely plenty of cases where I really couldn’t care less, usually when something’s just for automated processing and/or passing on to some other system.
2 Likes
Easy money with one element lists 
What if it’s spare?
So basically dividing and doing step 1) over each one
1 Like
What do you mean spare? As in having an odd number of elements? Doesn’t really matter.
Say you have three elements.
One part of your list is going to be one element. That’s sorted. Done.
The other part of your list is going to be two elements. That’s gonna get split into two one element lists. Both are sorted, so they get merged into a sorted two element list.
Then you get a one element list and a two element list, both are sorted. Merge them into a three element sorted list.
You now have a sorted three element list.
Doing all the steps over each one, including the dividing and doing all the steps over the parts.
You end up dividing repeatedly until you end up with single elements, basically.
2 Likes
No I’m asking you to sort 5 numbers. If the numbers were [10,11,13,21,1] your instructions would need to make them into [1,10,11,13,21].
Very possible. But you probably have realized that if you don’t know what numbers will be in the list then you can’t refer to the numbers by their value. You know they’re are 5 and I told you you can refer to them in order (e.g. 1st number, 2nd number, etc.). I also said that the person doing the problem understands “greater than” and “less than”.
With just those things you can solve it. It’s a very hard problem for someone with no CS experience, so it was more of a way for me to highlight what I meant by “thinking like a CS student”. The “normal” approach is to just look at it and “put the smallest number first, second smallest number second,…”. But for CS and programming we need a formula or algorithm that will process our data right, every time, for any valid input. Because of this, it requires you to abstract your thinking. Furthermore, you need to be very precise and exact about what you’re doing to what numbers specifically.
Assuming a and b is the 1st and 2nd number, you are on the right track for sure. We can compare two side by side numbers and swap them if the one on the left is smaller (this would reverse the sort tho).
Step 3 and 4 are not clear, though. Even stopping the whole computer roleplay, as an individual human I do not understand your instructions are for that. I think we need some more specificity around the whole repeating aspect.
4 Likes
Chads using bogosort can’t relate
4 Likes
Yeah, confused the word
Anyway, it’s all clear thanks!
1 Like
We can do better worse
3 Likes
Yes, got it in the end, I was mentally fried yesterday afternoon…
This was a very useful consideration
Ok I realize, let me try to explain it better.
So as I understand my task, I need to create an algorithm that can reorder any 5 elements in a crescent sequence, and the only parameter I’m aware of is that element x can be major or minor than element y.
Background info: [a,b,c,d,e] are not the 5 elements’ values, but their positions, so that also after swapping position they remain [a,b,c,d,e].
Here’s my algorithm:
algorithm
- Compare ‘a’ with ‘b’.
-
2a) (hypothesis: ‘a’ is major) Swap ‘a’ with ‘b’.
-
2b) (hypothesis: ‘b’ is major) Don’t do anything.
- Compare ‘a’ with ‘c’.
-
4a) (hypothesis: ‘a’ is major) Swap ‘a’ with ‘c’.
-
4b) (hypothesis: ‘c’ is major) Don’t do anything.
- Compare ‘a’ with ‘d’.
-
6a) (hypothesis: ‘a’ is major) Swap ‘a’ with ‘d’.
-
6b) (hypothesis: ‘d’ is major) Don’t do anything.
- Compare ‘a’ with ‘e’.
-
8a) (hypothesis: ‘a’ is major) Swap ‘a’ with ‘e’.
-
8b) (hypothesis: ‘e’ is major) Don’t do anything.
- Compare ‘b’ with ‘c’.
-
10a) (hypothesis: ‘b’ is major) Swap ‘b’ with ‘c’.
-
10b) (hypothesis: ‘c’ is major) Don’t do anything.
- Compare ‘b’ with ‘d’
-
12a) (hypothesis: ‘b’ is major) Swap ‘b’ with ‘d’.
-
12b) (hypothesis: ‘d’ is major) Don’t do anything.
- Compare ‘b’ with ‘e’.
-
14a) (hypothesis: ‘b’ is major) Swap ‘b’ with ‘e’.
-
14b) (hypothesis: ‘e’ is major) Don’t do anything.
- Compare ‘c’ with ‘d’.
-
16a) (hypothesis: ‘c’ is major) Swap ‘c’ with ‘d’.
-
16b) (hypothesis: ‘d’ is major) Don’t do anything.
- Compare ‘c’ with ‘e’.
-
18a) (hypothesis: ‘c’ is major) Swap ‘c’ with ‘e’.
-
18b) (hypothesis: ‘e’ is major) Don’t do anything.
- Compare ‘d’ with ‘e’.
-
20a) (hypothesis: ‘d’ is major) Swap ‘d’ with ‘e’.
-
20b) (hypothesis: ‘e’ is major) Don’t do anything.
It can become 30 steps if we need to add one extra step “x) check for alignment” (crescent scale is achieved?)
This is what I thought about before @yamitenshi revealed the trick
Edit, of course this process can end sooner than the last step in case alignment is achieved.
1 Like
Let me run a few test cases for you!
input: [4,3,2,5,1] → [1,2,3,4,5]
input: [5,4,3,2,1] → [1,2,3,4,5]
Looks like it works! Good job! Thats pretty impressive that you managed to get there without being exposed to this sort of stuff really. Maybe you’ve got some talent for it! Interestingly enough, you also didn’t arrive at what I personally thought was the easiest solution to arrive at. What I kinda expected you to come up with was:
- 1a) if a > b, swap a and b
- 1b) if b > c, swap b and c
- 1c) if c > d, swap c and d
- 1d) if d > e, swap d and e
- If you swapped a number in step 1, repeat step 1.
I take it you mean check through the list once to make sure its sorted? The great thing is that you don’t have to! When you have an algorithm that you can prove can’t have an unsorted number in the result, you don’t need to check.
5 Likes