Forem: Anubhav Shukla

Understanding Perceptron. How does it work, without going into Mathematics

Anubhav Shukla — Thu, 11 Jan 2024 06:59:11 +0000

Understanding the Perceptron

The perceptron is like a decision-making algorithm. Imagine you want to know if someone will pass an exam. The perceptron takes information like IQ and study hours, gives each piece a 'weight' based on its importance, adds them up, and decides: 'Yes, they'll pass' or 'No, they won't.' It's like a smart helper that learns from mistakes and gets better at making these yes-or-no decisions over time

Let's see this with the help of a figure

The red dot represents the student who failed the exam while the green one represents the one who passed.

Now what perceptron does is draw a line to separate this yes and no

This is what it does:

⭐. First, it will start a line (that will separate pass and fail) from some initial place

⭐. From here the loop begins.

⭐. Choose a random point

⭐. It checks if that student is going to fail or pass. It does that by putting the coordinate of that point in the equation of the line.

X * IQ + Y * studyHour.

Now if the solution of the equation becomes positive it will pass otherwise it will fail

⭐. Suppose it chooses this point

The green point should lie in the positive part of the line (as it represents the pass) while the red one should lie in the negative part of the line.

Since the selected point is at the correct position we don't do anything and choose another point.

⭐.Now we choose this point

This point is also in the correct position we don't do anything and choose another point.

⭐.Now we choose this point

Now this point lies on the wrong side and also putting the coordinate of this point in our line equation will produce a negative result. So we move our line such that this point lies in the negative part of the figure

⭐.After following these steps repeatedly it will finally give a line like this

Now if we have a student with its IQ and study hours we just need to put that information in the equation of the line and it will tell us if the student is going to pass or fail

Unraveling Multicollinearity: Causes, Implications, and Solutions

Anubhav Shukla — Sat, 23 Dec 2023 08:05:45 +0000

What is multicollinearity

Multicollinearity occurs when two or more predictor variables in a regression model are highly correlated, leading to issues in estimating individual coefficients. This tangled web can introduce numerical instability, making it tricky to pinpoint the true relationship between predictors and the target variable.

But wait, how does it create an issue in estimating individual coefficients?

Why multicollinearity is bad

Suppose this is the equation for knowing the accuracy of the model

Here y is the dependent variable and x1 and x2 are independent variables where β1 and β2 represent the weight of the x1 and x2 respectively which simply means in determining y how much weight does x1 possess. So if we want to see how much y depends upon x1 we can calculate β1 by keeping other variables constant.

Now if the two variables x1 and x2 are correlated then we cannot isolate x1 as it depends upon x2 and hence we will have a problem in calculating the value of β1.

So in place, we need to find out how our target depends upon each feature having multicollinearity in a data is very bad.

How to remove multicollinearity

We can apply feature selection. Where we identify which columns are important and drop the rest.
We can apply the regression technique which introduces a penalty term which is used to shrink the coefficient.
Calculate VIF (Variance Inflation Factor). Variables with high VIF values (typically above 5 or 10) may indicate multicollinearity.
We can plot a scatter plot and by looking at the graph we can tell which data are correlated.
We can increase the size of the data. Sometimes, increasing the size of your dataset can help alleviate multicollinearity issues. More data can provide a more representative sample of the population, leading to more stable coefficient estimates.

Code

np.random.seed(42)

# These are correlated data
x1 = np.random.rand(100)
x2 = 0.8 * x1 + 0.2 * np.random.rand(100)
x3 = 0.7 * x1 + 0.3 * np.random.rand(100)
x4 = 0.6 * x1 + 0.4 * np.random.rand(100)
x5 = 0.5 * x1 + 0.5 * np.random.rand(100)

# These are uncorrelated data
x6 = np.random.rand(100)
x7 = np.random.rand(100)
x8 = np.random.rand(100)
x9 = np.random.rand(100)
x10 = np.random.rand(100)

Let's see if we plot the graph between two correlated data how it going to look

plt.scatter(x1, x2)

and if we plot the graph between the uncorrelated data

plt.scatter(x6, x7)

From the figure, we can see which columns are correlated and if we want to drop the correlated columns we can easily do that

Now let's see what a correlation matrix is going to tell us

# First we need to make our variable into a data frame
data = pd.DataFrame({
    "x1": x1,
    "x2": x2,
    "x3": x3,
    "x4": x4,
    "x5": x5,
    "x6": x6,
    "x7": x7,
    "x8": x8,
    "x9": x9,
    "x10":x10
})

matrix = data.corr()
matrix

Here, a high value represents a very large correlation. For example, the x2 and x1 correlate 0.97 which is very high. The negative value represents the negative correlation.

We can also see this correlation using the heatmap provided by the seaborn.

import seaborn as sns
plt.figure(figsize=(10, 7))
sns.heatmap(corre, annot=True, cmap='coolwarm')
plt.title("Correlation Matrix")
plt.show()

If the data is very large it will be very difficult to tell which columns are correlated. So let's build a function which takes threshold (amount of correlation) as a parameter and returns the column name

def correlation(data, threshold):

    # so that we don't get duplicate column
    correlated_col = set()

    correlated_matrix = data.corr()
    for i in range(len(correlated_matrix.columns)):
        for j in range(i):

            # if the correlation is greater than the threshold
            if abs(correlated_matrix.iloc[i, j]) > threshold:
                related_col_name = correlated_matrix.columns[i]
                correlated_col.add(related_col_name)

    return correlated_col

correlation(data, 0.9)
Output
{'x2', 'x3'}
and
correlation(data, 0.7)
Output
{'x2', 'x3', 'x4', 'x5'}

Now if we want to drop the correlated column we can easily do that.

Conclusion

By understanding and addressing multicollinearity, we can enhance the robustness and interpretability of our models, ensuring more accurate insights for data-driven decision-making.

Leetcode 242. Valid Anagram. DSA # 5

Anubhav Shukla — Thu, 22 Sep 2022 05:49:50 +0000

Question Link

Easy

Python

In this question, we have to check if the two strings are anagrams of each other or not.
Means we have to check if the two strings have the same characters or not.

Now how can we check that?

We can sort both the strings and then compare them.

for example: s = "anagram", t = "nagaram"

After sorting: s = "aagmnr", t = "aagmnr"

Now we can compare both the strings.

But this approach will take O(nlogn) time complexity. And we don't want that

You can think like this:

There are 26 alphabets in the English language.
So each character of the string can be one of the 26 alphabets.
So we can create an array of size 26 and store the count of each character in the array.
We can store the count of any given string in the array.
And check the other string, if we encounter 0 in the array then that means that this is the new character, then we can return False.

Let's understand it with the help of an example:

s = "anagram", t = "nagaram"

 storage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 - We iterate over the string s and store the count of each character in the array.
    - s = "anagram"
     ---------------------------
     1. a -> storage[0] = 1
     2. n -> storage[13] = 1
     3. a -> storage[0] = 2
     4. g -> storage[6] = 1
     5. r -> storage[17] = 1
     6. a -> storage[0] = 3
     7. m -> storage[12] = 1
     ---------------------------

 storage = [3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] 

 Now we iterate over the string t and check if we encounter 0 or not
 If we encounter 0 then that means that this character is not present in the string s.

    - t = "nagaram"
     ---------------------------
     1. n -> storage[13] = 1  Since n is present we subtract 1 from storage[13] = 0
     2. a -> storage[0] = 3   Since a is present we subtract 1 from storage[0] = 2
     3. g -> storage[6] = 1   Since g is present we subtract 1 from storage[6] = 0
     4. a -> storage[0] = 2   Since a is present we subtract 1 from storage[0] = 1
     5. r -> storage[17] = 1  Since r is present we subtract 1 from storage[17] = 0
     6. a -> storage[0] = 1   Since a is present we subtract 1 from storage[0] = 0
     7. m -> storage[12] = 1  Since m is present we subtract 1 from storage[12] = 0      
     ---------------------------     

     Since we don't encounter 0 in the array, we can return True.

     Let's take another example:

     s = "abbcc", t = "abbccc"

        storage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        - s = "abbcc"
         ---------------------------
         1. a -> storage[0] = 1
         2. b -> storage[1] = 1
         3. b -> storage[1] = 2
         4. c -> storage[2] = 1
         5. c -> storage[2] = 2
         ---------------------------

        storage = [1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        - t = "abbccc"
         ----------------
            1. a -> storage[0] = 1  Since a is present we subtract 1 from storage[0] = 0
            2. b -> storage[1] = 2  Since b is present we subtract 1 from storage[1] = 1
            3. b -> storage[1] = 1  Since b is present we subtract 1 from storage[1] = 0
            4. c -> storage[2] = 2  Since c is present we subtract 1 from storage[2] = 1
            5. c -> storage[2] = 1  Since c is present we subtract 1 from storage[2] = 0
            6. c -> storage[2] = 0  Sice we encounter 0 in the array, we can return False.

            ---------------------------

Let's implement it:

def isAnagram(s: str, t: str) -> bool:
    s_length, t_length = len(s), len(t)
    if s_length != t_length:
        return False

    storage = [0] * 26

    for char in s:
        storage[ord(char) - ord('a')] += 1

    for char in t:
        if storage[ord(char) - ord('a')] == 0:
            return False
        storage[ord(char) - ord('a')] -= 1

    return True

Time Complexity: O(n)
Space Complexity: O(26) = O(1)

Instead of using an array of size 26, we can use a dictionary to store the count of each character.

def isAnagram(self, s: str, t: str) -> bool:
    s_length, t_length = len(s), len(t)
    if s_length != t_length:
        return False

    storage = {}

    for char in s:
        storage[char] = storage.get(char, 0) + 1

    for char in t:
        if char not in storage or storage[char] == 0:
            return False
        storage[char] -= 1

    return True

Leetcode 217. Contains Duplicate. DSA - #4

Anubhav Shukla — Fri, 16 Sep 2022 05:28:19 +0000

Question Link

Python || C++ || TypeScript

Brute Force Approach

This approach is very simple, so I am not going to waste much time in this approach

We take one element and compare it with all the other elements.
We do this for all the elements.

Code

def containsDuplicateMethod1(nums: list[int]) -> bool:
    length = len(nums)
    for i in range(length):
        for j in range(i + 1, length):
            if nums[i] == nums[j]:
                return True
    return False

Time Complexity: O(n^2)
Space Complexity: O(1)

Better Approach using Sorting

Since we have to find the duplicate elements, so we can sort the array and then find the duplicate elements.
Duplicate elements will be adjacent to each other.

For example: nums = [1, 2, 3, 1]

After sorting: nums = [1, 1, 2, 3]

Now we can find the duplicate elements by comparing the adjacent elements.

Code

def containsDuplicateMethod2(nums: list[int]) -> bool:
    nums.sort()
    length = len(nums)
    for i in range(length - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False

Time Complexity: O(nlogn)
Space Complexity: O(1)

Best Approach using Hashing

This method is also very easy to understand.

We create a Set.
We traverse the array and check if the element is present in the Set or not.
If the element is present in the Set then we return True.
If the element is not present in the Set then we add the element in the Set.
If we traverse the whole array, and we don't find any duplicate element then we return False.

Code

def containsDuplicateMethod3(nums: list[int]) -> bool:
    storage = set()
    for value in nums:
        if value in storage:
            return True
        storage.add(value)

    return False

Time Complexity: O(n)
Space Complexity: O(n)

Bonus

Best Approach using Hashing (one liner)

def containsDuplicateMethod4(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))

LeetCode - 121. Best Time to Buy and Sell Stock. DSA #3 Explanation.

Anubhav Shukla — Mon, 29 Aug 2022 18:50:00 +0000

Leetcode - 121. Best Time to Buy and Sell Stock

Easy

Question Link

Code

Python || C++ || TypeScript

First thing you should know is that the problem is asking for the maximum profit that can be made by buying and selling a stock once.
And Maximum Profit you can make is the difference between the maximum price and the minimum price i.e. if we buy the stock when
it's price is minimum and sell it when it's price is maximum then we get maximum profit.

For example, if we have prices [1, 2, 3, 4, 5] then we can buy the stock at 1 and sell it at 5, profit is 4.

Similarly, if we have prices [7, 1, 5, 3, 6, 4] then we can buy the stock at 1 and sell it at 6, profit is 5.

And if we have prices [7, 6, 4, 3, 1] then we can't make any profit.

Let's first discuss the brute force approach.

Brute Force Approach

We buy the stock at the first day
We calculate all the profit we can make by selling it at every day, means we sell it at day 2 and store the profit then we sell it at day 3 and store the profit and so on.
Repeat these two points for all the days.
Return the maximum profit we can make.

We can code the above approach using two for loop.

Code

def bestTimeForStockMethod1(prices: list[int]) -> int:
    max_profit = 0
    for buy_index, buy_value in enumerate(prices):
        for sell_index in range(buy_index + 1, len(prices)):
            curr_profit = prices[sell_index] - buy_value
            max_profit = max(max_profit, curr_profit)
    return max_profit

Let's understand the above code with the help of an example.

prices = [7, 1, 5, 3, 6, 4]

--> First iteration

We buy the stock at the first day i.e. we buy the stock at price 7

We sell the stock at day 2 i.e. we sell the stock at price 1.
Profit is 1 - 7 = -6 i.e. we are at loss.
We update the max_profit.
We sell the stock at day 3 i.e. we sell the stock at price 5.
Profit is 5 - 7 = -2 i.e. we are at loss.
We update the max_profit.
.........continues.........................
We sell the stock at day 6 i.e. we sell the stock at price 4.
Profit is 4 - 7 = -3 i.e. we are at loss.
We update the max_profit.

--> Second iteration

We buy the stock at the second day i.e. we buy the stock at price 1

We sell the stock at day 3 i.e. we sell the stock at price 5.
Profit is 5 - 1 = 4 i.e. we are at profit.
We update the max_profit.

And so on.

At the end we will have the maximum profit we can make.

Time Complexity: O(n^2)
Space Complexity: O(1)

Better approach

prices = [7, 1, 5, 3, 6, 4]

Just like the above approach let's buy the stock at day 1 i.e at price 7

Now when we sell the stock at day 2 i.e. at price 1 we will get the profit 1 - 7 = -6
-6. What kind of profit is that?. It's a loss.
And from this loss we can say that price of stock at day 2 is less than price of stock at day 1.
So why do we buy the stock at day 1? Let's buy the stock at day 2 i.e. at price 1. So we move
our pointer to day 2 i.e. at price 1.

Now when we sell the stock at day 3 i.e. at price 5 we will get the profit 5 - 1 = 4
4. We store this profit in max_profit.

Now we sell the stock at day 4 i.e. at price 3.
We will get the profit 3 - 1 = 2. We will store the maximum profit i.e. 4

Now we sell the stock at day 5 i.e. at price 6.
We will get the profit 6 - 1 = 5. We will store the maximum profit i.e. 5

Now we sell the stock at day 6 i.e. at price 4.
we will get the profit 4 - 1 = 3. We will store the maximum profit i.e. 5

Now we are at the end of the loop and since we don't encounter any loss which means we have bought the stock at lowest possible value.
Therefore, the max_profit which we store is the maximum profit we can make.

Let's take another example but with less english

prices = [7, 2, 5, 6, 1, 4]

Let's have two pointer

[7,     2, 5, 6, 1, 4]
 |      |
 Buy    sell

 2 - 7 = -5 
 Loss which means we can buy stock at lower price 
 therefore we move our buy pointer to sell pointer and increase sell pointer by 1

[7, 2,     5, 6, 1, 4]
 |         |
 buy       sell

5 - 2 = 3    max_profit = 3

[7, 2,     5, 6, 1, 4]
    |         |
    buy      sell

6 - 2 = 4    max_profit = 4

[7, 2,  5, 6, 1, 4]
    |         |
    buy      sell

1 - 2 = -1   max_profit = 4

Loss which means we can buy stock at lower price 
therefore we move our buy pointer to sell pointer and increase sell pointer by 1

[7, 2,  5, 6, 1,    4]
              |     |
              buy   sell

4 - 1 = 3    max_profit = 4

we are at the end of the loop. Therefore, we return max_profit i.e 4

Time Complexity: O(n)
Space Complexity: O(1)

Code

We can code this using two pointer approach.

def bestTimeForStockMethod2(prices: list[int]) -> int:
    max_profit = 0
    buy, sell = 0, 1
    while sell < len(prices):
        curr_profit = prices[sell] - prices[buy]
        if curr_profit < 0:
            buy = sell
        max_profit = max(max_profit, curr_profit)
        sell += 1
    return max_profit

Leaders in an Array. DSA #2

Anubhav Shukla — Wed, 06 Jul 2022 17:17:34 +0000

Question

Think of a solution with the help of an example

First I will discuss Brute force method

Let arr = [16, 17, 4, 3, 5, 2]

Is 16 a leader, no because 17 is greater than 16
Is 17 a leader, Yes because it is greater than all the element in it's right
Is 4 a leader, no because of 5.
Is 3 a leader, no because of 5.
Is 5 a leader, Yes because it is greater than all the element in it's right.
Is 2 a leader, Yes because there is no element in it's right so it is obviously greatest.

From this thinking process, we can see two things.

The last number will always be the leader.
If we take a number and compare it with every number which comes after it we can easily find out which number is the leader.

This will require 2 loop.
First loop will take a particular number.
Second loop will compare it with all the numbers after it. To check if it is greater than all the number.

Let's test our theory.
arr = [16, 17, 4, 3, 5, 2]

let's take 16
Is 16 greater than 17 -> False. Therefore we break out of the loop.
let's take 17.
Is 17 greater than 4 -> True.
Is 17 greater than 3 -> True.
Is 17 greater than 2 -> True.
Is 17 greater than 5 -> True.
Is 17 greater than 2 -> True.

We didn't break out of the loop. Therefore 17 is the leader.
And we will continue this process till the outer loop terminates.

Code for the above approach

vector<int> findLeader(int arr[], int n){

     // For storing the result
    vector<int> ans;

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(arr[i] < arr[j]){
                break;
            }
        }
    }
    return ans;

}

but this code is not complete because we are not storing the leader in ans anywhere in the code. So where we should add the statement to store leaders in the ans.

The answer is very simple if we ask one question to ourself.

When we need to add the numbers in the ans?

When the loop is not break. And to know this we can simply add the variable in our code whose value we will change when the loop breaks. And in the end we can simply check if the value of the variable is changed or not. If it is not changed we add the number to the ans.

Final code.

vector<int> findLeader(int arr[], int n){
    vector<int> ans;
    int flag;
    for(int i = 0; i < n; i++){
// Always set to 0 for new value
        flag = 0;
        for(int j = i + 1; j < n; j++){
            if(arr[i] < arr[j]){
// value is changed
                flag++;
                break;
            }
        }
// If value is not changed
        if(flag == 0){
            ans.push_back(arr[i]);
        }
    }
    return ans;

}

Better approach

Think like this leader is those numbers which are greater than all the numbers in there right so why don't we start our loop from the right and keep track of the max. If the current number is greater than the max then we can say that it is a leader. Let's understand this approach with the help of an example.

arr = [16, 17, 4, 3, 5, 2]

current window = [2]
since last element is always leader we add 2 to our res and current max in the window is 2.

current window = [5, 2]
Is 5 is greater than the current max (2) -> True. Therefore we can say it is greater than all the elements on it's right because it is greater than the max in it's right. We add 5 to our res. Current max in the window is 5.

current window = [3, 5, 2]
Is 3 is greater than the current max (5) -> False. Which means 3 can't be a leader because it is smaller than 5 which falls on it's right side.

current window = [4, 3, 5, 2]
Is 4 is greater than the current max (5) -> False. Which means 4 can't be a leader because it is smaller than 5 which falls on it's right side.

current window = [17, 4, 3, 5, 2]
Is 17 is greater than the current max (5) -> True. Therefore we can say it is greater than all the elements on it's right because it is greater than the max in it's right. We add 17 to our res. Current max in the window is 17.

current window = [16, 17, 4, 3, 5, 2]
Is 16 is greater than the current max (17) -> False. Which means 16 can't be a leader because it is smaller than 17 which falls on it's right side.

Loop will end and our res will contain = [2, 5, 17]

To code this problem we need two variables
First variable should point to the current max element in the right side.
Second pointer should point to the new element which we want to check for the leader

Code for the above approach

vector<int> findLeader2(int arr[], int n){
    // Since last element is always a leader  
    vector<int> res = {arr[n - 1]};
    int 
        i = n - 1,   // first pointer which will point to the current max
        j = i - 1;   // Second pointer which will point to new element to check for leader

    while (j >= 0){
        if(arr[j] >= arr[i]){
            res.push_back(arr[j]);
            // Pointer 1 is set to the new current max
            i = j;
        }
        j--;
    }
        // To return the number in order.
        reverse(res.begin(), res.end());
        return res;
}

Let's Dry run the above code

Let arr = [16, 17, 4, 3, 5, 2]

res = [2]
i = 5
j = 4
------First iteration---------

Is 5 > 2 ---> True.
res = [2, 5]
i = 5 ( i should always point to the max in the current window)
j = 3

------Second iteration---------

Is 3 > 5 ---> False.
res = [2, 5]
i = 5
j = 2

------Third iteration---------

Is 4 > 5 ---> False.
res = [2, 5]
i = 5
j = 1

------Fourth iteration---------

Is 17 > 5 ---> True.
res = [2, 5, 17]
i = 17
j = 0

------Fifth iteration---------

Is 16 > 17 ---> False.
res = [2, 5, 17]
i = 5
j = -1

Loop terminates

After reversing res = [17, 5, 2]

How to code a simple linear gradient generator using ReactJS.

Anubhav Shukla — Mon, 20 Jun 2022 18:08:57 +0000

This is what we are going to code.

Final code link

For styling our react app I am going to use style-components. If you don't know or want a refresher refer to this awesome article.

Now let the fun begins........

import React from "react";
import styled from "styled-components";

const GradientContainer = styled.div``;

const App = () => {
return (
// Here I will begin the code
}

export default App

This is the basic setup for our app. I am writing my code in the App component, you can write in whatever component you want.

Also, I am going to write all my styles inside GradientContainer. You can style your react app however you want.

First, let's code the structure of our app

       <GradientContainer>
    <div className="gradient_container_header">
      <h1 className="gradient_container_header_heading">
        Gradient Generator
      </h1>
      <h3 className="gradient_container_header_subheading">
        Generate your gradient
      </h3>
    </div>
    <div className="gradient_container_main">
      <div className="gradient_container_main_color_box">

         // first ColorInput will go here
        <div className="gradient_conatiner_main_color_box_range">

        // first Range Input

        </div>
      </div>
      <div className="gradient_container_main_gradient_box">

       // Gradient Box will go here


      </div>
      <div className="gradient_container_main_color_box">

       // Second ColorInput will go here

        <div className="gradient_conatiner_main_color_box_range">

       // Second Range Input will go here


        </div>
      </div>
    </div>
    <div className="gradient_container_footer">
      <h3>In Deg</h3>

      // Third Range Input will go here


      <h3 className="gradient_container_footer_text">
        Code for the gradient that you have generated
      </h3>
      <h1 className="gradient_container_footer_code">

      // Code will go here


      </h1>
    </div>
  </GradientContainer>

Output

Now let's understand the above structure line by line.

I created a div with className "gradient_container_header" which will act as a container for our header element.

Below this, the structure is a little bit complex and hard to understand but I will try my best to tell you as simple as possible.
First, let's understand what structure we are aiming for.

Here, you can see the mid part contain 3 component:- Color Picker and Range part || Gradient part || Color Picker and Range part

Therefore I created a div with className "gradient_container_main" which will act as a mid-part and inside that div, I have created three more div which will contain the three components, and with the help of flex-box we will achieve what we are aiming for.

Styling our structure.

const GradientContainer = styled.div`
  .gradient_container_header {
    text-align: center;
    .gradient_container_header_heading {
      font-size: max(3vw, 20px);
    }
    .gradient_container_header_subheading {
      font-size: max(1.5vw, 10px);
      color: rgba(0, 0, 0, 0.5);
    }
  }

  /* To arrange the components side by side */
  .gradient_container_main {
    display: flex;
    justify-content: center;
    gap: 5em;

    .gradient_container_main_color_box {
      display: flex;
      flex-direction: column;
      gap: 5em;
      align-items: center;
      justify-content: center;

      /* To rotate the range input */
      .gradient_conatiner_main_color_box_range {
        height: max-content;
        transform: rotateZ(-90deg);
      }
    }
  }
  .gradient_container_footer {
    text-align: center;
  }
`;

Output

How to code color picker

Here we are using a two color picker so instead of coding the color picker inside the app component (or whatever component you are currently working on ) it will be more convenient to make it a separate component and use that component wherever we want the color picker.

import React from "react";
import styled from "styled-components";

const ColorInputStyle = styled.input``;
const ColorInput = (props) => (
  <ColorInputStyle
    type="color"
  />
);
export default ColorInput;

Now let's use this component inside the App

    <GradientContainer>
    <div className="gradient_container_header">
      <h1 className="gradient_container_header_heading">
        Gradient Generator
      </h1>
      <h3 className="gradient_container_header_subheading">
        Generate your gradient
      </h3>
    </div>
    <div className="gradient_container_main">
      <div className="gradient_container_main_color_box">

         <ColorInput />
        <div className="gradient_conatiner_main_color_box_range">

        // first Range Input

        </div>
      </div>
      <div className="gradient_container_main_gradient_box">

       // Gradient Box will go here


      </div>
      <div className="gradient_container_main_color_box">

       <ColorInput />

        <div className="gradient_conatiner_main_color_box_range">

       // Second Range Input will go here


        </div>
      </div>
    </div>
    <div className="gradient_container_footer">
      <h3>In Deg</h3>

      // Third Range Input will go here


      <h3 className="gradient_container_footer_text">
        Code for the gradient that you have generated
      </h3>
      <h1 className="gradient_container_footer_code">

      // Code will go here


      </h1>
    </div>
  </GradientContainer>

Output

Now let's add some styling to our colorInput

import React from "react";
import styled from "styled-components";

const ColorInputStyle = styled.input`
  border-radius: 50%;
  width: max(5vw, 50px);
  height: max(5vw, 50px);
`;
const ColorInput = (pros) => (
  <ColorInputStyle
    type="color"
  />
);
export default ColorInput;

Output

Notice how the main color area is still square. The code to make it a circle is given below

import React from "react";
import styled from "styled-components";

const ColorInputStyle = styled.input`
  border-radius: 50%;
  width: max(5vw, 50px);
  height: max(5vw, 50px);

  &::-webkit-color-swatch {
    border-radius: 50%;
  }
  &::-moz-color-swatch {
    border-radius: 50%;
  }
`;
const ColorInput = (pros) => (
  <ColorInputStyle
    type="color"
  />
);
export default ColorInput;

Output

Now it's look perfect😍.

How to code range input

import React from "react";
import styled from "styled-components";

const RangeInputStyle = styled.input``;
const RangeInput = (props) => (
  <RangeInputStyle
    type="range"
    min={0}
    max={100}
  />
);
export default RangeInput;

Now lets use this this inside our App component

<GradientContainer>
      <div className="gradient_container_header">
        <h1 className="gradient_container_header_heading">
          Gradient Generator
        </h1>
        <h3 className="gradient_container_header_subheading">
          Generate your gradient
        </h3>
      </div>
      <div className="gradient_container_main">
        <div className="gradient_container_main_color_box">
          <ColorInput />

          <div className="gradient_conatiner_main_color_box_range">
            <RangeInput />
          </div>
        </div>
        <div className="gradient_container_main_gradient_box">
          // Gradient Box will go here
        </div>
        <div className="gradient_container_main_color_box">
          <ColorInput />

          <div className="gradient_conatiner_main_color_box_range">
            <RangeInput />
          </div>
        </div>
      </div>
      <div className="gradient_container_footer">
        <h3>In Deg</h3>

        <RangeInput />

        <h3 className="gradient_container_footer_text">
          Code for the gradient that you have generated
        </h3>
        <h1 className="gradient_container_footer_code">// Code will go here</h1>
      </div>
    </GradientContainer>

Output

Let's code gradient box

For this, we need to create a box with some height and width and set the background to a linear gradient.

import React from "react";
import styled from "styled-components";

const GradientBoxStyle = styled.div`
  width: max(20vw, 200px);
  height: max(30vw, 300px);
  background: linear-gradient(45deg, red, blue);
  margin: 3em auto;
  border-radius: 30px;
`;

const GradientBox = (props) => (
  <GradientBoxStyle
  />
);

export default GradientBox;

Let's use it inside the App component

    <GradientContainer>
      <div className="gradient_container_header">
        <h1 className="gradient_container_header_heading">
          Gradient Generator
        </h1>
        <h3 className="gradient_container_header_subheading">
          Generate your gradient
        </h3>
      </div>
      <div className="gradient_container_main">
        <div className="gradient_container_main_color_box">
          <ColorInput />

          <div className="gradient_conatiner_main_color_box_range">
            <RangeInput />
          </div>
        </div>
        <div className="gradient_container_main_gradient_box">
          <GradientBox />
        </div>
        <div className="gradient_container_main_color_box">
          <ColorInput />

          <div className="gradient_conatiner_main_color_box_range">
            <RangeInput />
          </div>
        </div>
      </div>
      <div className="gradient_container_footer">
        <h3>In Deg</h3>

        <RangeInput />

        <h3 className="gradient_container_footer_text">
          Code for the gradient that you have generated
        </h3>
        <h1 className="gradient_container_footer_code">// Code will go here</h1>
      </div>
    </GradientContainer>

Output

Now if I try to pick some color from the color picker nothing will happen the color of the gradient box will remain the same.

because right now our gradient box has a static background. But we want to change the background of the gradient box to the color user picked which means we need to change the state of the app as the user changes the color of the color picker and the best way to deal with this scenario is to use useState hook (because I am using functional components)

What we need to do

Create a variable (using useState because we also need to change the state of our app) that will store the value of the color as the user changes the color of the color picker.
Pass that variable to the gradient box so that we can apply that color to the background.

Let's tackle the first part.

Create a useState hook that will store the color of the color picker.

const App = () => {
  const [gradientValues, setGradientValues] = useState({
    color1: "#bb00ff"
  });

I have also given some default colors to this variable. This default color will be rendered when our app will be loaded for the first time.

Now let's tackle the second part.

Simply pass this variable as a prop to the GradientBox component.

        <div className="gradient_container_main_gradient_box">
          <GradientBox 
          color1 = {gradientValues.color1}/>
        </div>

And in the GradientBox component


import React from "react";
import styled from "styled-components";

const GradientBoxStyle = styled.div`
  width: max(20vw, 200px);
  height: max(30vw, 300px);
  background: linear-gradient(45deg, red, blue);
  margin: 3em auto;
  border-radius: 30px;
`;

const GradientBox = ({
  color1
}) => (
  <GradientBoxStyle 
  color1 = {color1}
  />
);

export default GradientBox;

Instead of using props, I destructured it using JavaScript object destructuring to use the direct value and also pass this value inside the style component so that I can access this variable inside my stylesheet.

Now set the background to the chosen color.

import React from "react";
import styled from "styled-components";

const GradientBoxStyle = styled.div`
  width: max(20vw, 200px);
  height: max(30vw, 300px);

  background: ${({
    color1,
  }) =>
    `linear-gradient(45deg, ${color1}, red)`};

  margin: 3em auto;
  border-radius: 30px;
`;

const GradientBox = ({
  color1,
}) => (
  <GradientBoxStyle
    color1={color1}
  />
);

export default GradientBox;

Output

But now if we still try to change the color of the gradient box by choosing color from color picker nothing will happen.

Because we still haven't added the color-changing functionality. We didn't tell ours react app what will happen if someone changes the color of the color picker.

Now let's discuss what we need to do to add this functionality.

We need to keep listening for changes in the color input.
We need to get the value of the current color the user is on.

Let's tackle the first problem

We are going to use the onChange property to keep listening for any change in the ColorInput.

const ColorInput = ({
  colorInputChangeHandler
 }) => (
  <ColorInputStyle
    type="color"
    onChange={(e) => colorInputChangeHandler(e)}
  />
);
export default ColorInput;

colorInputChangeHandler as the name itself suggests is going to tell ours react app what will happen if we change the color of the input. We are passing these functions as a prop. And also we need the current color the user is on therefore I am passing e, which will contain all the information related to ColorInput.

Now let's create this function and pass this function to the ColorInput component

  const colorInputChangeHandler = (e) => {
    const color = e.target.value;
    setGradientValues({
      ...gradientValues,
      color1: color
    })
  };

Here I am storing the value of the current color to the color variable and updating the state with the value of the new color that the user selected.

"...gradientValue" is a spread operator if you don't know about it let me give you a brief intro to it.

...gradientValue will get all the previous values stored in the gravientValue. Then we can update whatever value we want without changing the object.

Consider this example

gradientValue = {
    color1: "color 1 value",
    color2: "color 2 value"
}

// without using spread operator
setGradientValue({
    color1: "color 1 change value"
})

console.log(gradientValue)
// output
/*
  gradientValue = {
        color1: "color 1 change value"
}

property color 2 is gone.
setGradientValue set { color1: "color 1 change value" } this object to the gradientValue
*/

// using spread operator
setGradientValue({
    ...gradientValue
    color1: "color 1 change value"
})

console.log(gradientValue)
// output
/*
  gradientValue = {
        color1: "color 1 change value",
        color2: "color 2 value"
}

Right now gradientValue contains only one value so you will not notice the difference but later we are going to add more property to it.

When you load the page the starting color in the gradient box is #bb00ff but the starting color in the color input is black. We need to fix that. This problem can be easily fixed by setting the value property of the color input to the current color of the gradient box.

Pass the current value of the color to the ColorInput

<div className="gradient_container_main_color_box">
          <ColorInput
            colorValue={gradientValues.color1}
            colorInputChangeHandler={(e) => colorInputChangeHandler(e)}
          />

and in the ColorInput

const ColorInput = ({ 
  colorValue, 
  colorInputChangeHandler }) => (
  <ColorInputStyle
    type="color"
    value={colorValue}
    onChange={(e) => colorInputChangeHandler(e)}
  />
);

Now when you load the page you will get

Now with the same logic let's add functionality to other color input

First let's create the variable to store the current color value

  const [gradientValues, setGradientValues] = useState({
    color1: "#bb00ff",
    color2: "#00ffee",
  });

Pass all this value to the second ColorInput

//Second color input
          <ColorInput
            colorValue={gradientValues.color2}
            colorInputChangeHandler={(e) => colorInputChangeHandler(e)}
          />

and also pass this value to the GradientBox

          <GradientBox
            color1={gradientValues.color1}
            color2={gradientValues.color2}
          />

and in the GradientBox

import React from "react";
import styled from "styled-components";

const GradientBoxStyle = styled.div`
  width: max(20vw, 200px);
  height: max(30vw, 300px);
  background: ${({
    color1,
    color2,
  }) =>
    `linear-gradient(45deg, ${color1}, ${color2})`};
  margin: 3em auto;
  border-radius: 30px;
`;

const GradientBox = ({
  color1,
  color2,
}) => (
  <GradientBoxStyle
    color1={color1}
    color2={color2}
  />
);

export default GradientBox;

Output

But there is a problem. Go on and try to change the color of the gradient box by changing the color of the second color input.

On changing the value of the second color input, the value of the first color input changes.

Because no matter what color input we are changing, we are calling the same function (colorInputChangeHandler) which is only changing the color of the color1.

  const colorInputChangeHandler = (e) => {
    const color = e.target.value;
      setGradientValues({
        ...gradientValues,
        color1: color
      });
  };

There are two ways to solve the above problem

To create a new function and pass that in the second color input
We can use the name property of the input tag in HTML to identify which color input is currently active and change the value of color accordingly

I am going to follow the second approach. I don't want to create another function that performs the same thing. Because later we are going to add functionality to our range input and there are a total of 3 of them and I am not gonna create 3 separate functions for them.

Now let's add the name property to our color input

const ColorInput = ({ colorValue, 
  colorInputChangeHandler, 
  inputName }) => (
  <ColorInputStyle
    type="color"
    value={colorValue}
    name={inputName}
    onChange={(e) => colorInputChangeHandler(e)}
  />
);
export default ColorInput;

Pass the inputName value to our colorInput

<div className="gradient_container_main">
        <div className="gradient_container_main_color_box">
          <ColorInput
            colorValue={gradientValues.color1}
            inputName="color1"
            colorInputChangeHandler={(e) => colorInputChangeHandler(e)}
          />
          <div className="gradient_conatiner_main_color_box_range">
            <RangeInput
            />
          </div>
        </div>
        <div className="gradient_container_main_gradient_box">
          <GradientBox
            color1={gradientValues.color1}
            color2={gradientValues.color2}
          />
        </div>
        <div className="gradient_container_main_color_box">
          <ColorInput
            colorValue={gradientValues.color2}
            inputName="color2"
            colorInputChangeHandler={(e) => colorInputChangeHandler(e)}
          />
          <div className="gradient_conatiner_main_color_box_range">
            <RangeInput
            />
          </div>
        </div>
      </div>

Now using simple if and else statement we can check which color value we need to change.

const colorInputChangeHandler = (e) => {
    const name = e.target.name;
    const color = e.target.value;
    if (name === "color1") {
      setGradientValues({
        ...gradientValues,
        color1: color
      });
    } else if (name === "color2") {
      setGradientValues({
        ...gradientValues,
        color2: color
      });
    }
  };

And finally the work of the color input is done.

Adding functionality to range Input

Its functionality is the same as the Color Input.

Add some variables to keep track of the change made.
Add some props to our range input
Add a function that changes the state.
Pass that variable to the gradient box for changing the background.

Let's discuss these points one by one

What variable do we need?
For changing color 1 percentage, for changing color 2 percent, and for changing the angle of a linear gradient.
Let's add these variables to our state

  const [gradientValues, setGradientValues] = useState({
    angle: 45,
    color1: "#bb00ff",
    color2: "#00ffee",
    color1Percentage: 50,
    color2Percentage: 50
  });

Let's add some props to our range input

const RangeInput = ({
  start,
  end,
  rangeValue,
  rangeName,
  rangeInputChangeHandler
}) => (
  <RangeInputStyle
    type="range"
    min={start}
    max={end}
    value={rangeValue}
    name={rangeName}
    onChange={(e) => rangeInputChangeHandler(e)}
  />
);
export default RangeInput;

start and end will be the minimum and maximum values respectively. For example in color1Percentage start = 0 and end = 100 and in angle start = 0 and end = 360

name is provided to identify which range input is triggered (as we discuss in color input)

when the range is changed rangeInputChangeHandler will be triggered.

Let's add functionality to our range input.

const rangeInputChangeHandler = (e) => {
    const value = e.target.value;
    const name = e.target.name;
    if (name === "angle") {
      setGradientValues({
        ...gradientValues,
        angle: value
      });
    } else if (name === "color1Percentage") {
      setGradientValues({
        ...gradientValues,
        color1Percentage: value
      });
    } else if (name === "color2Percentage") {
      setGradientValues({
        ...gradientValues,
        color2Percentage: value
      });
    }
  };

Pass all the value to range input and gradient box

<GradientContainer>
      <div className="gradient_container_header">
        <h1 className="gradient_container_header_heading">
          Gradient Generator
        </h1>
        <h3 className="gradient_container_header_subheading">
          Generate your gradient
        </h3>
      </div>
      <div className="gradient_container_main">
        <div className="gradient_container_main_color_box">
          <ColorInput
            colorValue={gradientValues.color1}
            inputName="color1"
            colorInputChangeHandler={(e) => colorInputChangeHandler(e)}
          />
          <div className="gradient_conatiner_main_color_box_range">
            <RangeInput
              start={0}
              end={100}
              rangeName="color1Percentage"
              rangeValue={gradientValues.color1Percentage}
              rangeInputChangeHandler={(e) => rangeInputChangeHandler(e)}
            />
          </div>
        </div>
        <div className="gradient_container_main_gradient_box">
          <GradientBox
            color1={gradientValues.color1}
            color2={gradientValues.color2}
            angle={gradientValues.angle}
            color1Percentage={gradientValues.color1Percentage}
            color2Percentage={gradientValues.color2Percentage}
          />
        </div>
        <div className="gradient_container_main_color_box">
          <ColorInput
            colorValue={gradientValues.color2}
            inputName="color2"
            colorInputChangeHandler={(e) => colorInputChangeHandler(e)}
          />
          <div className="gradient_conatiner_main_color_box_range">
            <RangeInput
              start={0}
              end={100}
              rangeName="color2Percentage"
              rangeValue={gradientValues.color2Percentage}
              rangeInputChangeHandler={(e) => rangeInputChangeHandler(e)}
            />
          </div>
        </div>
      </div>
      <div className="gradient_container_footer">
        <h3>In Deg</h3>
        <RangeInput
          start={0}
          end={360}
          rangeValue={gradientValues.angle}
          rangeName="angle"
          rangeInputChangeHandler={(e) => rangeInputChangeHandler(e)}
        />
        <h3 className="gradient_container_footer_text">
          Code for the gradient that you have generated
        </h3>
        <h1 className="gradient_container_footer_code">
          Code will go here
        </h1>
      </div>
    </GradientContainer>

Use this value inside the GradientBox

import React from "react";
import styled from "styled-components";

const GradientBoxStyle = styled.div`
  width: max(20vw, 200px);
  height: max(30vw, 300px);
  background: ${({
    angle,
    color1,
    color2,
    color1Percentage,
    color2Percentage
  }) =>
    `linear-gradient(${angle}deg, ${color1} ${color1Percentage}%, ${color2} ${color2Percentage}%)`};
  margin: 3em auto;
  border-radius: 30px;
`;

const GradientBox = ({
  color1,
  color2,
  angle,
  color1Percentage,
  color2Percentage
}) => (
  <GradientBoxStyle
    color1={color1}
    color2={color2}
    angle={angle}
    color1Percentage={color1Percentage}
    color2Percentage={color2Percentage}
  />
);

export default GradientBox;

Finally display the linear gradient code

Using all the variable we created in the useState we can easily generate the code

        <h1 className="gradient_container_footer_code">
          linear-gradient({gradientValues.angle}deg, {gradientValues.color1}{" "}
          {gradientValues.color1Percentage}%, {gradientValues.color2}{" "}
          {gradientValues.color2Percentage}%);
        </h1>

as the value changes the state will be updated.

and that's it. We got our linear gradient generator.

Quick Sort!!. DSA - #1

Anubhav Shukla — Tue, 14 Jun 2022 05:24:29 +0000

Quick Sort

Like Merge sort, Quick Sort uses a divide and conquer algorithm. It picks a pivot point and divides the whole array around that point. After dividing the whole array around that point we will have two parts of the array the left and the right part. Now we have to repeat the whole process for both halves i.e pick the pivot point and divide the whole array around that point. Repeating these steps will lead to a point where the array will contain only one element and that is our base case i.e when the length of the array became 1 we simply return the array.

How to find Pivot Index.

A pivot number is defined as the number whose left side is the smaller and right side is greater.

For example in arr = [2, 1, 3, 6, 4] 3 is pivot point. Because all the elements before 3 are smaller than 3 and all the numbers after 3 are greater.

To divide the array around the pivot point we need to find the pivot index i.e index of the pivot point.

For example if arr = [2, 1, 3, 6, 4]. Here pivot number = 3 and it's index = 2. After dividing the array around 3 arr_left = [2, 1, 3] and arr_right = [6, 4]

In this algorithm, we need to select a number and make it a pivot point i.e we need to put it in its right position. We can select any number we want, but for simplicity, I am going to choose the 1st element i.e element at index 0.

def pivot(arr: list) -> int:
    pivot_count, length = 0, len(arr)
    for i in range(1, length):
        if arr[0] > arr[i]:
            pivot_count += 1
            arr[i], arr[pivot_count] = arr[pivot_count], arr[i]
    arr[0], arr[pivot_count] = arr[pivot_count], arr[0]
    return pivot_count

In above code pivot_count returns the pivot index.

Logic

How to put the selected number in the right place. Suppose we have arr = [4, 8, 2, 1, 5, 7, 6, 3]. Let's choose 4 as our number. 4 will be in its right place if all the element left to 4 is smaller and all the elements right to 4 is greater. Therefore the length of the left side of 4 = total number which is smaller than 4 and hence the index of 4 i.e pivot_index = total number which is smaller than 4 (we didn't add 1 because the index start from 0).

Therefore final array will become arr = [3, 2, 1, 4, 8, 5, 7, 6]

Dry Run

Let's dry run the above code to understand it much better.

Let arr = [4, 8, 2, 1, 5, 7, 6, 3]

Pivot_count = 0, length = 8
Beginning of Loop. Our pivot number is 4 (as I mentioned above I am going to choose the first element). We don't want to compare 4 with 4 i.e arr[0] with arr[0] that's why I am starting loop from index 1.
First iteration: 4 > 8 ---> false.

pivot_count = 0

Second iteration: 4 > 2 ---> true. Therefore we increment the pivot_count and now we are ready to swap. Notice I am incrementing pivot_count before swapping. This is because I want to swap with the number which is the first largest number than 4. Now the arr = [4, 2, 8, 1, 5, 7, 6, 3]

pivot_count = 1

Third iteration: 4 > 1 ---> true. Therefore we increment the pivot_count and swap the two number.

pivot_count = 2 arr = [4, 2, 1, 8, 5, 7, 6, 3]

Fourth iteration: 4 > 5 ---> false.

pivot_count = 2 arr = [4, 2, 1, 8, 5, 7, 6, 3]

Fourth iteration: 4 > 7 ---> false.

pivot_count = 2 arr = [4, 2, 1, 8, 5, 7, 6, 3]

Fourth iteration: 4 > 6 ---> false.

pivot_count = 2 arr = [4, 2, 1, 8, 5, 7, 6, 3]

Third iteration: 4 > 3 ---> true. Therefore we increment the pivot_count and swap the two number.

pivot_count = 3 arr = [4, 2, 1, 3, 5, 7, 6, 8]

Now the loop will break and we put the 4 at index = pivout_count

arr = [3, 2, 1, 4, 5, 7, 6, 8]

Implementing Quick sort

What we need to do

Take the first element of the array and make it pivot i.e place it in the right position. Now we have one element sorted. We divide the pivot about this point and find the pivot in the left and right half respectively. We will continue this process until the length of an array became 1.

def quick_sort(arr: list) -> list:
    length = len(arr)
    if length <= 1:
        return arr
    mid = pivot(arr)
    return quick_sort(arr[:mid + 1]) + quick_sort(arr[mid + 1:])

Let's dry run the program to understand it much better.

Let arr = [4, 8, 2, 1, 5, 7, 6, 3]

We will return the arr if the length of arr <= 1. This will be our base case

‏‏‎ ‎

1 ---> arr = [4, 8, 2, 1, 5, 7, 6, 3]

mid = 3 arr = [3, 2, 1, 4, 5, 7, 6, 8]

quick_sort([3, 2, 1, 4]) + quick_sort([5, 7, 6, 8])

‏‏‎ ‎

1->2 ---> arr = [3, 2, 1, 4]

mid = 2 arr = [1, 2, 3, 4]

quick_sort([1, 2, 3]) + quick_sort([4])

‏‏‎ ‎

1->2->3 ---> arr = [1, 2, 3]

mid = 0 arr = [1, 2, 3]

quick_sort([1]) + quick_sort([2, 3])

‏‏‎ ‎

1->2->3->4 ---> arr = [1]

returns [1]

‏‏‎ ‎

1->2->3 ---> arr = [1, 2, 3]

mid = 0 arr = [1, 2, 3]

[1] + quick_sort([2, 3])

1->2->3->4 ---> arr = [2, 3]

mid = 0 arr = [2, 3]

quick_sort([2]) + quick_sort([3])

‏‏‎ ‎

1->2->3->4->5 ---> arr = [2]

returns [2]

‏‏‎ ‎

1->2->3->4 ---> arr = [2, 3]

mid = 0 arr = [2, 3]

[2] + quick_sort([3])

‏‏‎ ‎

1->2->3->4->5 ---> arr = [3]

returns [3]

‏‏‎ ‎

1->2->3->4 ---> arr = [2, 3]

mid = 0 arr = [2, 3]

[2] + [3]

1->2->3 ---> arr = [1, 2, 3]

mid = 0 arr = [1, 2, 3]

[1] + [2, 3]

1->2 ---> arr = [3, 2, 1, 4]

mid = 2 arr = [1, 2, 3, 4]

[1, 2, 3] + quick_sort([4])

1->2->3 ---> arr = [4]

returns [4]

‏‏‎ ‎

1->2 ---> arr = [3, 2, 1, 4]

mid = 2 arr = [1, 2, 3, 4]

[1, 2, 3] + [4]

1 ---> arr = [4, 8, 2, 1, 5, 7, 6, 3]

mid = 3 arr = [3, 2, 1, 4, 5, 7, 6, 8]

[1, 2, 3, 4] + quick_sort([5, 7, 6, 8])

‏‏‎ ‎

1->2---> arr = [5, 7, 6, 8]

mid = 0 arr = [5, 7, 6, 8]

quick_sort([5]) + quick_sort([7, 6, 8])

‏‏‎ ‎

1->2->3---> arr = [5]

returs [5]

‏‏‎ ‎

1->2---> arr = [5, 7, 6, 8]

mid = 0 arr = [5, 7, 6, 8]

[5] + quick_sort([7, 6, 8])

1->2->3---> arr = [7, 6, 8]

mid = 1 arr = [6, 7, 8]

quick_sort([6, 7]) + quick_sort([8])

‏‏‎ ‎

1->2->3->4---> arr = [6, 7]

mid = 0 arr = [6, 7]

quick_sort([6]) + quick_sort([7])

‏‏‎ ‎

1->2->3->4->5---> arr = [6]

returns [6]

‏‏‎ ‎

1->2->3->4---> arr = [6, 7]

mid = 0 arr = [6, 7]

[6] + quick_sort([7])

1->2->3->4->5---> arr = [7]

returns [7]

‏‏‎ ‎

1->2->3->4---> arr = [6, 7]

mid = 0 arr = [6, 7]

[6] + [7]

1->2->3---> arr = [7, 6, 8]

mid = 1 arr = [6, 7, 8]

[6, 7] + quick_sort([8])

1->2->3->4---> arr = [8]

returns [8]

‏‏‎ ‎

1->2->3---> arr = [7, 6, 8]

mid = 1 arr = [6, 7, 8]

[6, 7] + [8]

1->2---> arr = [5, 7, 6, 8]

mid = 0 arr = [5, 7, 6, 8]

[5] + [6, 7, 8]

‏‏‎ ‎

1 ---> arr = [4, 8, 2, 1, 5, 7, 6, 3]

mid = 3 arr = [3, 2, 1, 4, 5, 7, 6, 8]

[1, 2, 3, 4] + [5, 6, 7, 8]

final ans = [1, 2, 3, 4, 5, 6, 7, 8]

Final code

def pivot(arr: list) -> int:
    pivot_count, length = 0, len(arr)
    for i in range(1, length):
        if arr[0] > arr[i]:
            pivot_count += 1
            arr[i], arr[pivot_count] = arr[pivot_count], arr[i]
    arr[0], arr[pivot_count] = arr[pivot_count], arr[0]
    return pivot_count


def quick_sort(arr: list) -> list:
    length = len(arr)
    if length <= 1:
        return arr
    mid = pivot(arr)
    return quick_sort(arr[:mid + 1]) + quick_sort(arr[mid + 1:])


print(quick_sort([4, 8, 2, 1, 5, 7, 6, 3]))

‏‏‎ ‎