DEV Community: Mehmed Duhovic

JavaScript – Function Declarations vs. Function Expressions

Mehmed Duhovic — Tue, 13 Jul 2021 20:31:30 +0000

What are the differences between function declarations and function expressions? We'll find out in this article.

We know how to write functions in JS, right? We use the function keyword, whose main role is to create a function. But did you know that there are two function form variants (or more, depending on the context)? If not, take a look at the code snippet below and try to understand the syntactical and logical differences.

function calculateSomethingForMePlease() {
 // here goes logic - function declaration
}
let findTheClosestBeachNearMe = function(lat, lng) {
 // here goes logic - function expression
}

Function Declaration

The first variant is called the function declaration because it is an expression by itself. We write the JavaScript keyword function followed by the name of the function. The parser then associates the function keyword with the name of the function during the compilation phase. Why is this useful? Well, we can call the function not only after the declaration but also before the declaration!

calculateSomethingForMePlease(); // this is valid in JS

function calculateSomethingForMePlease() {
 // here goes logic
}

In most other programming languages this doesn't work, but JS has this cool concept called hoisting, during which it grabs the whole function objects, and makes them available anywhere in our file by pushing it to the top, compared to the (SPOILER ALERT) the next variant that we will see.

Function Expression

The function expression is a function that is assigned to a certain variable. As you might have guessed - the function itself is not available nor associated to the variable until the statement line has been reached during execution.

findTheClosestBeachNearMe(43.94151, 17.4194); // OH NO, HELL BREAKS LOOSE!

let findTheClosestBeachNearMe = function(lat, lng) {
 // here goes logic - function expression
}

Function Declaration vs. Function Expression

So we might ask ourselves - when can we use one or the other?

As seen above - we might use function declarations to create standalone functions, that are visible before any other code. (compared to function expressions which are only visible when the interpreter reaches the line of code).

Otherwise - we might be inclined to keep our global scope clean (due to hoisting declarations can pollute the global namespace). Then we would use IIFEs (Immediately invoked Function Expressions, quite a name huh?).

(function (bar){
  //Here we have an encapsulated local scope and the ability to return things
  return 'baz'
})('foo')

If you've ever worked with asynchronous code, you've might also come across callbacks which are another form of function expressions.

asyncFn(function (){
  console.log('Done!')
})

Yet another form of function expression is the named functions inside objects. Look below for an example:

const earth = {
  population: '7.674 billion',
  getPopulation: function() {
    return this.population;
  }
};

Final Words

As you can see - there are more differences between the two forms than just structural, and each can fit a certain use case better. Read up on this Stack Overflow question for additional examples and discussion regarding performance, mutability and availability.

CSS Gradients: An Introduction

Mehmed Duhovic — Fri, 14 May 2021 21:04:12 +0000

This article will cover CSS gradients and take a took at some real-life uses for them.

Most of the time we use solid background colors to style our web application, using the background property. There is actually more to the background property, as it is a shorthand for many different properties including:

background-image - can set a background image or generate a color gradient (we will talk about this!)
background-position - can set the position of the background image
background-size - sets the size of the rendered background image
background-repeat - can set the 'repeat' property of the image in order to fill the entire element
background-origin - can set the background positioning, being relative to the element's border-box, padding-box or content-box
background-color - sets a specific background color which will render behind any set background image

While using some of these single properties, we should also keep in mind that if we at a later time style elements with the background property, we will reset all the others back to their initial value. We should instead write individual properties unless we are definitely sure that we won't override them later.

Background-image and CSS gradients

We usually use background-image property to accept a path to an image URL (background-image: url(url-to-image.png) in order to set the image as the element's background. But the background-property actually serves one additional use - we can define gradients, which are actually extremely useful effects. Let us see them in use:

  <div class="image-wrapper wrapper-1">
    <span>Two-Color linear gradient</span>
    <img
      src="https://i.pinimg.com/originals/02/c5/13/02c5130828505d0365ca6afdb047c888.png"
    />
  </div>
  <div class="image-wrapper wrapper-2">
    <span>Two-Color linear gradient with an angle</span>
    <img
      src="https://i.pinimg.com/originals/02/c5/13/02c5130828505d0365ca6afdb047c888.png"
    />
  </div>

.image-wrapper {
  position: relative;
  border-radius: 12px;
  border: 1px solid black;
  height: 300px;
  display: flex;
  justify-content: center;
  margin-bottom: 10px;
}

span {
  position: absolute;
  top: 10px;
  left: 10px;
  width: 150px;
  font-size: 14px;
  color: white;
}

.wrapper-1 {
  background: linear-gradient(#e66465, #9198e5); /* linear gradient example */
}

.wrapper-2 {
  background: linear-gradient(45deg, #e66465, #9198e5); /* linear gradient example */
}

The two listing above would produce the following two images:

CSS Gradients Example - Using Two-Color Linear Gradient

The linear-gradient function used above consists of three basic parameters that define its behavior: angle, starting color, and ending color. In the first example (the basic two-color linear gradient) we omitted the angle so the style was automatically reverted to the default top to bottom angle.

The second example actually has a set angle of 45 degrees, and it visually appears to be different than the first - even though they use the same colors! We can set gradient angles using several different controls. For example, by using predefined keywords such as to top, to bottom, or even a corner such as to bottom right. In each of these cases, the gradient would start from the top, from the bottom, or from the bottom-right corner of the element.

In the second example above, using a precise angle, we used degrees as the unit. 0deg would be equivalent to the to top command, and by increasing the degree value we would move the gradient clockwise around the circle. We can also use rad (or radians), turn (turns) or grad (gradians). For more information about angles, please click here.

Multiple color stops

Now let us take a look at this:

.wrapper-3 {
  background: linear-gradient(45deg, #e66465, #9198e5, #12045b, #1afe49);
}

.wrapper-4 {
  background: linear-gradient(
    45deg,
    #e66465 0%,
    #9198e5 20%,
    #12045b 40%,
    #1afe49 80%
  );
}

Which would produce the following (.wrapper-3 is the left image, while .wrapper-4 is the right image in the listing):

CSS Gradients Example -Multi colored gradients

Above we defined gradients using more than two colors, each of which are called color stops. The listing above has a gradient function that accepts four colors. New colors can be simply inserted by adding them to the linear-gradient function. We can add any number of colors, separated by a comma, and the function will spread them evenly. We can additionally explicitly set the position of the color stops, and they do not need to be evenly spaced. Instead of percentages, we could also use pixels, ems, and any other length units.

Hard stops and repeating linear gradients

.wrapper-5 {
  background: linear-gradient(90deg, green 33%, white 33%, white 66%, red 66%);
}

.wrapper-6 {
  background-image: repeating-linear-gradient(
    90deg,
    blue 20px,
    salmon 40px,
    red 80px,
    blue 120px
  );
}

Above inside the .wrapper-5 block we set the colors inside the linear-gradient() function at the same position. This will have the effect of instant switch between colors, rather than a smooth transition.

CSS Gradients - Linear gradient with a hard stop and repeating linear gradient

We created the left image (having the appearance of the Italian flag) using hard stops. The right image is created using a new function - repeating-linear-gradient() in which - wait for it - the pattern repeats, alternating between blue, salmon, and red colors.

Radial and repeating radial gradients

.wrapper-7 {
  background-image: radial-gradient(red, black);
}

.wrapper-8 {
  background-image: repeating-radial-gradient(
    circle,
    red 0,
    red 30px,
    black 30px,
    black 60px
  );
}

CSS Gradients - Radial and Repeating radial gradient

We have created some really cool effects above, using a new type of gradient or the radial-gradient. This type of gradients starts at a single point and proceeds outward in all directions. By default, it is centered, and transitions evenly to every corner. We can also change the appearance of the radial gradient, by specifying where the gradient should be centered, or by making the gradient a circle rather than an ellipse. On the right, we used the repeating-radial-gradient() function in order to repeat the pattern in concentric rings.

Final Words

Gradients can be a lot more expressive and complex and in this article, we only mentioned the basics of using them. For a more detailed explanation, you can visit the official developer documentation forlinear-gradient() here, for radial-gradient() here, and from there you can start exploring the concepts more deeply.

Here we have our codepen for this article:

Please check other blog posts on thedukh.com.

On CSS Shorthand Properties

Mehmed Duhovic — Thu, 29 Apr 2021 23:14:35 +0000

Let us remind ourselves what we did in the last two articles. We created a cute card view consisting of our favorite Pokemon (and quite a simple one too!). Using that card view we explained two important concepts in CSS - cascades, and inheritance. Using the same view we will now go through another CSS topic - Shorthand Properties.

For the article about cascades click here, and for the article about inheritance here. This is the third part of basic CSS methodologies, and it will be on the topic of CSS Shorthand Properties.

Shorthand properties are properties that we can use to set several other related properties at once. Some common shorthand properties are background, font, padding, margin, and border.

For example - the font shorthand property allows us to change several other font properties - some of which are font-style, font-weight, font-size, line-height, and font-family. Shorthand properties are useful simply because they keep our code clean and short.

How shorthands override other properties

The thing with shorthand values is that we don't need to write complete styles. For example, on the official MDN Web Docs, we have different variations of the font property. Sometimes we can omit certain values, but that doesn't mean that the omitted values are gone - they are just set to the initial value. Let us import a new font and set it up using the font shorthand property to illustrate this.

@import url("https://fonts.googleapis.com/css2?family=Antonio:wght@300;400;500&display=swap");

#main-list a {
  font: 20px Antonio; /* new font */
  /* ... */
}

This would of course change the look of our Pokemon Cards:

List of favorite Pokemon - new font property!

But more importantly, by checking the computed tab inside our Dev Tools we see that we applied more styles to our element (not only the font-family and font-size).

Initial properties added by using the font shorthand property

We didn't define any of the additional font properties such as font-style, font-variant, font-weight, font-stretch, or font-height. Using the shorthand properties we could override other styles that would be set by default, or inherited by other elements, so be careful if you set a certain style to an element!

The order of shorthand values

When it comes to the order of the values, CSS is quite flexible - we can set the border shorthand property in quite a few different ways (although we should always use the best practice). For example - we can write border: 5px solid red; or border: red 5px solid; and our smart browser would understand which value specifies the width, which the color and which the border style.

We also have the more ambiguous properties, which couldn't be written as freely, for example, the properties for padding and margin that specify values for each of the four sides of the element. For these properties, the values are in always the clockwise order - starting at the top. Top, Right, Bottom, Left.

Let us now set our anchor padding using the shorthand property!

#main-list a {
  font: 20px Antonio;
  color: inherit;
  text-decoration: inherit;
  background-color: pink;
  padding: 20px 5px 10px 35px;
  margin: 10px;
  display: flex;
  flex-direction: column;
  text-align: center;
  border-radius: 6px;
}

Using the shorthand padding property

You can see the result above. Yeah, it looks clunky and uneven, but we wrote this just to illustrate the concept.

We can also use the truncated notation. We can omit some values, and the property will still pick up values from the opposite side. For example, if we specify three values, the left and the right side will use the second one, if we specify two values, the top, and the bottom value will use the first one, and one value will apply to every side.

div {
    padding: 30px; /* equivalent to padding: 30px 30px 30px 30px */
    margin: 20px 15px; /* equivalent to margin: 20px 15px 20px 15px */

    border-color: black;
    border-style: dashed;
    border-width: 10px 30px 12px; /* equivalent to border-width: 10px 30px 12px 30px; */
}

Above, for the border-width property we've given three properties - for top, right and bottom. No left value is specified, so the left side will take the same value as the right side (30 pixels in this case). Below we will set the padding using only two values (applying the first value to top and bottom sides, and the second value to left-right sides).

#main-list a {
  font: 20px Antonio;
  color: inherit;
  text-decoration: inherit;
  background-color: pink;
  padding: 10px 30px;
  margin: 10px;
  display: flex;
  flex-direction: column;
  text-align: center;
  border-radius: 6px;
}

Using the two-value shorthand for padding

Final Words

With this article we conclude the three-part CSS fundamentals regarding structure and style appliance. We learned what styles are applied to the elements and how the properties of those elements are determined.

Here we have our codepen for this article:

If you liked this article maybe you'll like more stuff on thedukh.com.

CSS Inheritance in more detail

Mehmed Duhovic — Mon, 19 Apr 2021 20:36:48 +0000

Let's take a look at the pen in the last article here. We notice that we set the font-family property to the Google Font we imported in our stylesheet, and we set it using the * (Asterix) selector, which basically selects all elements in our stylesheet. What would happen if instead of the * selector, we would use the <body> selector?

Let's look at the result:

body {
  font-family: Lato; /* this is a property that will be applied to all the child elements in the DOM */
}

List of my favorite Pokemon

Nothing changes! Although the procedure in which the font-family property is applied to the document is different when using * and body, we notice something more interesting. All of our ancestor elements within the <body> will inherit this font; there is no need to apply it explicitly to each child element inside our stylesheet.

The image below shows how properties are passed down through the DOM to their child elements.

Inherited properties passing down the DOM

An important notion to keep in mind though is that not all properties can be inherited. Some of the most common properties that can be inheritable are color, font, font-family, font-size, font-weight, line-height, letter-spacing, text-align, white-space, and more text-related properties. List properties also inherit, and some of the most common inheritable list properties are list-style, list-style-type, list-style-position, and list-style-image. You can see a full list here

Using the special values

Inheritance can be manipulated further using two special values: initial and inherit.

Inherit can force inheritance in places where the cascade is preventing it. This will cause the element to inherit any value from the parent element. How we can test this? If you remember we set the text color of our anchor to be black, and we removed the underline which is the original style. What if we move those two rulesets to the parent element (#main-list). We will break our styles!

#main-list {
  list-style: none;
  display: flex;
  color: black; /* we moved these two lines here */
  text-decoration: none;
}

#main-list a {
  /*color: black;
  text-decoration: none; */
  background-color: pink;
  padding: 20px;
  margin: 10px;
  display: inline-block;
  text-align: center;
  border-radius: 6px;
}

Pokemon list. Notice how the CSS ‘broke’ (the anchor links have the default styling)

In order to inherit the rulesets for color and text-decoration from our parent element, we will use the value of inherit for both properties. This is beneficial because now we can edit the parent ruleset (for example using JavaScript) and the anchor should apply these newly changed rules. We can also use the inherit keyword to force the inheritance of a property which is not normally inherited, such as border or padding. With the changes below the script should look as before (having black text and no underline decoration):

#main-list a {
  color: inherit;
  text-decoration: inherit;
  background-color: pink;
  padding: 20px;
  margin: 10px;
  display: inline-block;
  text-align: center;
  border-radius: 6px;
}

Initial keyword on the other hand is used when we already have styles applied that we want to undo. Every CSS property by default, has an initial value, and by using the initial keyword we actually reset the rule to that default value. (a warning if you want to use initial in your styles though, it is not supported in IE or Opera Mini).

In the listing below we have the CSS in which the color has been set to red inside the anchor, but inside the rare class we set the color to initial. Because the color property is by default black (color: black) , the rare element will be black.

#main-list a {
  color: red;
  text-decoration: inherit;
  background-color: pink;
  padding: 20px;
  margin: 10px;
  display: inline-block;
  text-align: center;
  border-radius: 6px;
}

#main-list .rare {
  background-color: salmon;
  color: initial;
}

Result of using the listing above

And that is it regarding inheritance. As you probably noticed the concept is tightly coupled with the idea behind cascades and as a matter of fact many starters kinda mix these two concepts up! Hope that this article cleared a bit of the fog regarding inheritance and cascades!

The result

Here we have our codepen for this article:

If you liked this article maybe you'll like more stuff on thedukh.com.

How do CSS cascades work?

Mehmed Duhovic — Sun, 11 Apr 2021 14:14:20 +0000

We need to know how the different CSS rules are applied to elements so that we can write clean, structural styles. We need to know how to actually add styles to elements with plain classes, or ids, or elements that might be children of other elements. This is usually straightforward, we just create a simple selector and the styling rules will do the work on their own. But, when we write styles for heavier applications, the code complexity will grow accordingly. In that case, we might come across situations in which some of our rules conflict with each other, and we need to predict how certain rulesets will behave, and how to write rules in order to create the best stylesheets possible.

Knowing cascades might come in handy in that case.

Creating Some Structure

We will learn cascades by building a simple card view consisting of my favorite pokemon:

List of My Favorite Pokemon

To start, we will create a simple HTML structure and an accompanying stylesheet. We will do this in codepen, to reduce the configuration time of writing a full HTML document and chaining a stylesheet to id. (Yeah we will save 5 seconds tops 😀 ). Our code will look like in the following listing:

<div class="favorite-pokemon-container">
  <h1 id="main-title" class="title">List of my favorite pokemon!</h1>
  <ul id="main-list" class="list">
    <li>
      <a href="https://www.pokemon.com/us/pokedex/pikachu"
        >Pikachu
        <img
          src="https://assets.pokemon.com/assets/cms2/img/pokedex/full/025.png"
          width="100"
      /></a>
    </li>
    <li>
      <a href="https://assets.pokemon.com/assets/cms2/img/pokedex/full/006.png"
        >Charizard<img
          src="https://assets.pokemon.com/assets/cms2/img/pokedex/full/006.png"
          width="100"
      /></a>
    </li>
    <li>
      <a href="https://assets.pokemon.com/assets/cms2/img/pokedex/full/031.png"
        >Nidoqueen<img
          src="https://assets.pokemon.com/assets/cms2/img/pokedex/full/031.png"
          width="100"
      /></a>
    </li>
    <li>
      <a
        class="rare"
        href="https://assets.pokemon.com/assets/cms2/img/pokedex/full/144.png"
        >Articuno<img
          src="https://assets.pokemon.com/assets/cms2/img/pokedex/full/144.png"
          width="100"
      /></a>
    </li>
    <li>
      <a href="https://assets.pokemon.com/assets/cms2/img/pokedex/full/051.png"
        >Dugtrio<img
          src="https://assets.pokemon.com/assets/cms2/img/pokedex/full/051.png"
          width="100"
      /></a>
    </li>
    <li>
      <a href="https://assets.pokemon.com/assets/cms2/img/pokedex/full/094.png"
        >Gengar<img
          src="https://assets.pokemon.com/assets/cms2/img/pokedex/full/094.png"
          width="100"
      /></a>
    </li>
  </ul>
</div>

Basic Structure

Conflicts arise when two or more rules target the same element on our page. We will show how this is possible. We will target the heading, to change its style. If we look closely we will see that we can target the header in a couple of different ways, some listed below:

h1 {
  color: red; /* tag */
}
#main-title {
  color: blue; /* id */
}
.title {
  color: black; /* class */
}

All three of these rules target the same element, and all of those rules are attempting to change the color of the text of the heading.

Which style does the browser apply? The browser follows a set of rules to determine which ruleset will apply. In our case, according to CSS rules, the second declaration, which uses the ID declarator will win, and the title will have the color blue. We call this set of rules a cascade. The cascade will determine how different conflicts are resolved, and it is one of the fundamentals of the CSS scripting language. The cascade is often misunderstood and many developers have issues with it (how many of us used and misused the !important operator just because?)

How Cascade Resolves a Conflict?

When a conflicting declaration happens, the cascade takes a couple of things into account:

The origin of the stylesheet, or where the styles come from. Styles that we write are applied in conjunction with the browser’s default styles
Specificity of the selectors, which selectors take precedence
Source order – order in which styles are declared in the stylesheets

With these rules, the browsers can behave accordingly when resolving any ambiguous declaration conflicts in the CSS.

Origin-based conflicts

These ones are not so well known. Basically, every browser has its own sets of default styles, which the browser applies when no other styles apply. These are called browser styles. They usually have lower priority than your stylesheets (called author styles), but they generally do basic styling, they style headings, paragraphs, lists and give them that basic browser look (top and bottom margins, left paddings, blue colors to links, etc.).

In our example, we can see some basic browser styles – our lists have a list-style-type of disc applied to it to produce those bullet points. Additionally, links are blue and underlined. Headings have top and bottom margins.

These can be simply overridden using our own styles. Considering that they don’t do anything unexpected and that they can be easily overridden, they are actually quite simple to resolve, by just setting your own values in the stylesheet. You can see a list of all the overridden browser styles by opening your developer tools and looking at the elements section.

The !important operator

Apart from browser and author rulesets, there is another operator that overrides every other in our stylesheet. If our styles have declarations that are marked as important, by adding !important to the end of the declaration, then those declarations are treated as higher-priority rulesets. In the order of preference, they come before every other cascading style. It is an easy fix, and it solves the issue now, but we can run into a lot of trouble later down the road especially if we keep adding !important to multiple declarations. I won’t advise you against it, but its use should be controlled.

Specificity-based conflicts

If conflicting declarations can’t be resolved based on their origin, the browser tries to resolve them based on their specificity. Specificity is usually evaluated in two parts: styles applied inline in the HTML and styles applied using a selector.

Inline styles

If we apply styles using the HTML’s style attribute, the declarations are only applied to that element, and they override any other declaration which you might have. They have no selector because they are applied directly to the element. For example, in our pokemon list, we have one pokemon with the ‘rare’ link. We can apply inline styles to that specific element.

    <li>
      <a
        class="rare"
        style="background-color: purple;"
        href="https://assets.pokemon.com/assets/cms2/img/pokedex/full/144.png"
        >Articuno<img
          src="https://assets.pokemon.com/assets/cms2/img/pokedex/full/144.png"
          width="100"
      /></a>
    </li>

This sets the background-color of only this element to purple.

The only way inline declarations can be overridden is by using the !important operator, to actually shift the style into a higher-priority origin. If the inline styles themselves are marked as !important then there is actually nothing that can override them. Thus it is always better to change our styles in our stylesheets and not directly in our HTML code. We will revert this change and do some selector work.

Selector Styles

Now here is when it gets really interesting. When we actually talk about CSS cascades, we mostly only reference selector specificity. For example, a selector that has two classes has higher specificity than a selector with only one class.

If one rule sets the background color to orange, but another with a higher specificity sets the background color to green then the green styling is applied. What gives? If we try to override our ‘rare’ element with a class selector… it doesn’t work! Because the first selector is more specific than the second, it consists of an ID and a tag name, and the second only consists of a class name.

#main-list .rare {
  background-color: salmon; /* this rule has an ID and it overrides the one below that consists of two classes */
}
.list .rate {
  background-color: grey;
}

Why? Because an ID selector has a higher specificity than a class selector, and to be more precise a single ID selector has a higher specificity than a class selector, and a class selector has a higher specificity than a tag selector.

ID > Class > Tag

Basically, if a selector has an ID, it overwrites any of the other styles, if they have the same amount of IDs then the selector with the most classes wins, and otherwise, the selector with the most tags wins. For example, if we would like to select the title again, and to change its colors we would do something similar to the following listing.

html body div h1 {
  color: red; /* fifth most specific rule, consists of tags */
}

body .favorite-pokemon-container h1 {
  color: blue; /* fourth most specific rule, has a class */
}

.title {
  color: pink; /* third most specific rule, only one class */
}

.favorite-pokemon-container .title {
  color: skyblue; /* second most specific rule, having two classes */
}

#main-title {
  color: orange; /* most specific rule, only one ID */
}

The most specific selector here would be the last one, which consists of only one ID, then the one that consists of two class names, then the one with one class name, then the first two, with the second having precedence over the first one due to the class used.

More often than not, declarations that have no effect on your styles happen due to more specific rules overriding it. Beginner developers often use IDs which by itself create a very high specificity, making it really hard later to override them. We can only override them by using a more specific ID. Just to recap what we’ve learned one more time – IDs are always more specific than anything else, more IDs are more specific than just one, classes are behind IDs when it comes to specificity, and tags are least specific.

Best practices for writing declarations when overriding other styles are: creating rulesets that have a higher specificity so that they override an existing ruleset (using more specific elements), or reducing the specificity of the ruleset we want to override so that it is easier to style it with new declarations.

Source-order conflicts

These are the third and final step to resolving the cascade. If the origin and the specificity are the same, then the declaration that appears later in the stylesheets takes precedence over a declaration that appears before it.

We can easily manipulate this by managing the stylesheet directly. If you create two selectors that are equal in specificity then whichever appears last wins.

a.rare {
  color: pink;
}
.list a {
  color: blue;
}

Pseudo styles

Pseudo-elements should also follow a certain structure because the source order of pseudo-elements affects the cascade. The correct order of pseudo-elements is, :link, :visited, :hover and :active. We need to follow these rules because later styles can override earlier styles. If the user hovers over a link, the hover takes precedence, but if the user clicks on the link then the active style takes precedence.

Just to recap some of the most important tips, don’t use IDs in your selector and don’t use !important. IDs can mess up the specificity of the whole stylesheets, and there is almost no need to override the important operator.

Here we have our codepen:

If you liked this article please visit my blog for more tech writings or click here for the original post. 🤘

JavaScript Sorting Algorithms: Quick Sort

Mehmed Duhovic — Sun, 28 Feb 2021 16:18:02 +0000

Similarly to merge sort, quick sort utilizes recursion in order to sort elements. Similarly to merge sort it is based on partitioning the array into smaller arrays. But the mechanism of sorting elements is different. Quick sorted introduces a new concept in sorting called the ‘pivot’.

Introduction to Quick Sort

Wow, quite a name, right? Quick sort. Based on the name itself it must be fast, right? Quick sort works by selecting any element (there are optimization techniques that can select the best option, but in our case, we will just take the first element) which will be called the pivot. 🚀 🚀

Then, we will move all the numbers smaller than that number to the left of that number, and all the numbers greater than that number to the right of that number. We are NOT sorting those numbers, we are only moving them. After each sorting session, there is one thing clear - the pivot is always in the right spot!

Visualization

The Inputs for this algorithm are: [12, 3, 44, 38, 5, 47, 15, 9]. 📊

Quick sort visualization using visualgo. Please visit https://visualgo.net/ for more visual algorithms.

First iteration, we selected the pivot. In our case the first number. Then the algorithm moves all the elements smaller than the pivot to the left of the pivot, and all the elements greater to the right. Elements moved to the left or right of the pivot are not sorted. Only the pivot is sorted after each iteration.

In the vizualization above 12 is the first pivot. After going through the whole array, 12 (yellow) is in the correct spot, and elements to the left of it (green) and right of it (purple) are still to be properly sorted. In our next iteration we select the left partition of the array, and we continue the process. Keep in mind that 12 is now at the correct spot, and is marked orange.

Selecting 12 as the pivot, everything else apart from the pivot is still to be sorted!

Sorting the left partition, the past pivot (12) is now in the correct spot.

Pivot Implementation

Now is not the time for sorting, that comes later!

We will instead first write a function that will be responsible for selecting the pivot and properly arranging the elements to either left or right of the pivot, while the correct order of the elements is still not that important. 'Pivoting' the array should not involve creating a new array. ✈️ ✈️

Pseudocode:

The method should accept three arguments: an array to 'pivot' on, the starting index and the ending index
For simplicity's sake, the pivot will be picked from the beginning of the array
The current pivot index will be stored in a variable
The algorithm will loop through the array1. If the pivot is greater than the current element, the pivot index is increased and the pivot index element is swapped with the current element
At the end the starting element is swapped with the pivot index
The algorithm returns the pivot index

function pivot(arr, start = 0, end = arr.length + 1) {
  let pivot = arr[start];
  let swapIndex = start;
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIndex++;
      swap(arr, i, swapIndex);
    }
  }

  swap(arr, start, swapIndex);
  return swapIndex;

  function swap(arr, firstIndex, secondIndex) {
    [arr[firstIndex], arr[secondIndex]] = [arr[secondIndex], arr[firstIndex]];
  }
}

The code above accepts three arguments, the array, the starting index (defaulting at 0), and the ending index (defaulting at the length of the array minus 1, or the last element). The pivot is the starting element, and the swapIndex starts at the beginning of the array. The algorithm then iterates, going through every element in the array, checking if the pivot is greater than the current element in the loop. If it is the swapIndex increases and the elements at those two indices are swapped. After the loop has finished we do one last swap - swapping the pivot element with the element at the swap index, thus setting the pivot at the appropriate place in the array.

Quick Sort Implementation

Again - quick sort is a recursive function. Please check the link to understand the concept more if you've never dealt with recursive code before!

Quick sort pseudocode:

The pivot method is called, saving the return value in a pivot Index variable
Quick sort is recursively called on the left and right sides of the array using the pivot index as the parameter.

function quickSort(arr, left = 0, right = arr.length - 1) {
  if(left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }

  return arr;
}

If the leftmost element is smaller than the rightmost (basically, if there is more than one element in the array) we do the following - call the pivot method, returning the pivot index, and then recursively call the quickSort on the left sub-portion of the array (from the start to the pivotIndex - 1) and the right sub-portion (from the pivotIndex + 1 to the end of the array). Recursion takes care of the rest :). 🎆 🎆

Big O Complexity

Quick sort uses recursion - so it isn't surprising that the best and average case are again all the same - O(nlog(n)). There are O(log(n)) decompositions, and O(n) comparisons inside each decomposition. But wait, there is the worst case complexity. What is going out there? There is a rare case in which the pivot is repeatedly the smallest element in the array. In that case we would need to decompose the array O(n) times, and make O(n) comparisons, thus making the algorithm O(n2).

Conclusion

Quick Sort is an effective algorithm due to its divide and conquer methodology. Compared to Merge Sort it is more effective when the data set is smaller (and vice versa - Merge Sort is more effective on a larger data set). Hope you learned something new today! If you liked this one please check the whole series or visit my blog for more tech articles. 🤘

JavaScript Sorting Algorithms: Merge Sort

Mehmed Duhovic — Tue, 16 Feb 2021 21:27:10 +0000

We are done with the basic sorting algorithms! Bubble Sort, Selection Sort and Insertion Sort were (I hope) easy to understand and wrap your head around. Implementing them will come naturally with time. Truth be told, those basic algorithms have their drawbacks - they do not scale well!
Doubling the size of the input will double the time to produce the sorted array!

Thus, we will move to some more advanced algorithms, whose sorting time will be O(nlog(n)). Without further ado let us introduce the first of those efficient Javascript Sorting algorithms - Merge Sort.

Introduction to Merge Sort

Merge Sort is quite different compared to the sorting algorithms we've seen. Merge sort divides the starting array into smaller arrays of 0 or 1 elements and then merges them back together. No need to loop through the array two times!

The whole process has two major steps:

Dividing the array
Merging the smaller arrays back together

Visualization

The Inputs for this algorithm are: [38, 1, 40, 34, 9, 41, 2, 16]. 📊

Merge sort visualization using visualgo. Please visit https://visualgo.net/ for more visual algorithms.

Seems like quite a lot of work right? But it is not, are just dividing the array (colored elements) and then merging the elements back together. Let us first understand the merging logic. At one point in the algorithm we had to merge the following subarrays - [[1, 38], [34, 40]]. Both of those are sorted - which is a requirement in order to produce a new sorted array that will contain all the elements found in those two subarrays.

Merge Implementation

This is the pseudocode for merge sort:

Create an empty array and create indices i and j
While there are still values that we haven't looked at1. If the value in the first array is smaller than the value in the second array, we will push that value onto our empty array, increase the value of i, and move on to the next value in the first array2. Otherwise, if the value in the second array is smaller than the value in the first array, we will push that value onto our empty array, increse the value of j, and move on to the next value in the second array
When all elements from one array are pushed to the sorted array, we will push all the remaining elements from the second array to the sorted array too

function merge(arr1, arr2) {
  let results = [];

  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }
  console.log(results);
  return results;
}

Let us go through the code to see what is happening here, taking inputs [[1, 38], [34, 40]] as an example. We have created our empty array and our two indices before running the loop. The loop checks for the values of our indices i and j and whether they are less than the lengths of the two arrays we want to merge. If the element at the index i of arr1 is smaller than the element of the index j of arr2 we push that element onto our results array.

Taking into account our exemplary array we compare values at indices 0 and 0, which are 1 and 34, so we push 1 to the results array and increase the value of i. The next iteration we compare indices at 1 and 0, which are now 38 and 34, and considering 34 is smaller than 38 we push 34 to the results array (which is now [1, 34]), and we increase the value of j. We keep repeating this until we have the finished array, which will be sorted in the end.

Merge Sort Implementation

Keep in mind: this solution uses recursion. Programmers who never worked with recursive code before might find recursion unintuitive, and it might be a good idea to check the link to understand the concept more.

Pseudocode for merge sort is as following:

The algorithm will continue halving the array until it produces arrays containing no elements or only one element
Once those arrays exist the algorithm will merge back those arrays (using the method above) until the 'merged' array has the same length as the starting array

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  } else {
    let mid = Math.floor(arr.length / 2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, right);
  }
}

The base says that as soon as the length of the array is one or zero, we return the array, otherwise, we crate the middle element, and then divide the array into two subarrays left, and right, in the end, we call merge on those two arrays.

Now we look back at the visualization.

Conveniently, we have 8 elements in our array. The algorithm first divides the array into 4, then into 2, and then into one element sub-arrays. At one point the elements are all different colors - it means that they are individual. The algorithm then starts merging the elements back together - 38 and 1 become [1, 38], 40 and 34 become [34, 40], and then these two arrays are combined-merged, and the algorithm runs until all the elements are sorted.

Big O Complexity

The best case, average case, and worst case of Merge sort are all the same - O(nlog(n)). Log(n) comes from the number of divisions the algorithm has to make. Having 8 elements means we would need to halve the array three times.

First time we would get two arrays with 4 elements each
Second time we would get four arrays with 2 elements each
Third time we would get eight arrays with one element each

If we would double the size of the input array, we would need to add one division to the algorithm! The n in the formula comes from the number of comparisons done when the arrays are merged back together.

Conclusion

And that is our fourth JavaScript Sorting Algorithm article, with Merge Sort! A tiny bit more comprehensive than the basic three, but still pretty easy to understand, right?! If you liked this one please check the whole series or visit my blog for more tech articles.

JavaScript Sorting Algorithms: Insertion Sort

Mehmed Duhovic — Tue, 09 Feb 2021 12:14:40 +0000

After talking a bit about Bubble Sort and Selection Sort we will mention yet another simple JavaScript Sorting Algorithm - Insertion Sort.
🔷🔷

Introduction

In our JavaScript Sorting Algorithms series we are explaining and implementing different sorting algorithms using JavaScript. The next Javascript sorting algorithm that we'll talk about is Insertion Sort.

Insertion Sort is considered an 'elementary' sorting algorithm, like the last two we wrote about (check the navigation), but compared to them it is actually somewhat useful and good to know outside the standard interview environment. The sorting algorithm divides the array into two portions. One portion is 'sorted', and the algorithm gradually fills out that portion with new values.

So, how we implement this algorithm? First, we will create a one-item chunk of the array we want to sort, and then we iterate from the next array in line - and we set each element to the place it belongs in the left portion.

💯 💯

Pseudocode

We will start by selecting the second element in the array
Afterward, we will compare that element to the element before it and act accordingly (swap if necessary)
We will go to the next element, and then we again check where it fits in the sorted left portion of the array
The algorithm repeats the logic until the array is sorted
Return the array

Visualization

For the visualization, let us use the same inputs as the last time for selection sort: [11, 17, 5, 28, 3, 6, 15].
📊

Insertion Sort Visualization

The first element in our array will fit into the sorted portion, characterized by the color orange. Then we select the next element in line (red) to compare it to the sorted portion. We see that 17 is larger than 11, so it stays in place, but the next element - 5 is smaller than both 11 and 17, and we will rearrange items so that 5 can fit in the correct place (green). And we do this for every element in the array.

Implementation

function insertionSort(arr) {
    for(var i = 1; i < arr.length; i++) {
        var currentVal = arr[i];
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j + 1] = arr[j];
        }

        arr[j + 1] = currentVal;
    }
    return arr;
}

console.log(insertionSort([11, 17, 5, 28, 3, 6, 15]));

As we already mentioned we start from the second element in the array (hence the var i = 1) and we iterate until the end. Inside every loop iteration, we redeclare the currentVal variable as the current value of the index i, and then we iterate backward from that element to the start of the array. For every iteration in which the currentVal is smaller than the value indexed by j we 'move' the element one place forwards until we find the correct spot for the current value!

Big O Complexity

As other elementary sorting algorithms Insertion Sort is also quadratic - O(n²), because as we increase the number of inputs elements we need to quadratically increase the runtime!

Let us mention some benefits to Insertion Sort. If the array is almost sorted we can just compare and move the elements which are out of place. Additionally, insertion sort can work dynamically, meaning that we can feed it new elements in real time - which is not possible by other algorithms.

Conclusion

We will conclude this part of JavaScript Sorting Algorithms with Insertion Sort here! If you liked this one please check the whole series or visit my blog for more tech articles.

What is the logarithmic runtime O(log(n))?

Mehmed Duhovic — Sun, 31 Jan 2021 12:18:27 +0000

Originally written on thedukh.

In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a given number x is the exponent to which another fixed number, the base b, must be raised, to produce that number x.
-Wikipedia

Introduction

If you want to see the original post and refresh your knowledge on Big O notation please click here.

In the last part, we clarified and deciphered the Big O notation, which tells us how fast and performant our code is. We've seen and explored some examples of different notations such as O(1), O(n), and O(n²).

There is another common variation of Big O runtime. Take a look at the image below, in red we see the logarithmic time complexity. Wait, logn. What? Well, if you (like me) lost math at the exact same point letters were introduced, do not despair! 😕 😕

It might be obscure at first, but this post will try to hopefully make it clearer and easier to understand.

So lets start!

Different Notations From The Last Post

The Logarithm

If we have any number b such that b > 0 and b ≠ 1, and we have x > 0 then we can say that the 'log base b of x' is ${y = log_bx}$ which is equivalent to ${b^y = x}$ .

And that's it! If you didn't catch it at first, logarithms and exponents are just inverse functions.
** $log_bx \iff b^y = x}$ . 📐 📐

B is the base, x is the argument, and y is the solutions to the equation.

In the case above ${y = log_bx}$ is called the logarithmic form and ${b^y = x}$ is the exponential form.

Log (the combination of letters) doesn't mean anything - it is just the name of the function that denotes the logarithmic operation. So if we see log anywhere in our mathematical problems, we will be sure that we are dealing with logarithms.

The parameter b being subscripted tells us the base of the operation, and x is the parameter.

We are just asking - what number do we need as the exponent to b in order to get x as the final result. An easy mnemonic method to remember in what correlation logarithms and exponents are (which I use often) is to imagine the b 'growing' and the x always 'running right from the equal sign' so that the equations fit. 🚀

Let us run through a couple of examples to walk one through on how we could solve issues like these.

What would be the result of ${y = log_416}$ ?

Getting the solution straight ahead might be hard. The best way to determine the solution would be to convert the formula into exponential form. Finding ${log_416}$ immediately might seem daunting but knowing that ${log_416}$ is the same as ${4^? = 16}$ suddenly seems a lot easier! What exponent are we looking for here so that 4 multiplied by itself gives 16? The solution is of course ${4^2 = 16}$ , so the solution of ${log_416}$ is 2.

What would be the result of ${y = log_6216}$ ?

Again we convert the logarithmic form into exponential. ${log_6216}$ is equal to ${6^? = 216}$ . What exponent do we need here? 6 multipled by itself is 36. So it is not 2, we need a bigger exponent! We should try it one more time - 36 * 6 = 216! We have found our exponent. It is three, so the solution of ${log_6216}$ is 3.

What would be the result of $\over 3}81 }$ ?

Now, this one is equal to $13?=81{\frac{1}{3}^? = 81}$ . Lets do the calculations $13−4=34=81\frac{1}{3}^{-4} = 3^4 = 81$ . So now we have that $log_{1 \over 3}81 = -4 }$ . 🤘 🤘

For more information about logarithms, you can check out this page. We touched on the subject enough to properly understand logarithmic time complexity, but you can take a look at the link above for more exercises, more properties of logarithms, and some special logarithmical types!

Logarithmic Time Complexity

The image below shows us how a logarithm scales:

A logarithm chart

Quite efficient! Even if we increase the size of the inputs, the value will start to converge at a certain point, so it is not a wonder that after the constant complexity, the logarithmic time complexity is the most efficient one!

Logarithmic time complexity most commonly occurs when a paradigm known as Divide and Conquer is involved. Divide and Conquer is a programming paradigm that breaks the issue into smaller subproblems. Each subproblem is small enough that it can be solvable, and finally, after the computations are done the subproblems are combined. Some of the standard algorithms that use Divide and Conquer are Binary Search, Quicksort, and Merge Sort.

The diagram below shows the merge sort algorithm, the array input is divided, first into two arrays, then into four, and it will keep on dividing itself until it becomes small enough that the individual items can be sorted. Afterward, the now separated chunks get combined together to get the final result - a sorted array.

Divide and Conquer merge sort diagram

Logarithmic Time Complexity Example

O(log(n))

Just to make something clear here. You probably noticed that we don't have a subscripted value when the logarithmic notation is involved. We just write O(logn).

In the examples above we had to write the base, because we solved different mathematical variations of logarithms. If there is no base specified then the base value by default is 2. So log100 would be equal to ${log_{10}100}$ .

Now let us look at an interesting problem.



function binarySearch(array, key) {
  var low = 0;
  var high = array.length - 1;
  var mid;
  var element;
  while (low <= high) {
    mid = Math.floor((low + high)/ 2)
    element = array[mid]
    if (element < key) {
      low = mid + 1;
    } else if (element > key) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1
}

binarySearch([1, 2, 4, 6, 7, 9, 13, 14, 15, 16, 18, 22, 25, 26], 9); // 5

BinarySearch method takes two arguments, an array, and some key that is supposed to be in the array.

We define initial variables. Low is by default zero pointing to the first element in the array, high will be the length of the array minus one (pointing to the last element in the array), and we also declare but not yet define mid and the element variables.
For as long as the low value is smaller or equal than the high value, we will run the while loop.
We find the middle index (by adding and dividing the current low and high values), and set the current element to the value found on that index inside the array. If the element is less than the key we're looking for, we redeclare the low value, if the element is bigger than the key, we redeclare the high value, and we go back to step 2.
Checking for the exact value of the element. If the element is neither bigger nor lower than the key value, then we've found our element!
If we went through the loop without returning the key value, then that value didn't even exist in the array in the first place! We return just -1.

The algorithm is visually represented below with the input provided in the code snippet.

Our search value is 9.

First our middle value is 13 and 9 is less than 13, so we ignore all the values larger than 13!

Our next middle value is 4, which is lower than 9 so we ignore all the values less or equal than 4.

Our next middle value is 7, which is again lower than 9 so we ignore all the values less or equal than 7.

Our final value is 9, and that is the number we are looking for!

This solution 'divides' the time required to get to the result by two. Or, in other words if we would double our input, we would only need one additional step in order to get to the solution.

Binary Search Example

Conclusion

We have shown that the logarithmic notation isn't that intimidating and that we can easily grasp the logic behind it with only a little bit of mathematics. An algorithm running this complexity is quite an efficient one, but sometimes often this complexity isn't applicable to the algorithm at hand. 🏆 🏆 🏆

If you want to check out more articles - click here

What is Big O and why is it important?

Mehmed Duhovic — Sun, 17 Jan 2021 00:06:41 +0000

Originally written on thedukh.

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
-Wikipedia

Introduction

Even if you’ll never use Big O in your professional career, it is still important to know what it is. And it can be valuable grasping the concept – knowing how to classify certain algorithms based on the changes in input size comes in handy during technical interviews, coding challenges or huge projects where performance matters greatly.

Usually when working on a problem, the developer follows a single principle whilst looking for an implementation of a certain algorithm among multiple versions. I NEED THIS TO WORK.

If the first solution works. Amazing. Let’s use that one.

If not, see what the hell is happening, change some stuff until it works, and pick up the second solution, or the third… or any that comes after that. Anything, as long as it works.

‘It works’ sometimes isn’t good enough

But what if we want to go a bit deeper, more into detail. What if we want to compare those multiple implementations (those that work) and to classify them based on different characteristics. What if we want to identify inefficiencies in our solutions, or discuss trade-offs between different variations. How do we even define ‘better’ when it comes to code? Do we consider better solutions faster ones, or those who use less resources, or those who are more readable?

Big O notation is a way to describe the relationship between the inputs of the algorithm and the time needed to implement that algorithm. In short, based on the size of the input, Big O notation tells us how fast the algorithm will run.

The definition

Big O notation describes the performance or the complexity of an algorithm. It does this by counting the number of operations inside the algorithm, based on the input. Still seems baffling, right? Well, look at the image below. If we have a certain input n, and if we increase the size of that input, the runtime of different algorithms will be different.

Different Notations

If you’re scratching your head even more than when you just started reading this article, look at the following example. Let’s solve this interview question.

Write a function sumTo(n) that calculates the sum of numbers 1 + 2 + ... + n.

What comes to mind first? The usual solution using the for loop. We will iterate through the numbers from 1 to n and then sum them up as they come along.

function sumTo(n) {
  let sum = 0;Using the for loop w
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

console.log(sumTo(5)) // 1 + 2 + 3 + 4 + 5 = 15

n (the input) is important here, because, as we increase n, JavaScript has to create one more operation due to the for loop (JavaScript needs to add another number to the sum).

So, if we sent 3 as the parameter, the for loop would run three times, and do the addition three times. If 5 was the parameter, the addition would be called 5 times, if 100 was the parameter it would be called 100 times, if 1000… you get the point.

This solution is dependent on the parameter n, and the number of operations grow as n grows. We can say that the runtime of this algorithm is directly correlated to the input – O(n).

Now take a look at another solution of the same problem:

function sumTo(n) {
  return n * (n + 1) / 2;
}

console.log(sumTo(5)); // 5 * (5 + 1) / 2 = 30 / 2 = 15

If you want to read about finite and infinite sums and why this formula works, please check this link, and you can read about the proof here. Basically, the formula n * (n + 1) / 2 will find the sum of all numbers between 1 and n. How many operations do we have here? Well, we have the multiply, then the addition and lastly the division, so no matter what number we input we will always have 3 operations (3 is a constant, it is considered insignificant so we can reduce it to 1). So, this algorithm runs at a constant speed. No matter what the input, the time to run this function will always remain the same – O(1).

Big O examples

O(1)

An algorithm is running at O(1) if the result is not dependent on an input variable or if inputs don’t affect how many operations need to be performed. O(1) usually outperforms all of the other notations. You saw one example up there, and here are a couple more:

function sumNumbers(n1, n2) {
  console.log(n1 + n2)
}

function printMultiple(n) {
  for (let i = 0; i < 10; i++) {
    console.log(i * n)
  }
}

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

The first function (sumNumbers) has two values as inputs (n1 and n2), and they are not affecting the number of operations (there is only one operation in the body of the function – addition), so the runtime isn’t dependent on the inputs. It always runs at a constant time – O(1).

The second function (printMultiple) seems interesting, we do have a foor loop, and we saw that a loop is correlated to a higher runtime. Well, not in this case because the loop only runs 10 times, so again, regardless of n only ten multiples will be printed (we could say that we have 10 operations, but we will see that we can simplify Big O expressions, so the final runtime will be again O(1)).

The third example is also running in a constant time. Why is accessing arrays always constant? Because of the way arrays are structured, elements of an array are located in a continuous memory sequence, so any item of the array is easily computed by using the formula – memory_address + item_size * index, only requiring one operation.

Arrays in memory visualized

O(n)

O(n) describes an algorithm whose performance grows linearly and in direct proportion to the size of the input. The time complexity increases as the size increases and they increase at the same rate. Some examples are below:

function loggingNumbers(n) {
  for (let i = 1; i <= n; i++) {
    console.log(n)
  }
}

function loggingNumbers2(n) {
  for (let i = 0; i < n; i++) {
    console.log(n)
  }

  for (let i = 0; i < n; i++) {
    console.log(n)
  }
}

The first loggingNumbers method takes an argument, and the for loop is dependent on that argument, meaning that it controlls how many iterations the loop will run. If we send 5, we will output numbers from 1 to 5, if we send 10 from 1 to 10, and so on, so the output is correlated to the input and it means that this method grows linearly – O(n).

The second loggingNumbers2 method is interesting, it has two for loops running one after another (they are not nested). So, one runs at n, another one also, so the final runtime is O(2n). Or is it? Again, we can simplify the expression, remove the constant, and we would only get O(n) as the runtime.

O( ${n^2}$ ).

function multiplicationTable(n) {
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= n; j++) {
      console.log(i * j);
    }
  }
}

What is happening here? The multiplicationTable method has two for loops, and each is iterating over n, meaning that in total we get n * n iterations. The runtime will be O( ${n^2}$ ). It’s worth to note here that the runtime of nested loops is equal to the amount of loops being nested, if we had three of them the runtime would be O( ${n^3}$ ). and so on. Additionally, check the visualization graph above to see the rate at which the curve appears if the runtime is quadratic or cubic, which means that as we increase the input, the runtime increases at an even faster rate, making the algorithm not very efficient.

Simplifying Big O expressions

As seen above inside loggingNumbers2 method we have removed the 2 from the solution.

Why?

Let’s us look at this mathematically. If n keeps increasing to infinity, the constant 2 isn’t changing the growth rate of the algorithm, the linear function is still growing linearly. This doesn’t mean that the constants are irrelevant or not meaningful. It just means that the Big O notation doesn’t care about constants because Big O only describes the growth rate in terms of mathematical functions, not their actual runtime.

The two biggest rules here are that constants don’t matter (O(2n) becomes O(n), and O(10) becomes O(10 * 1)) and that smaller terms don’t matter (O(n ~~+ 10~~) becomes O(n), keep in mind, the 10 isn’t affecting the growth rate by much, if we keep increasing the n to infinity).

Conclusion

We’ve defined the Big O notation, shown some of the most common examples and explained why and how we simplify . In the next part we’ll go through the logarithmic runtime, which is more efficient than linear (O(n)) but less efficient than constant (O(1)).

JavaScript Sorting Algorithms: Selection Sort

Mehmed Duhovic — Sat, 02 Jan 2021 22:27:21 +0000

I've finished the uni - there is no way in hell I would still need data structures and algorithms, right? (that's what I thought, I forgot almost everything to make more room in my brain for football trivia and stupid memes :)) Until I quite embarrassed myself on one interview, and because of that I spent quite some time re-learning this stuff, which landed me a better job than the one I had. (YEAAH!) Again, check my blog if you wish! This is second part in our (cue the SSSR music) JavaScript Algorithm Series.

Introduction

After finishing Bubble Sort we are moving onto the next Javascript sorting algorithm – Selection Sort.

Selection Sort is somewhat similar to Bubble Sort, but instead of first sorting higher values by placing them into correct positions, we first place smaller values into the correct positions. We still iterate through the whole array in (mostly) the same way.

The question is HOW? We need to store the currently smallest value in some kind of a container variable. Then that value can be redeclared depending on the value of other elements (if some element is smaller than the already smallest element in the array).

Pseudocode

Store the first element in the array inside the 'smallest container variable'
The algorithm will iterate through the array comparing the current element and the current smallest variable on each iteration
The algorithm will update the value of the smallest variable if the current element is smaller than the smallest container variable
If not the algorithm just continues until it reaches the end of the array
The algorithm will then swap the current element and the smallest variable
The algorithm will repeat the process going from step 1. to 5.

Visualization

Let us visualize this algorithm using the inputs [11, 17, 5, 28, 3, 6, 15]. Vizualization has been done using this amazing free tool called visualgo.

Initially, the smallest value is assigned to the first value in the array (red element). Then the algorithm iterates through elements and compares the smallest value and the current element (green), and if it finds a smaller value it redeclares that value. At the end of each iteration the algorithm swaps the current smallest element with the first element in the iteration, and thus the currently smallest element is sorted in the appropriate place (changing color to orange).

Implementation

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let smallest = i;
    let j = i + 1;
    for (; j < arr.length; j++) {
      if (arr[j] < arr[smallest]) {
        smallest = j;
      }
    }
    if (i !== smallest) {
      [arr[smallest], arr[i]] = [arr[i], arr[smallest]];
    }
  }
  return arr;
}

selectionSort([11, 17, 5, 28, 3, 6, 15]);

At the start of each outer iteration we set the smallest value to the first value in the array. In the same block (because we use ES6 let declaration) we declare the value j to be i + 1. Then we just go through every element in the array. if we find a smaller value than the current smallest value, then we redeclare the smallest index to be j. In the end of each iteration we just swap the values if there is a smaller value AND it is not equal to the value we started with using - [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] - thanks ES6.

Big O Complexity

Similar to bubble sort, the average Big O of selection sort is O(n2) because (again) we compare every element to every other element in the array. If the number of elements grow, the runtime will grow exponentially. Selection sort might be more useful than bubble sort when we want to use an algorithm that reduces swapping, because the algorithm only swaps once - at the end of every loop.

Conclusion

That's it! The next one we'll talk about is Insertion Sort, so please stay tuned, and happy coding :).

JavaScript Sorting Algorithms: Bubble Sort

Mehmed Duhovic — Sun, 27 Dec 2020 21:34:16 +0000

You can read more posts on programming and tech on my blog. This series will be updated as soon as I catch some free time :)

Introduction

So I have this thing on my blog called the JavaScript Sorting Algorithm series. This series of posts will try to explain and implement different sorting algorithms in our favorite scripting language - JS of course! And we will start our journey with the easiest one - bubble sort.

Although the bubble sort algorithm compared to other sorting algorithms isn't that efficient, and isn't used anywhere in the real world, interviewers still commonly check for it during interviews. It is good to at least know how it works under the hood.

How does bubble sort (you can also find it under the alternate name sinking sort) work. The algorithm 'bubbles' large values (thus the name) to the top on each iteration of the algorithm. Then it compares adjacent elements between each other and swaps them if they are in the wrong order.

Pseudo code looks like this:

The algorithm will compare two adjacent elements. For example a and b.
The algorithm will swap them if they are out of order by checking whether a is less than b
The algorithm will repeat steps 1. and 2. until the end of the array is reached. At the end of iteration the largest number should be at the very end of the array.
The algorithm will then ignore the last item and repeat step 1, until all the elements are sorted

Let us visualize this algorithm using the inputs [15, 6, 4, 18, 7, 13, 1].
The algorithm is vizualized using visualgo.

So, at first we compare every element with its adjacent elements (green elements). If the element is larger - it will be swapped, during each iteration the largest element will be stuck to the end (orange elements). This process repeats itself until all the elements are sorted.

Implementation

function bubbleSort(arr) {
    for(let i = arr.length; i > 0; i--) {
        for(let j = 0; j < i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }

    return arr;
}

bubbleSort([15, 6, 4, 18, 7, 13, 1]);

Every iteration we reduce the iterator by 1 (because the last element is already sorted!). if the element is bigger than its adjacent element, we will use the swapping mechanism [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] (a pretty cool ES6 concept to swap items in place without the need for a temporary variable).

Optimize it!

There is one specific scenario in which we can optimize the algorithm a bit.

If the array is almost sorted – needing to rearrange only an item or two, the algorithm still goes through all the loops, even though nothing is happening.

In order to fix this – we just need to check whether we made any swaps.

function bubbleSort(arr) {
  let swapHappened;
  for (let i = arr.length; i > 0; i--) {
    swapHappened = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapHappened = false;
      }
    }
    if (swapHappened) {
      break;
    }
  }
  return arr;
}
bubbleSort([2, 4, 6, 5, 7, 9, 12]);

Big O Complexity

The average Big O of bubble sort is O(n2) because we iterate twice through the whole array. We need to compare current element to every other element in the array.

Conclusion

That's it! Bubble sort isn't a very demanding algorithm to learn. We will post more sorting algorithms in the future. In the meantime, please check my blog for more tech articles.