DEV Community: Guilherme_Konan

Why we use "key" in React?

Guilherme_Konan — Tue, 13 Jul 2021 21:06:53 +0000

Ever wondered why React keeps bugging you about using the key attribute? Why we need to use this if everything is working perfectly? The answer is rather simple, Performance!

Every time you make a change in a React app your application re-renders entirely right? Actually no! And that's what we are going to understand now!

The problem

Every time our application renders React create a new tree of react elements. The problem here is updating the UI to match the most recent tree created in render. This problem can be solved in a non efficient way, ending with a a complexity in the order of O(n^3) where n is the number of nodes (elements) in the tree.

React came with a really clever way of handling this, by implementing an algorithm based on two simple assumptions they managed to make this problem go from O(n^3) to O(n).

The two assumptions they made can handle most cases, and they are:

If one element changed it's type a new tree will be created.
If two elements have the same key id in both trees, they are the same element and will not be re-rendered from 0.

Reconciliation algorithm

The algorithm have some different ways to work depending on the root elements. If the root element changed from one type to another (or one tag to another) the new tree will be created from scratch.

A good way to visualize is checking out this example I got from react docs:

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

Here the Counter will not be reused, the Counter will be remounted.

Another case React handles pretty well is when we have DOM elements of the same type. React can update only attributes and have the structure be reused, Check the examples above:

<!-- before -->
<img src="images/image.svg" className="something" />

<!-- after -->
<img src="images/image.svg" className="another-something" />

The tag remains the same and react only updates the className.

Another case is with styles:

<!-- before -->
<div style={{color: "green", padding: "10px"}}></div>

<!-- after -->
<div style={{color: "orange", padding: "10px"}}></div>

React only changes the color style, and not padding.

Okay really interesting, but why key?

React differs if a node changed or not using the node type itself or the attributes passed to it. But there's a problematic case that is not resolved by only looking at the node or it's attributes. Lists.

Lists will have the same node types and attributes, so they won't be recognized by the algorithm.

But we can have cases where the algorithm will work fine, like this:

<!-- tree1 -->
<ul>
    <li>1</li>  
    <li>2</li>
</ul>

<!-- tree2 -->
<ul>
    <li>1</li>  
    <li>2</li>
    <li>3</li>
</ul>

Here we have two lists, React will match the first two elements (1, 2) and will insert the last one (3) at the end.

But if we have a similar but different implementation.

<!-- tree1 -->
<ul>
    <li>2</li>  
    <li>3</li>
</ul>

<!-- tree2 -->
<ul>
    <li>1</li>  
    <li>2</li>
    <li>3</li>
</ul>

Here we are inserting something new at the start of the list. React doesn't know how to handle this and will recreate every element, instead of reusing 2 and 3 that remained the same between trees, leading to bad performance.

That's where keys are important. Using keys we can have every item in a list have a unique identifier (ID) so React can easily detect who needs to be changed or not, re-rendering only the ones with changes.

Conclusion

That's my takeaway and what I have understood searching about this underlying implementations react has.
I started searching for curiosity + to have a better understanding of react's big picture. I may write more about how react works underneath the hood in the future, if you have any suggestion please comment down here :) Thanks for reading.

The compiling process

Guilherme_Konan — Mon, 28 Jun 2021 12:34:49 +0000

The compiling process

Hello guys, a while back I made some notes about the compiling process. When I finished I thought that I could make some small edits and transform it into a post. So here we are.

The compiling process (turn source code in machine code) is divided in 4 smaller steps:

preprocessing
compiling
assembling
linking

To be sure you will understand everything I will first explain some terms I will be using when describing the compiling process:

prototype: Is a function declaration that comes in the start of our programs, so the compiler can understand that there will be a function with this name. We usually declare our functions at the top of our code and write what they to at the end of it.

Example of a prototype:

/*here we only declare name, type and parameters of our function,
we don't say what the function does (aka we don't specify the
function body), that's why it's a prototype.*/
int area( int length, int breadth );

Library: Is a compiled binary file (or a collection of binary files) which can be linked (will explain what is linked below in the compiling steps).

header file: Is the name of what we include when we start our code (aka #include<stdio.h>), header files are files that contain prototypes for all the functions from the libraries we include in our code.

Okay Now let's go for the 4 compiling steps.

Preprocessing

Preprocessing is when the compiler look at the header files we included in our program and replace the "include" lines for the actual prototypes that are inside of these files.

for example:

#include <stdio.h>

int main(void)
{
    printf("hello, world\n");
}

will be preprocessed into:

//prototypes from printf function
...
int printf(string format, ...);
...

int main(void)
{
    printf("hello, world\n");
}

Compiling

Compiling takes our source code in C, and converts to assembly code.

Assembling

Assembling is the process of converting the assembly code that we have after the last step, Compiling, and actually convert it (or assemble it) to binary code (or machine code). Most modern compilers don't have this phase because they jump the assembly code and convert directly your source code to binary, they probably will only convert to assembly first if you ask to. But with old compilers the case will often be that they will convert your code do assembly first and then to binary.

Extra: When a compiler makes the binary code for you and it still haven't being linked, he actually have produced for you an Object file. Here is an good explanation of what it is (link for this explanation in the end).

Object code is a portion of machine code not yet linked into a
complete program. It's the machine code for one particular library
or module that will make up the completed product. It may also
contain placeholders or offsets not found in the machine code of a
completed program. The linker will use these placeholders and
offsets to connect everything together.

Linking

Now that we have our program file in binary we need to link it to the binary of the libraries we are using so in the end we have only one binary file with all of it inside, that process is called linking.

Additional: stdio is a part of the standard library, and the linker in the linking process already know where this library is, that's why we doesn't have to specify where the binary file of the library is when using stdio and some other standard functions (we still need to specify the header files).
But when we are using a library that is not standard (for example a library you created) we need to specify it with the linker using a flag when compiling our program. This flag is -l, and we use it without the lib prefix to link with the library file. Ex: -lExampleLibrary. If your library file is not where -l looks by default you have to specify where is it using -L.
Example:

if the library code is inside the current folder you are:
gcc test.c -L. -lExampleLibrary -o test

Just to have the notes a little more specific I'm gonna explain some more deep details about the linking process.

library file: When the linker go get the binaries of the libraries we are using he doesn't actually get .o files (aka normal binary files), he get's what we call a library file, that can be a static ".a" or a dynamic ".so" one.

A static Library combines all the object code (aka binary code that doesn't have been linked) into a single archive with a ".a" file extension, that's what our linker actually goes get to link with your source code.

A dynamic Library have their object codes linked together forming a single piece of object code that is loaded into memory and only the address in memory of where the library function (being used in source code) is, is added to the executable file (after linked).

Customizing Git Bash in Windows

Guilherme_Konan — Fri, 21 May 2021 16:07:23 +0000

Hello guys, this is gonna be a small post about git bash customization, so by the end of it you will know how to change some aspects of your git terminal, for example making it like mine:

so let's dive in!

Finding and Editing git-prompt

Open your git bash terminal and type this commands:

cd /etc/profile.d/
explorer .

The first command is to change your current directory to the /etc/profile.d/ that is where the file we need to edit is. The other command just open the explorer in the current directory, so you will se something like this:

Here is our git-prompt.sh. Now we can open it and see what we have there.

if test -f /etc/profile.d/git-sdk.sh
then
    TITLEPREFIX=SDK-${MSYSTEM#MINGW}
else
    TITLEPREFIX=$MSYSTEM
fi

if test -f ~/.config/git/git-prompt.sh
then
    . ~/.config/git/git-prompt.sh
else
    PS1='\[\033]0;$TITLEPREFIX:$PWD\007\]' # set window title
    PS1="$PS1"'\n'                 # new line
    PS1="$PS1"'\[\033[32m\]'       # change to green
    PS1="$PS1"'\u@\h '             # user@host<space>
    PS1="$PS1"'\[\033[35m\]'       # change to purple
    PS1="$PS1"'$MSYSTEM '          # show MSYSTEM
    PS1="$PS1"'\[\033[33m\]'       # change to brownish yellow
    PS1="$PS1"'\w'                 # current working directory
    if test -z "$WINELOADERNOEXEC"
    then
        GIT_EXEC_PATH="$(git --exec-path 2>/dev/null)"
        COMPLETION_PATH="${GIT_EXEC_PATH%/libexec/git-core}"
        COMPLETION_PATH="${COMPLETION_PATH%/lib/git-core}"
        COMPLETION_PATH="$COMPLETION_PATH/share/git/completion"
        if test -f "$COMPLETION_PATH/git-prompt.sh"
        then
            . "$COMPLETION_PATH/git-completion.bash"
            . "$COMPLETION_PATH/git-prompt.sh"
            PS1="$PS1"'\[\033[36m\]'  # change color to cyan
            PS1="$PS1"'`__git_ps1`'   # bash function
        fi
    fi
    PS1="$PS1"'\[\033[0m\]'        # change color
    PS1="$PS1"'\n'                 # new line
    PS1="$PS1"'$ '                 # prompt: always $
fi

MSYS2_PS1="$PS1"               # for detection by MSYS2 SDK's bash.basrc

Here we have a lot of different things, but let's focus on the important part, this one:

    PS1='\[\033]0;$TITLEPREFIX:$PWD\007\]' # set window title
    PS1="$PS1"'\n'                 # new line
    PS1="$PS1"'\[\033[32m\]'       # change to green
    PS1="$PS1"'\u@\h '             # user@host<space>
    PS1="$PS1"'\[\033[35m\]'       # change to purple
    PS1="$PS1"'$MSYSTEM '          # show MSYSTEM
    PS1="$PS1"'\[\033[33m\]'       # change to brownish yellow
    PS1="$PS1"'\w'                 # current working directory

Here is where we are gonna customize it. The nice thing about git bash, is that there are already some pretty comments that help us understand what each thing does.

To customize it we are gonna need to understand two things: The special backslash characters and the ANSI color escape codes.

The first one is pretty simple, there are some of them and they each represent something that can be seeing in our terminal, here are some of them:

\u => username

\h => hostname until the first '.'

\w => current working directory

So for example the line PS1="$PS1"'\u@\h' Would be username@hostname.

The last thing is the color codes. Those are used before the line we want to color it, so:

PS1="$PS1"'\[\033[32m\]'       # change to green
PS1="$PS1"'\u@\h '             # user@host<space>

Here we are changing the username@hostname to green. There are a few color codes we can use in bash such as:

Black        30  
Red          31     
Green        32     
Brown/Orange 33     
Blue         34     
Purple       35     
Cyan         36
Light Gray   37

There are some special codes that change the style of the text too:

Normal        0
Bold text     1
Faint text    2
Italic        3
Underlined    4

So we can make some pretty cool customization combining those together, here is an example:

PS1="$PS1"'\[\033[1;36m\]'       # change to bold 1() and cyan (36)

There are some other lines that you can customize. Basically every line that is changing PS1 represents a customization for some part, and all of them have good comments to guide you. I only focused in the first ones to be easier to understand, since you are focusing in only a couple lines, instead of the entire file. But if you prefer that I point out them, they are these lines here:

This one changes the part that indicates in which branch you are

PS1="$PS1"'\[\033[1;33m\]'  # change color to bold yellow
PS1="$PS1"'`__git_ps1`'   # bash function

And this ones defines the second line, where you write the commands (in case is only the "$")

PS1="$PS1"'\[\033[1;31m\]'     # change color to bold red
PS1="$PS1"'\n'                 # new line
PS1="$PS1"'$ '                 # prompt: always $

And that's it, with this knowledge you can make some more customizations in your git bash :). If you liked how mine feel free to get the code for you here:

if test -f /etc/profile.d/git-sdk.sh
then
    TITLEPREFIX=SDK-${MSYSTEM#MINGW}
else
    TITLEPREFIX=$MSYSTEM
fi

if test -f ~/.config/git/git-prompt.sh
then
    . ~/.config/git/git-prompt.sh
else
    PS1='\[\033]0;Terminal Dir:$PWD\007\]' # set window title
    PS1="$PS1"'\n'                 # new line
    PS1="$PS1"'\[\033[1;35m\]'       # change to bold purple
    PS1="$PS1"'GMkonan '             # user@host<space>
    PS1="$PS1"'\[\033[1;32m\]'       # change to bold green
    PS1="$PS1"'in '          # show MSYSTEM
    PS1="$PS1"'\[\033[1;36m\]'       # change to bold cyan
    PS1="$PS1"'\W'                 # directory without the path
    if test -z "$WINELOADERNOEXEC"
    then
        GIT_EXEC_PATH="$(git --exec-path 2>/dev/null)"
        COMPLETION_PATH="${GIT_EXEC_PATH%/libexec/git-core}"
        COMPLETION_PATH="${COMPLETION_PATH%/lib/git-core}"
        COMPLETION_PATH="$COMPLETION_PATH/share/git/completion"
        if test -f "$COMPLETION_PATH/git-prompt.sh"
        then
            . "$COMPLETION_PATH/git-completion.bash"
            . "$COMPLETION_PATH/git-prompt.sh"
            PS1="$PS1"'\[\033[1;33m\]'  # change color to bold yellow
            PS1="$PS1"'`__git_ps1`'   # bash function
        fi
    fi
    PS1="$PS1"'\[\033[1;31m\]'        # change color to bold red
    PS1="$PS1"'\n'                 # new line
    PS1="$PS1"'$ '                 # prompt: always $
fi

MSYS2_PS1="$PS1"               # for detection by MSYS2 SDK's bash.basrc

# Evaluate all user-specific Bash completion scripts (if any)
if test -z "$WINELOADERNOEXEC"
then
    for c in "$HOME"/bash_completion.d/*.bash
    do
        # Handle absence of any scripts (or the folder) gracefully
        test ! -f "$c" ||
        . "$c"
    done
fi

MSYS2_PS1="$PS1"               # for detection by MSYS2 SDK's bash.basrc

Useful Links

customize git bash

Minha experiência no NLW #4

Guilherme_Konan — Fri, 26 Feb 2021 20:05:57 +0000

Eae galera beleza? Esse é meu primeiro post em português, eu ainda pretendo continuar escrevendo a maioria dos meus artigos em inglês, porem esse aqui não podia ser o caso e eu acho que você sabe porque. Hoje pela primeira vez eu participei de uma NLW (Next level week) um evento feito pela RocketSeat que dura uma semana. Nessa quarta edição o evento foi dividido em trilhas de React, NodeJS e Elixir. Nesse post eu vou contar um pouquinho sobre a minha experiência nesse evento e como eu resolvi aproveitar ele!

Trilhas

Eu fiz duas trilhas nessa NLW, a de Node e a de React. No site da Rocket é recomendado que você escolha apenas uma trilha, mas eu vou dar a minha opinião. Eu escolhi fazer duas trilhas por alguns motivos:

1 - Eu tenho o tempo para isso

Se você trabalha 8 horas por dia eu acho que é melhor ficar com só uma trilha, porem eu dediquei essa semana toda apenas para estudar.

2 - Já possuo conhecimentos em React

Eu não sou nenhum especialista em React, mas já usei ele em alguns projetos, inclusive usando especificamente o NextJS como foi usado na NLW (como meu portfolio e meu blog) então acompanhar as aulas de react foi bem mais tranquilo do que as aulas de Node no qual eu tinha o conhecimento bem limitado.

Talvez você tenha pensado nisso...

"Porque Você fez um curso de React que você já conhece ao invés de algo novo como o Elixir?" ou "Vale a pena fazer a NLW em uma trilha de uma tecnologia que eu já uso:?". Então, para a primeira pergunta a resposta esta em um ponto que foi dito na própria NLW. É melhor você ficar bom em algo especifico do que saber um pouquinho de cada coisa então parar em nenhum conhecimento solido. Tenha foco.

Para a segunda pergunta, minha resposta é sim, você tem a chance de aprender coisas novas sobre essa tecnologia, que mesmo que fossem simples você n sabia. Para mim essas foram o uso de contextos do react, criação de notificações, uso do typescript, uso dos modules no css e por ai vai. Mas o melhor de tudo é que mesmo que você saiba de absolutamente TUDO que tenha sido passado em todas as aulas, no final você ainda vai ter um projeto com uma ideia muito boa (tanto o projeto de node quanto o de react para mim foram muito bem pensados e não clichês como algum tipo de todo app) Além disso você vai ter a oportunidade de criar um network muito grande com os devs que estão fazendo o NLW também (só de eu postar minha apresentação no servidor deles mais de 30 pessoas me adicionaram no linkedin, além das conversas e conexões em outras redes que eu não vou comentar). Então eu acho que no final sempre vai valer a pena.

Recomendações

Agora algo que eu posso recomendar para quem tem vontade de fazer a NLW (obviamente são apenas opiniões minhas)

Recomendações gerais

1 - Tenha o tempo para estudar focado e entender bem o conteúdo

2 - pratique o conteúdo de alguma forma

3 - Vá no servidor, se apresente, pergunte, responda por mais tímido que seja (como eu)

4 - Anote, escreva, desenhe ou qualquer coisa que te ajude a absorver melhor o conteúdo

Perfil de quem pode fazer mais de uma trilha

1 - Tenha bastante tempo no dia

2 - Tenha muito foco

3 - Conheça alguma das tecnologias previamente

Como eu estudei?

Vi muitas pessoas que no meio da semana já tinham feito muitas modificações no projeto original (principalmente no React) e, apesar de estar me segurando para fazer isso, eu preferi não fazer nenhuma modificação até o final da semana. Eu acho que se eu mudasse o projeto demais eu poderia acabar me perdendo nas aulas subsequentes, mesmo que fosse por não usar alguma boa pratica de escrita. Minha forma foi ter 2 projetos, o da aula e outro que estivesse usando as mesmas tecnologias, para eu reforçar o conteúdo e quebrar a cabeça no segundo deixando o que era feito em aula para eu mexer apenas quando já tivesse concluído a semana (diga-se de passagem já comecei a alterar ele agora :) ).

Eu tenho muita experiência que eu ainda poderia dizer sobre essa semana, mas eu acho que esse artigo esta ficando grande demais já então vou conclui-lo por aqui. Muito obrigado a toda a equipe da RocketSeat, a qualidade e o carinho que foi posto no conteúdo é algo que nunca teria passado pela minha cabeça. Um obrigado especial ao Filipe Deschamps também por falar bem da Rocket fazendo eu ter vontade de verificar por mim mesmo. Estou muito ansioso pelos próximos eventos, para continuar sempre indo ao próximo nivel.

Implementing Binary Search in Java

Guilherme_Konan — Mon, 25 Jan 2021 20:40:23 +0000

If you saw my article about Selection Sort it means that you already know at least one sorting algorithm. Now that you have a sorted list (or can create one) we are gonna dive in an algorithm that can search for an element in this sorted list, that's gonna be the Binary Search algorithm. We are gonna talk about two approach's to this algorithm, iterative and recursive and about it's time complexity too.

Like I did in all my A&DS Implementation articles with java until now we are gonna create two files.

Iterative Search

Let's start creating the BinarySearch.java file.

This file is gonna hold both our Iterative and recursive search methods. But first we will make the iterative one, iterativeSearch

    void iterativeSearch(int[] arr, int key) {


        //just a placeholder
        int index = 0;

        //defines the first one in the array
        int first = 0;
        //defines last one in the array
        int last = arr.length - 1;
        //defines the mid point of this array
        int mid = (first + last)/2;
    }

The first thing we do is create two parameters for our method, the array and the key (or value) we want to search inside this array, the we create the variables we are gonna be using, the index is gonna be the variable that stores the position of the value we are searching (the index of the key). The first variable is the index for the first value in the array (which is 0 because every array starts at 0). The last is the index of the last value in the array which we can get by subtracting one from the size of our array. And finally the mid variable that stores the mid point of our array.

IMPORTANT: Why we get the mid point of the array by using the sum of the first with the last divided by two instead of just getting the last/2 ? We need to make a sum with the first because when we start iterating, the first position of the array is gonna start to change, incrementing every time the loop is completed, making the mid point of the array change too.

Now that we have our variables all set we are going to create the logic to search for the key

    //while the array is not the size of zero
    while(first <= last) {
        if (arr[mid] < key) {
            //shifts to the right since is greater and we already checked mid
            first = mid + 1;
        }
        //if item in mid make it equal index, break the loop and return at the end
        else if (arr[mid] == key) {
            //define index as mid
            index = mid;
            //print result
            System.out.println("The position of " + key + " is " + index);
            //break from the while loop
            break;
        }
        else {
            //shifts the end point to the left of mid
            //since the value is smaller and we already checked the mid
            last = mid - 1;
        }
        // make new count now with the new value to first or last
        mid = (first + last)/2;
    }

Okay, here we have a basic while loop that iterates until the variable first(that stores the start of the array) is bigger than the last which means that we are gonna iterate until the end of the list. Inside the loop we start creating our conditions to find our element. The way binary search is by dividing the list by half until it finds the number (that's why we make the mid variable) and here is where our conditions play. in the first if statement we make so if the number in the mid is smaller than the key (element we are searching) we will update the variable first to be the position after the mid position, which means we are gonna now search only the right half of the list, because everything to the left is smaller than our key so the key is not gonna be there.

Example images (taken from tutorialPoint)

In this example 31 is the key

After we defined our key we define the mid point of the list (in this case 27)

Then we enter in our loop and met our first condition, comparing if mid value is lower than key

The condition is met so we define first to be the element left to mid (in this case the 31 itself, or position 5) and we repeat the loop

The next condition is if the mid point value is equal to key, if it is the element was found and we can break the loop, here we use the index variable just to get more understandable in print.

Last but not least we make our final condition that is really similar to our first condition, in this case (although not explicitly told in the statement ) checks if the mid value is greater than the key, if it is we are gonna search only the left half of the list, by defining last as the value before the mid point.

The last thing we have in our while loop that is executed in every loop is the mid = (first + last)/2; , This is necessary because every time the loop is executed we make new comparisons with mid and update what we are searching in the list, and if we update the first variable and last variable but don't update our mid variable we will continue with the same mid point every time so the loop is going to make the same comparisons every time.

if (first > last) {
            System.out.println("Not found");
        }
    }

The last thing in out iterativeSearch method is just a simple condition to make sure that, if the loop ends and the key wasn't found, the key is not in the list so we print "not found".

Okay now that we created our method lets create our BinarySearchMain.java to run it!

public class BinarySearchMain {
    public static void main(String args[]) {
        BinarySearch binary = new BinarySearch();
        int[] arr = {10, 6, 4, 8, 2};
        int key = 8;

        binary.iterativeSearch(arr,key);
    }
}

Here we just make a main method and call our iterativeSearch passing the array and key we defined,now everything is working! Just try to run it and play around with different arrays.

In the above case the output should be this

The position of 8 is 3

Time Complexity

The time complexity of iterative search is O(log n) because in the worst case scenario (if the number we are looking for is at the end of the list or is not in the list) we will have to divide the list in half repeatedly until we get to the end of the list. The best case scenario would be O(1) ( or Ω(1) ) and it would be if the element we are looking for is already in the mid point of the array.

Recursive Search

Since we already covered the iterative approach I'm gonna be more to the point in the recursive one

    int recursiveSearch(int[] arr, int key, int first, int last) {

        //just a placeholder
        int index = 0;

        int mid = (first + last)/2;

        //base case
        if (first > last) {
            return -1;
        }

        if(arr[mid] < key) {
            //return recursive but with first being shifted right from              
            //mid getting only the right half of the array 
            return recursiveSearch(arr,key,mid + 1, last);
        }
        else if (arr[mid] == key) {
            //recursive is gonna end up here at the end
            index = mid;
            //return the value
            return index;
        }
        else {
            //return recursive but with last being shifted left from mid
            //getting only the left half of the array
            return recursiveSearch(arr,key,first, mid - 1);
        }
    }

The recursive search is pretty simple, we start by making our recursiveSearch method . The difference is that this time instead of making it a void we make it as an int, so we can use the returns to make our recursion. The other difference in the method is that we add more two parameters: the int first and the int last.

Inside the method we have a base case that comes at the top of the code that if our first is higher than the last our element is not in this list. After that we have our set of conditions similar to what we have done in the iterative search. But inside this if statements we have our return statements. Here is where we are gonna use the power of recursion, we call the same recursiveSearch again in our first if statement and pass the same array,key and last. But we pass our first as mid + 1 making it shift the start of the array to only the right half of the array.

In our next if we do basically the same thing to check if our key is in mid.

Our last check in else is where we use the same concept of our first if but we shift the last to the left half of the array.

And we are done with the recursive search, now we only need to add to main to run it.

        int first = 0;
        int last = arr.length - 1;


        int recursive = binary.recursiveSearch(arr, key, first, last);

        if(recursive == -1) {
            System.out.println("Not found");
        }
        else {
            System.out.println("Found at position " + recursive);
        }

if it returns -1 as we defined in our base case, we print "Not found". else, we found the position so we just print it!

and this is the output (used the same test I used to iterative search)

Found at position 3

Time complexity

Maybe you realized something peculiar about it but... The time complexity of recursive search is the same O(log n) of our iterative search! In the worst case scenario we are still dividing the list by half multiple times. And the best case scenario is still O(1) or ( Ω(1) )

So, you may be asking yourself "What is the difference?" Honestly the only difference is in Space complexity but that is some content for another whole article. So in the end is a matter of choice, which one you find easier to understand? Go and use it!

If you want to see the full code you can see it here in this github repo

This is a post I have started writing in the end of 2020 but I got back to it only in 2021. Because of that I felt like it wasn't good enough and wasn't sure if I should post it or not. I decided to post because if it really bad, the worst thing it can happen is not be useful for someone, if it's not that bad it can still help someone. But just letting stay inside my computer for no reason just doesn't even have a chance to help someone.

If you have any suggestions or critics about what I should write or/and how I should write (more detailed? less detailed?) or even how is my grammar (not a native English speaker) feel free to put it in the comments, It would help me a lot!

Implementing Selection Sort in Java

Guilherme_Konan — Fri, 11 Dec 2020 09:43:58 +0000

Selection Sort is a simple sorting algorithm. In this article we are gonna implement it using java to sort an array from smallest to largest element. We are gonna talk about it's time complexity too. Let's dive into it!

Let's start by creating our first java file SelectionSort.java

In this file we are going to create a method called sort that returns an array of ints.

int[] sort(int[] arr) {
    int index;
    //looping the unsorted list
    for (int first = 0; first < arr.length; first++) {

    }
}

Here we start by creating a integer variable called index (that we are going to use later) and a loop that iterates through all the array. Then we are going to make index have the same value as first, make another loop and implement our condition... Yeah that's a lot! Allow me to explain.

int[] sort(int[] arr) {
    int index;
    //looping the unsorted list
    for (int first = 0; first < arr.length; first++) {

        //index starts at first but changes in every loop
        index = first;  

        //then every loop the index is compared with all numbers
        //except the one we are comparing to (the index)
        for (int i = first + 1; i < arr.length; i++) {
            //check if value is lower
            if (arr[i] < arr[index]) {
                //if it is, change index to it
                index = i;
            }
        }
    }
}

Let's start explaining this second loop we made. This loop is inside the first loop, so every time we iterate the first loop once, we get a value of the list and go through all the elements in the array using the second loop, so we can compare the value we got in the first loop with all the elements in the array with the second loop.

IMPORTANT: In the second loop we make int i = first + 1 because we are looping every item in the list EXCLUDING only the one we are actually comparing, because the value we have is never gonna be smaller than itself.

After the two loops were made we make a condition inside the second loop, where we check if the the items in the for loop (arr[i]) is smaller than the value we got with the first loop (arr[index]) . If the condition is true we make the index, that holds our smaller number so far, be the index of the smaller number found. The if condition checks every number in the second loop until the end, getting the smaller number in the array and saving its index with the index = i .

Now that our second loop got to the end and we have the index of our smallest number we need to swap the position he is in

int[] sort(int[] arr) {
    int index;
    //looping the unsorted list
    for (int first = 0; first < arr.length; first++) {

        //index starts at first but changes in every loop
        index = first;


        //then every loop the index is compared with all numbers
        //except the one we are comparing to (the index)
        for (int i = first + 1; i < arr.length; i++) {
            //check if value is lower
            if (arr[i] < arr[index]) {
                //if it is, change index to it
                index = i;
            }
        }

        //holds the value of the minimum we found
        int temp = arr[index];
        //places the value that was in the start at the place we found our index
        arr[index] = arr[first];
        //puts the value from the index in the start
        arr[first] = temp;
    }
    //terminate the loop and return array sorted
    return arr;

}

Here I we have all the sort method ready, I put it all completed here so you don't get confused on where the pieces of code are in the big picture, but we are going to be talking about the end, the swap and return part:

        //holds the value of the minimum we found
        int temp = arr[index];
        //places the value that was in the start at the place we found our index
        arr[index] = arr[first];
        //puts the value from the index in the start
        arr[first] = temp;
    }
    //terminate the loop and return array sorted
    return arr;

}

I'm gonna talk about this giving an example that was made in CS50 algorithms part (highly recommend), you have two cups, one with a blue liquid and the other with a red liquid. You want to swap the blue liquid of the 1 cup to be in the 2 cup and the red liquid of the 2 cup to be in the 1 cup without mixing. What do you do? A good way to do this is have a "Temporary cup", a 3 cup that will hold your blue liquid, so you can put the red liquid in the 1 cup, and then put the blue liquid in the 2 cup.

In code we are doing the same thing! We are making a temporary variable int temp and assigning the value of the smallest number we found to it. Then we make the value of arr[index], that is current the smallest number, be the value of the first loop, and we make the value of the first loop be the temporary variable, the smallest number.

With that we made our swap! So after that the first iteration of the first loop finally ends and repeats itself again until we looked at every number and compared, choose and swap then. Now we just need to return the sorted array with return arr .

Time complexity

Before we print make our print method and then execute our code to see everything working let's explain the time complexity of this algorithm. We start the algorithm making a loop that goes through every number in the array. which means that we have a O(n) because n is the number of steps and is = to the number of elements we have in the array. After that we have a second loop, inside the first loop, that iterate through every number in the array too, so that's another O(n). So we have a O(n) that for every n inside of it there's another O(n), that makes O(n X n) or O(n^2). So the time complexity of this algorithm is O(n^2) !

Wait a second...

Maybe you are questioning yourself "But every time we make our second loop we make it be the position of the first loop + 1, so we don't check n entirely in the second loop, so it would be n-1,n-2..." and yes, you are actually right! at the end of the second loop we would be checking just one element, so the time complexity should be something like O(n X 1/2 X n). This is correct, but in the Big O notation we ignore constants like 1/2, so in the end we just have O(n X n) and that's why it stays like that!

Okay that was a mouthful, but we are almost at the end! now we are just going to create the last method, printArray:

    void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " | ");
        }
    }

Here we don't need to return anything, we are just making a for loop that goes through all the array and prints the values with a pipe | separating them.

Now we are gonna create a java file to execute and test this algorithm! Let's create a file called SelectionSortMain.java

package selectionSort;

public class SelectionSortMain {
    public static void main(String args[]) {
    SelectionSort selection = new SelectionSort();

    //create the array
    int[] arr = {10, 6, 4, 8, 2};

    //This is gonna print the original array
    System.out.println("Unsorted array: ");
    selection.printArray(arr);

    //sort the array
    selection.sort(arr);

    //used println here just to make a space since we used print in the printArray
    System.out.println();

    //print sorted array
    System.out.println("Sorted array: ");
    selection.printArray(arr);
    }

}

Here we just create an array, print it unsorted (with our printArray method) and then we use our sort method and print it again, so our output should be this:

Unsorted array: 
10 | 6 | 4 | 8 | 2 | 
Sorted array: 
2 | 4 | 6 | 8 | 10 |

And that's pretty much it! Hope this article helped you in some what way. You can check out the repo I made in Github with all the code and with more implementations of DS&A. I'm new to making articles and writing in general but I'm trying to improve! Any questions or suggestions are pretty much appreciated. Good luck on your learning journey!

Some useful links

Implementing Singly Linked Lists in Java

Guilherme_Konan — Thu, 10 Dec 2020 06:54:24 +0000

Linked lists are really important data structures, they let us store values in different parts of the memory and find them by their addresses. Today in this article I'm gonna go on how to implement a Singly Linked List in java.

lets create our first java file SinglyLinkedList.java

Inside lets start by making a class that will represent the Node

package singlyLinkedList;

class Node {
    //thats the value(data) that is inside the Node
    public int data;
    //Thats the pointer inside the Node, every Node
    //has a pointer that store the address of the next node
    //Here we call this pointers "next"
    public Node next;

    public void displayNodeData() {
        System.out.print( data +  " -> ");
    }

}

This class will represent the Node, every Node in a liked list stores a value, represent by our public int data in code, and a pointer to the next Node that will be represented by our public Node next in our code. Inside this class we made a method that will just print the data so that in the end we can see our results.

Okay now inside our class SinglyLinkedList we are gonna start by defining a Node that represents the start of our list, a head node.

public class SinglyLinkedList {
    //Its private because we only need to reference head
    //inside this class
    private Node head; //here head == null

IMPORTANT: head = null even if we don't write it explicitly, java does that for us.

We are gonna use head in our methods to reference the beginning of our list (aka our first node) and for iterations, we will see this now.

Our first method is gonna be a simple insert,We are gonna use this method to insert a value at the beginning of the list

    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        head = newNode;
    }

Here we first create a new Node called node Node node = new Node(); then we set the data of this node to the parameter data that we will pass as argument later when we call it. In the end we make the newNode point to the head (which is null) and then make head points to the newNode so now head is holding the address of this newNode and newNode is pointing to null, which is the end of the list.

IMPORTANT: Just to clear things out, if we insertFirst two times (like we are gonna do later) the second newNode is gonna start pointing to head which is the address of the first newNode and then head is gonna point to the second newNode making this:

 head
  ↓
newNode -> null

be this:

 head
  ↓
newNode2 -> newNode -> null

Now lets make our deleteFirst method

    public void deleteFirst() {
        //shifts the first node (head) to be where 
        //it was pointing (second node)
        head = head.next;
    }

This one is more simple and to the point, head points to what is next to the head. Basically shifts head to be the second node, making it the first node.

Before we continue with building our other methods lets make a printLinkedList method so you can see the results and have a better visualization of what the code is doing too.

Here is our printLinkedList method

    public void printLinkedList() {
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;

        }
        System.out.print("NULL");

    }

We just make a Node called current that starts at head,which means that the node current starts pointing to the address of the first node. Then we loop the current node so that every loop we Displays our node data (with the displayNodeData() we made in our node class) and shifts the current node to the next node, passing through all the nodes in the linked list until we find null (which is the end), after the loop we just print "NULL" to indicate end of the list and make a nicer representation with the print.

Now lets create another java file called LinkedListMain.java . This is the file we will execute.

package singlyLinkedList;

public class LinkedListMain {
    public static void main(String args[]) {
        SinglyLinkedList linkedList = new SinglyLinkedList();
        linkedList.insertFirst(1);
        linkedList.insertFirst(8);
        linkedList.insertFirst(5);
        linkedList.insertFirst(3);
        linkedList.deleteFirst();
        //its gonna be 5 -> 8 -> 1 -> NULL
        linkedList.printLinkedList();
    }
}

Here we are gonna call our methods, when you run it the output should be be 5 -> 8 -> 1 -> NULL

Now you can test the methods the way you want! Lets get back to creating our other methods.

We created methods for inserting in the first place and deleting the first place, but if we want to put something at the last place? Well lets create methods for it, starting with insertLast

    public void insertLast(int data) {
        Node current = head; //start from the first node
        //loop until current == null because you are looping
        //all the nodes until you find the end (null)
        while(current.next != null) {
            current = current.next;
        }
        //insert the newNode next to current
        //which now is the final node
        Node newNode = new Node();
        newNode.data = data;
        current.next = newNode;
    }

Okay, here we start by doing something pretty similar to what we did in the printLinkedList method, we start by the head and loop, but here we loop until the current is pointing to null and not IS equal null. Because with this we will have current as the last node, because the last node is the one that points to null. Then we create a newNode and make the current point to the newNode so now it is the last node because the order changed from

current -> null

current -> newNode -> null .

After that we can create our deleteLast method

    public void deleteLast() {
        Node current = head;
        Node temp = head;
        while (current.next != null) {
            temp = current;
            current = current.next;
        }
        current = temp;
        current.next = null;
    }

Here we make like the insertLast method and make the exact same loop, but we have something different. That is the Node temp, so we can move current to the last position with our loop, but we also move the temp alongside so that in the end we have current in the last position current -> null but we have temp before that temp -> current -> null . Then we make current shift to temp position and make current point to null.

Okay, that`s great and all but... what if we want to put something in the middle for example? Or delete it? Well we can make a method to put a node anywhere AFTER another node.

Lets start with the insertAfter
`

    public void insertAfter(Node after,int data) {
        Node current = head;
        Node temp = head;
        while (temp.data != after.data ) {
            temp = current;
            current = current.next;
        }
        Node newNode = new Node();
        newNode.data = data;
        temp.next = newNode;
        newNode.next = current;
    }

In theinsertAfterwe again usetempand we make a similar loop, but the condition is different. Now we want to match thetemp.datathat we are looping with theafter.datathat is a node we are gonna pass to our method. When the loop finishes we havetempin the place of ourafternode, which means we are gonna insert ournewNodeafter thetempnode where ourcurrentnode is. After the loop we create thenewNodeand we make temp point to thenewNodeand makenewNodepoint to thecurrent` node.

Now we have our last method, the deleteAfter method

    public void deleteAfter(Node after) {
        Node current = head; 
        while (current.data != after.data) {
            current = current.next;
        }
        current.next = current.next.next;
    }

Here we check if the current.data is != to after.data so we can have the position of the after node (the same way we made with temp in the last one). Then we just make the current point to what the it was pointing before was pointing to. Example:

current -> node1 -> node2

After the current.next = current.next.next:

current -> node2

And that`s all our methods implemented and explained. Now we can test all of them

package singlyLinkedList;

public class LinkedListMain {
    public static void main(String args[]) {
        SinglyLinkedList linkedList = new SinglyLinkedList();
        linkedList.insertFirst(1);
        linkedList.insertFirst(8);
        linkedList.insertFirst(5);
        //its gonna be 5 -> 8 -> 1 -> NULL

        linkedList.insertLast(3);
        //now its gonna be 5 -> 8 -> 1 -> 3 -> NULL
        Node node = new Node();
        node.data = 1;
        linkedList.insertAfter(node, 10);
        // now its gonna be 5 -> 8 -> 1 -> 10 -> 3 -> NULL


        Node node2 = new Node();
        node2.data = 8;
        linkedList.deleteAfter(node2);
        // now its gonna be 5 -> 8 -> 10 -> 3 -> NULL
        linkedList.deleteFirst();
        //now its gonna be 8 -> 10 -> 3 -> NULL
        linkedList.insertFirst(14);
        //now its gonna be 14 -> 8 -> 10 -> 3 -> NULL
        linkedList.insertLast(40);
        // now its gonna be 14 -> 8 -> 10 -> 3 -> 40 -> NULL
        linkedList.deleteFirst();
        //now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
        linkedList.insertLast(56);
        //now its gonna be 8 -> 10 -> 3 -> 40 -> 56 -> NULL
        linkedList.deleteLast();
        // now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
        linkedList.printLinkedList();
    }
}

I hope you understood or at least I could help just a little bit in your learning. This is my first article so I may or may not have explained or write in a good way but I will try to improve as I write more! If you want the source code you can check my repository in Github where I'm trying to make a list of Data Structures and Algorithms implemented in java (and maybe later in C ) with everything up to date or the source below that is the exact same code as above, I will let some links that you can check more about linked lists and that's it. Good studying and good luck!

SinglyLinkedList.java

package singlyLinkedList;

class Node {
    //thats the value(data) that is inside the Node
    public int data;
    //Thats the pointer inside the Node, every Node
    //has a pointer that store the address of the next node
    //Here we call this pointers "next"
    public Node next;

    public void displayNodeData() {
        System.out.print( data +  " -> ");
    }

}

public class SinglyLinkedList {
    //Its private because we only need to reference head
    //inside this class
    private Node head; //here head == null

    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        head = newNode;
    }

    public void deleteFirst() {
        //shifts the first node (head) to be where 
        //it was pointing (second node)
        head = head.next;
    }

    public void insertLast(int data) {
        Node current = head; //start from the first node
        //loop until current == null because you are looping
        //all the nodes until you find the end (null)
        while(current.next != null) {
            current = current.next;
        }
        //insert the newNode next to current
        //which now is the final node
        Node newNode = new Node();
        newNode.data = data;
        current.next = newNode;
    }

    public void deleteLast() {
        Node current = head;
        Node temp = head;
        while (current.next != null) {
            temp = current;
            current = current.next;
        }
        current = temp;
        current.next = null;
    }

    public void insertAfter(Node after,int data) {
        Node current = head;
        Node temp = head;
        while (temp.data != after.data ) {
            temp = current;
            current = current.next;
        }
        Node newNode = new Node();
        newNode.data = data;
        temp.next = newNode;
        newNode.next = current;
    }

    public void deleteAfter(Node after) {
        Node current = head; 
        while (current.data != after.data) {
            current = current.next;
        }
        current.next = current.next.next;
    }

    public void printLinkedList() {
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;

        }
        System.out.print("NULL");

    }
}

LinkedListMain.java

package singlyLinkedList;

public class LinkedListMain {
    public static void main(String args[]) {
        SinglyLinkedList linkedList = new SinglyLinkedList();
        linkedList.insertFirst(1);
        linkedList.insertFirst(8);
        linkedList.insertFirst(5);
        //its gonna be 5 -> 8 -> 1 -> NULL

        linkedList.insertLast(3);
        //now its gonna be 5 -> 8 -> 1 -> 3 -> NULL
        Node node = new Node();
        node.data = 1;
        linkedList.insertAfter(node, 10);
        // now its gonna be 5 -> 8 -> 1 -> 10 -> 3 -> NULL


        Node node2 = new Node();
        node2.data = 8;
        linkedList.deleteAfter(node2);
        // now its gonna be 5 -> 8 -> 10 -> 3 -> NULL
        linkedList.deleteFirst();
        //now its gonna be 8 -> 10 -> 3 -> NULL
        linkedList.insertFirst(14);
        //now its gonna be 14 -> 8 -> 10 -> 3 -> NULL
        linkedList.insertLast(40);
        // now its gonna be 14 -> 8 -> 10 -> 3 -> 40 -> NULL
        linkedList.deleteFirst();
        //now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
        linkedList.insertLast(56);
        //now its gonna be 8 -> 10 -> 3 -> 40 -> 56 -> NULL
        linkedList.deleteLast();
        // now its gonna be 8 -> 10 -> 3 -> 40 -> NULL
        linkedList.printLinkedList();
    }
}

DEV Community: Guilherme_Konan

Why we use "key" in React?

The problem

Reconciliation algorithm

Okay really interesting, but why key?

Conclusion

The compiling process

The compiling process

Preprocessing

Compiling

Assembling

Linking

Links

Customizing Git Bash in Windows

Finding and Editing git-prompt

Useful Links

Minha experiência no NLW #4

Trilhas

Talvez você tenha pensado nisso...

Recomendações

Implementing Binary Search in Java

Iterative Search

Time Complexity

Recursive Search

Time complexity

Links

Implementing Selection Sort in Java

Time complexity

Wait a second...

Some useful links

Implementing Singly Linked Lists in Java

Some Links that you may find interesting