Have you ever felt overwhelmed by an algorithm problem and don't know where to start? One thing I like to do when programming, is to the problem before I get to program. Otherwise, if I try to get the logic on the go, I usually end up having to debug what the hell is happenning in the program and adapt to those outputs. understand The dissadvantage of improvising on the way are: it's a loss of time, and you probably won't be able to explain to another person why does your program works with all the adjustments you had to do to it. So let's start applying the 4 steps in the image above for sorting an array of numbers from smallest to largest. Decompose: Break down a problem into smaller pieces First step is to , it would seem a big problem to sort everything in one go: how will we be able to compare everything against everything? decompose There are many ways to approach this problem, but for this example, we will use a simple sorting algorithm 'the bubble sort'. It is called bubble sort because the biggest numbers are the first to move to the correct place, and they go up like bubbles in the water. So lets start from the smallest step to the most general one: 1.- Compare 2 numbers, find the biggest, and ensure it is to the right. 2.- Repeat the comparisons until you finish with the array, as a result, the biggest number to be moved will be the first one to be in the right place. 3.- Repeat the passes through the array until all 'local' biggest numbers are in the right place. In other words, until we finish sorting. Here is how the array will be changing: Pattern matching: Finding similarities between things For we can realize that we repeat the smallest step 'comparisons' as many times as needed, so that should be inside a loop that repeats until we finish one pass. And we also see that we repeat the passes through the array until we are done sorting, that is another loop. pattern matching Abstractions: Pull out specific differences to make one general solution In we need to take out special cases, for example, in the gif above, you can see I don't compare until the very end of the array: abstractions I compare positions 0-1 until positions 9-10, (I'm using index 0 convention) next time I compare from 0-1 to 8-9, next time from 0-1 to 5-6, next time from 0-1 to 3-4, next time from 0-1 to 2-3 and then I know I finished sorting Why? How? I don't go through the whole array because it is not necessary since I already know that the last numbers are already sorted. But it will not always be with these specific positions, so we have to think, what would be a general rule that could apply to any array? My solution is to use a variable that stores the position where I made the last change in one pass of the array; I can be sure that everything to the right of the last change will already be sorted and I don't need to check those numbers again, this saves computing time :) Algorithm: List of steps to complete a task And the final part! the . algorithm I created 2 variables: * to know where I have finished with the array, my limit len * to save the last change, the one I talked about in the previous section. position How do I determine my limit? Easy, just count the pairs for the first pass through the array, the one that considers all pairs. (I will be using ruby code to illustrate) len = arr.size - 1 # len = 11-1 = 10. consider I will use a exclusive range, # so it will only include 0,1,2,3,4,5,6,7,8,9. The value for the last change will be set everytime we make a swap, that will come later, for now, let's set it to position 0 position = 0 Then make the comparison and swap the elements accordingly, don't forget to update your variable for the last changed position. position arr[i] > arr[i + ]
  arr[i], arr[i + ] = arr[i + ], arr[i]
  position = i
end if 1 1 1 is the current position in the array, in this case, it's 0. And is the next position (to compare against), in this case position 1. In ruby we can use to swap positions of the elements in the array. i i+1 arr[i], arr[i+1] = arr[i+1], arr[i] In the swap can be done like this: javascript temp = arr[i]
arr[i] = arr[i+ ]
arr[i+ ] = temp let 1 1 Use an to do the swap only when the first element is greater than the next, otherwise, we don't want to modify anything, so I end the . if if Then we repeat until we finish passing through the array... until , the limit. len Notice how variable changes until position 8, because it didn't make any movements when it was in the 9 iteration . position i In the code it is represented with a loop, I use method in ruby, but you could represent it in other languages as javascript like: #times for(var i = 0, i < len, i++) len.times |i| arr[i] > arr[i + ]
    arr[i], arr[i + ] = arr[i + ], arr[i]
    position = i
  end
end do if 1 1 1 We want that our new limit for the next time we do this again will be the last position we changed previously, so we assign it to our len. (a) And the next time we repeat this process we want to begin with a reseted position so it can be used again, thus we assign at the beginning of each repetition. (b) position = 0 We will also tell our biggest loop to do this while our len is more or equal than 1, because we want to stop when we are left with a pair of elements that we know are already sorted, element 0 and element 1 when len is 0. (c) len >= position = len.times arr[i] > arr[i + ]
      arr[i], arr[i + ] = arr[i + ], arr[i]
      position = i len = position while 1 #<--------------(c) 0 #<--------------(b) do |i| if 1 1 1 end end #<--------------(a) end Finally, we return the modified array, and the complete code will be the following: len = arr.size - len >= position = len.times arr[i] > arr[i + ]
        arr[i], arr[i + ] = arr[i + ], arr[i]
        position = i len = position arr print bubble_sort [ , , , , , , , , , , ] def bubble_sort (arr) 1 while 1 0 do |i| if 1 1 1 end end end end 10 4 6 8 5 2 4 6 8 9 22 # [ 2, 4, 4, 5, 6, 6, 8, 8, 9,10, 22] I hope this can help you as a guide to start thinking about programming solutions in the future. Thanks for reading until here :) I will leave you with a little animation representing the process that happens with the array and the variables:

Visit my Github projects!

Read My Stories

Too Long; Didn't Read

Questions about cloud security? Get answers here.

Bubble Sort Algorithm: How to Develop Your Computational Thinking

Too Long; Didn't Read

Kitpao

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Bubble Sort Algorithm: How to Develop Your Computational Thinking

Too Long; Didn't Read

Kitpao

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES