Author: Tracy

Algorithms: Insertion Sort

- Tracy Leave a comment

I wanted to make Insertion Sort part of a two-fer with Selection Sort, but it honestly took me a minute to figure out how to implement.

Continuing the card game analogy of earlier, if Selection Sort is scanning your hand and moving the smallest items down to the left, eventually ending up with a fully sorted hand…

Insertion Sort is like when a dealer gives you a new card. You look over what you’ve got so far, and add the card to its rightful spot. Similar to Selection Sort, Insertion Sort also operates on the idea of a “sorted” section and  an “unsorted” section.

When an item (let’s call it A) is larger than the element to its immediate left (B), the two aren’t swapped like in Bubble Sort. Instead, you hold on to A’s value, and then reassign B’s value to the spot array[A]. So it’s like you are sliding B’s value down the line. Then you compare A with the item in the index to the left again (C). If A > C, you can then put A down in array[B]’s original spot. Otherwise, you need to keep working to the left and shifting over elements until you find the right spot for A. When you finally assign A to its spot, you’re done with inserting A. Then you repeat the process with the next item in the “unsorted” section.

I had some issues wrapping my head around how to move items down the line, making room for the array, initially thinking about a recursive solution, but really all I needed was a while loop.

 

Algorithms: Selection Sort

- Tracy Leave a comment

I’m still working my way through implementing the basic sorting algorithms in Ruby, so maybe I should just make this a special “Intro Sorting Week.” There, sounds like a fun holiday, right? Today we’re talking selection sort.

Selection Sort

Selection sort is where you scan the array, pick the smallest element, and then swap it with the first element. Then you scan the rest of the array again, look for the next smallest element, and then swap it with the second element… Y’all see where I’m going with this?

It creates a sorted subarray on the left, and an unsorted subarray on the right. You work your way through smaller and smaller subarrays until the entire array is sorted. The algorithm is called selection sort because it repeatedly SELECTs the next smallest element and swaps it into place.

A common example of real life selection sort is when you’re playing cards and you are organizing your hand. You look over your hand, and SELECT a card and move it to its rightful place on the left (creating a sorted section), and continue working through until your hand is sorted. To me this isn’t the greatest example, because you’re not necessarily swapping the items when you select and sort a minimum card. It’s more like the cards are individually going both left and right, and often you can move multiple cards at a time. But that’s just me and how I organize my cards… back to Selection Sort.

The good: Selection sort is easy to understand. It’s also faster than bubble sort, but given how awful BS is (ever notice that bubble sort is BS?) that’s not much of an accomplishment. Selection sort is also in place, so it saves you space.

Downsides: This sorting algorithm takes a long long time. O(n^2) even in its best case. Ouch! Also it’s important to note that it’s not stable.

Here’s my selection sort done with two for loops:

Algorithms: Bubble Sort

- Tracy Leave a comment

Bubble sort! I stumbled across this clip while looking for video algorithm explanations.

Wow, even Obama knows what’s up. Bubble sort ain’t where it’s at.

The idea behind bubble sort is that given an array, you can go through the array, item by item, and compare each item with the item that is next in line. If the first item is larger (or comes after) the second item, then you should swap the pair. Continue these pair comparisons until you get to the end and then repeat. After enough times running through the array, you will come to the point where the array is sorted, and you’ll find that you’ve made no swaps.

There are some advantages to bubble sort. It’s easy to understand how it works. It uses up a constant amount of auxiliary space, it’s stable, and in the best case scenario, when the array is already sorted, it takes linear time.

Alas, bubble sort is mostly impractical. In application, bubble sort can take O(n^2). Not great.

Here’s my implementation of bubble sort in ruby. It’s really all about that swap flag.

** EDIT : After some thinking, I realized that during each iteration there is no need to check the items at the end since the largest item will “bubble up” to the top. The subarray that you are looping through will get smaller & smaller. This can be accomplished by iterating backwards over the array and decreasing the area searched, but I haven’t added this yet. Surprisingly, Bubble Sort could be a little less terrible.

Algorithms: Binary Search, Revisted

- Tracy Leave a comment

A while back I walked through the basic idea of binary search. Knowing what binary search is, and implementing it however, are very very different things.

I’ve been taking a technical interviewing course, in order to add some sort of method to the madness of my job hunt. Pretty much every day we’re whiteboarding and mock interviewing. Last night I received the following question while I stood at the whiteboard:

Number of Ones
Given a sorted bit array (values of 0, and 1) determine the number of 1’s in the array.

Input: Array of elements with values belong to the set S : { 0, 1 }
Output: Integer
Example
Input: [0, 0, 0, 1, 1, 1] => Output: 3
Input: [0, 0, 0, 0] => Output: 0

Constraints
Time Complexity: O(log n) A linear search is not acceptable for runtime.
Auxiliary Space Complexity: O(1)

So, the naive solution here would be to iterate over the entire array, and keep count of how many ones we encounter (or just use Ruby’s built in count method…). But of course to check every item in the array that would be time of O(n). Linear search runtime isn’t acceptable!!!

Several things made my mind jump to binary search. First off, the array is sorted. Second, the very obvious time complexity of O(log n). And also the entire array is binary. Isn’t that cute.

But just because you know what to do doesn’t mean that it will be easy. I decided in my approach to have a “middle_index” that I was moving around throughout the array, but I forgot to implement a start_index and an end_index to keep track of my new subarrays. GAH!!! I kept trying to make only middle_index work until I ran out of time. When I was told about the additional markers, it felt so so obvious to me, and so much simpler. In fact, when I was walking through my diagram of the problem on a test array, my hands were the natural bounds of the start_index and the end_index. It just didn’t register.

Anyways, today I went back and finished up my ruby method for this problem. I almost forgot to account for the two cases that might drive me into an infinite loop: an array of all 0’s or all 1’s. I think it will take me several more runs of this, but hopefully someday implementing binary search will be fast and breezy.

And here’s my general Ruby implementation of Binary Search.

Algorithms: Max Length of the Subarray Where the Sum of Elements is Less than or Equal to K

- Tracy Leave a comment

Here’s a recent coding challenge that I completed for a job interview. Recent as in… I finished it about 30 minutes ago… I had a devil of a time figuring out what to call this problem, but basically…

You’re given an array and an integer k. Return the length of the longest subarray where when you add up the elements inside the subarray, it’s less than or equal to k.

Input:  ( [1, 2, 3] , 3 )

Output:  2

# So, just to clarify here… All of the possible subarrays in the above example would be:

[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3].

[1, 2] is the largest subarray where the sum is less than or equal to 3. [1, 2].length = 2, so we return 2.

OKAY THEN.

I’ve been learning about creating recursive functions with the help of helper methods, or helper lambdas in Ruby’s case. For this code challenge I felt like I didn’t have time to play around with new techniques so I just created two separate methods.

find_subarrays takes an array and spits out the combination of subarrays. I called [1..-1] because I didn’t want to include the empty array that is included in the beginning.

My max_length function takes in an array and the integer k, creates a holder variable qualified_subarrays_lengths. Originally I was going to throw the entire subarrays into the variable when I found a match, but then I decided that just the length would be enough to solve the problem.

First I found all the subarrays by calling find_subarrays. Then I iterated over this array and checked to see if the sum of elements were equal to or below k (*oh look it’s our good friend Inject, thanks for being helpful!). If so I pushed the length of the subarray onto the qualified_subarrays_lengths array. After iterating across all subarrays, I just took the max value from qualified_subarrays_lengths.

TA DA.

Scroll To Top