## Python Sorting Algorithm – Heap Sorting -P1

**Learning : Python, Math, Algorithm **

** Subject: Sorting Algorithm, Heap Sort**

[

NOTE:To keep the code as simple as we can,We WILL NOT ADDany user input Varevecations. Assuming that our user will Enter the right inputs.]

Once I start preparing and writing the code for Heap Sorting I fond that I can’t jump to the Heap Sorting without some introductions, So in this post we will cover the Array, Binary Tree, Binary Array, Max-Heap, how to know if a given Array is in Max-Heap or not, Add node to a Max-Heap and Delete a node from a Max-heap. For all this, we will have two or three posts to cover what i think we must know.

So First:

**Binary Tree:** A Binary Tree is a set of Nodes and each Node may have a Maximum of TWO Childs, called Left-Child and Right-Child. Going down to the next level, each of the Child’s (the left one and the right one) again may have TWO Child’s (Left and Right) .. and so on. The last level were there is no more child’s that level is the Leaves. Here are some sample of Binary Tree’s..

All the above are Binary Tree’s, But we will talk about Three Definitions for a Binary Trees:

Full Binary Tree, Complete Binary Tree, Perfect Binary Tree

**Full Binary Tree:**

A Tree is a __Full Binary Tree__ in which Every/All Nodes Except Leaf Nodes(last level) have __ Zero or Two__ Children.

**Complete Binary Tree:**

A Binary Tree called a {__complete binary tree__} in which All/Each levels are completely filled __except__ possibly the last level has all keys as left as possible

__Practical example of Complete Binary Tree is Binary Heap.__

**Perfect Binary Tree:**

A Binary Tree is {__a Perfect Binary Tree__} IF all the internal nodes have Two children **and** all leaf nodes are at the same level.

NOTE: Every Full Binary Tree is A Complete.

FULL BINARY TREE | FULL BINARY TRTEE |

COMPLETE BINARY TREE | COMPLETE BINARY TREE |

PERFECT BINARY TREE | PERFECT BINARY TREE Figure 1 |

**Binary Tree And Array:** To convert a binary tree into array or to present a Binary Tree as an Array we need to consider the following :

1. To Taking all the elements in the Binary Tree.

2. To Keeping the relations between the nodes, who is the parent and what are the childerns for each parents [Left child and Right child].

**1. Taking all the elements in the Binary Tree:**

So for a given tree as __Figure 1:[in above example] __, we can see that (A) is the First Element [Root] (First Parent) and has 2 childs (B) (Left Child) & (C) (Right Child), –> Then Element (B) as parent has Two childs (D) (Left Child) & (E) (Right Child), –> Then Element (C) as parent has Two Childs (F) (Left Child) & (G) (Right Child) .. this is the end of the tree, leaves level.

Now, IF we want to present this Tree as an Array we will start with (A) in index 0, then will write all the elements level by level, from Left to Right. So we will have the array **a1** as follow:

** a1 = [A,B,C,D,E,F,G]**

**2. Keeping the relations between the Nodes:** Using the Method of filling the Array as in point One (above) we Save the relations between the Parents and Childs. For a given Array **a1 = [A,B,C,D,E,F,G]** we can user three formulas to know the Parent and the Childs of any given Node as following:

Assuming we are at index (x) then:

1. Left Child Index of Node (x) : 2 * x + 1

2. Right Child Index of Node (x) : 2 * x + 2

3. Parent Index of Node (x) : x//2 (absolute value of the division)

So, if we refer to a1 Array and (Figure-1), and say we want to know the childrens of node (A), Node (A) is in index [0] so:

The Left child index of Node (A) is : 2 * 0 + 1 = 0 + 1 = 1, the Element in index 1 in the Array a1[1] = B.

The Right child index of Node (A) is : 2 * 0 + 2 = 0 + 2 = 2, the Element in index 2 in the Array a1[2] = C.

The Left child index of Node (C) is : 2 * 2 + 1 = 4 + 1 = 5, the Element in index 5 in the Array a1[5] = F.

The Right child index of Node (C) is : 2 * 2 + 2 = 4 + 2 = 6, the Element in index 6 in the Array a1[6] = (G).

The Parent of Node (E) will be: 4//2 = 2, so the parent of the Element (E) is a1[2] = (B)

**Heap Tree:** Is a Binary Essentially an almost Complete Tree. So a **Heap Tree is**: Tree with All/Each levels are completely Filled except possibly the last level has all keys as left as possible. In Heap The Nodes represents as Integer Numbers.

**Max-Heap:** In Max-Heap Tree the Child Node is Smaller than his Parent.

**Mini-Heap:** In Mini-Heap Tree the Child Node is Larger than his Parent.

We will stop here in this part and will start doing some coding in Python Sorting Algorithm – Heap Sorting – P2.

..:: Have Fun with Coding ::.. 🙂

To Download my Python code (.py) files

Click-Here

By: Ali Radwani

## Another sketch challenge: A Fish

This week sketch challenge **@1hour1sketch** on Twitter is to Draw a **A Fish** so here is my sketch using pencil then black Pen and some watercolor, it takes around 30min [off and on]. More Sketches on my Sketch page ..

you may Follow me on Twitter **@h_ta3kees**

Here is my sketch..

## Python: Sorting Algorithm. 7- Radix Sorting

**Learning : Python Coding, Math, Algorithm **

** Subject: Python Code to Applying Radix Sorting Algorithm **

[

NOTE:To keep the code as simple as we can,We WILL NOT ADDany user input Varevecations. Assuming that our user will Enter the right inputs.]

**Sorting Algorithm** is a way to sort a given list/Array of numbers, there are several sorting Algorithm as follow:

**Type of Sorting Algorithm**

1. Quick Sort. [**Click to Read the Post.**]

2. Bubble Sort. [**Click to Read the Post.**]

3. Merge Sort. [**Click to Read the Post.**]

4. Insertion Sort. [Click to Read the Post.]

5. Selection Sort. [Click to Read the Post.]

6. Heap Sort. [Click to Read the Post.]

7. Radix Sort. [Click to Read the Post.]

8. Bucket Sort. [Click to Read the Post.]

Here in this post we will write a function to take a given list/Array and sort it then pass it back. We assume the user will enter a serial of numbers, that he want to sort, our function will sort it using Radix Sorting Algorithm and print out the original Array and the sorted one.

**Radix Sort Algorithm**: In Radix Sort, we will apply coming Steps:

1. Get the Maximum Number of Digits in the Array. [length of Maximum Number]

2. Add Zeros [0] to the Left of Each Number so All Numbers in the Array will be Same Lenght.

3. Sort the Array Based on The Most Right Digit [digit index] =[-i]. This was Iteration 1.

4. Repeat Step 3, and for each Iteration We Sort based on [digit index] = [-iteration].

5. If [digit index] = 0, Thats mean we did sort until Most left Digit in the Numbers. Then we Stop the Loop.

6. Return the Array.

Coding: In our Radix Sorting Application we will have several Functions to help us completing our task. First let’s see the functions:

Main-menu: To Show the Main Menu of the Application.

header: Just a Decoration Function to Print the Header of the Application.

digits_equalizer: To Add Zeros to the Left of Each Number in the Array.

create_list: Let the User to Enter the Array.

radix_sort: Applying Radix Sorting Algorithm in a Fast-Run

radix_sort_details: Applying Radix Sorting Algorithm Step-by-Step.

Just to be a short artical, i will not go thought Functions like the def main_menu() , def create_list() and def header().

So, let’s start with digits_equalizer() Function, in Radix Sorting we start comparing all numbers based on it’s digites and sorting cording that, but if a number has three digits and another one has two, then we may face an error [index out of range], so first we will convert the array to a string and will add zero.. Here is the code..

This Function will return two arguments, the Array after adding zeros and the maximum digits.

Now, we will write the function of Radix Sorting (Fast-Run) the details function will be a copy with some print-statement.

So here is the code..

# Radix Sort Fast-Run Function def radix_sort() : arr = create_list() temp_arr = [] # Convert to srting and Add Zeros to left side of each number in the array. arr,max_d = digits_equalizer(arr) # Loop for all digits of numbers. for d in range (1,max_d+1): # Loop for sort numbers 0 to 9. for sn in range (0,10): # Check each right digits of each number. for each in arr: if each[-d] == str(sn): temp_arr.append(each) arr = temp_arr temp_arr = [] return(arr)

End of this Post..

All Code as .py file format is available in Download Page.

..:: Have Fun with Coding ::.. 🙂

To Download my Python code (.py) files

Click-Here

By: Ali Radwani

## Python: Kadane’s Algorithm

**Learning : Python, Algorithm, Math **

** Subject: Implement the Kadane’s Algorithm**

**Definition:** Kadane’s Algorithm is to search in a one Dimensional Array [integer positive and negative numbers] for a we will largest Sum of contiguous subarray.

[

NOTE:To keep the code as simple as we can,We WILL NOT ADDany user input Varevecations. Assuming that our user will Enter the right inputs.]

**Algorithm** To find the largest subset sum, we apply coming step:

We will use two variables:

current_max: to hold the max sum of thesub-set

start_again: will be as a flag to re-set the current_max

__ Algorithm: __

1. Start from Element in the array index = 1, save it as start_again. Set Current_max to Array Element in index = 0.

2. Do sumation of start_again with the next element index + 1.

3. If current_max < start_again then re-set current_manx = start_again

4. If start_again < 0 then re-set start_again = 0

5. Repeat from 2 to 4 until the end of the array.

6. If we reach end of the Array, then return the current_max

More from Kadane’s Algorithm:

The aim of Kadane’s Algorithm is to return the Maximum sum of sub-set. But in our code here we will return the following:

1. Maximum sum of largest subset

2. The start Index and the End Index of the subset.

3. printing out the subset.

We will have three options in our application, as following:

1. Kadane’s Algorithm – Fast Run.

2. Kadane’s Algorithm – Step By Step.

9. Exit.

As we are doing in our Algorithms coding, we will use a Main-Menu, and a Function to help the user to enter the Array.

**Coding**

We will start with def create_array(): and will return the Array that the user will enter. here is the code..

Now, here is the code for the Main-Menu and the Main application body. In Main application body code, we will use the while True : loop and calling the main_menu() function then with if statement we will check on the user_selection

The Main-Menu |

Here is the Main Application body code.. |

Last, we will write the Function to get the Kadane’s Sum in a Fast-Run, the details one will be a copy with mode print-out statement to show the steps .. __[All code is in Download Page.]__

As we mentioned, Our Kadane’s function will return three things, the Grates Sum of a sub-set, and to position of that sub-set as start index and end index. Here is the code ..

Here is a Run-Time screen .. |

We done with another Algorithm, looking forwards to solve new one in coming days.

..:: Have Fun with Coding ::.. 🙂

To Download my Python code (.py) files

Click-Here

By: Ali Radwani

## Another sketch challenge: Black Cheetah

This week sketch challenge **@1hour1sketch** on Twitter is to Draw a **Black Cheetah** so here is my sketch using pencil then black Pen, it takes around 50min [off and on]. More Sketches on my Sketch page ..

you may Follow me on Twitter **@h_ta3kees**

Here is my sketch..

## Python: Sorting Algorithm.- 4-Selection

**Learning : Python coding, Math, Algorithm, **

** Subject: Writing Selection Sorting Algorithm in Python**

NOTE:To keep the code as simple as we can,We WILL NOT ADDany user input Varevecations. Assuming that our user will Enter the right inputs.]

**Sorting Algorithm** is a way to sort a given list/Array of numbers, there are several sorting Algorithm as follow:

**Type of Sorting Algorithm**

1. Quick Sort. [**Click to Read the Post.**]

2. Bubble Sort. [**Click to Read the Post.**]

3. Merge Sort. [**Click to Read the Post.**]

4. Insertion Sort. [Click to Read the Post.]

5. Selection Sort. [Click to Read the Post.]

6. Heap Sort. [Click to Read the Post.]

7. Radix Sort. [Click to Read the Post.]

8. Bucket Sort. [Click to Read the Post.]

Here in this post we will write a function to take a given list and sort it then pass it back. We assume the user will enter a serial of numbers, that he want to sort, our function will sort it using Selection Sorting Algorithm and print out the original numbers and the sorted one.

Selection Sort Algorithm: In Selection Sort, we will apply coming Steps:

1. Select the Element (e) in Index i = 0.

2. Find the Smallest Element in the Array from Index i Until index = length of Array.

3. SWAP the Smallest number in the Array with the Element (e) in index i=0.

4. Select the Element (e) in index i = i+1.

5. Repeat the Algorithm from step 2, until i+1 > length of the Array.

In our Application we will have three Functions, one to collect the Array numbers from the user. [*This is the main function in all our sort applications*] here is the code

We are calling this Function within the Main Selection Sort Function.

Now we will write the Selection Sort Function .

# Selection Sorting Function def selection_sort(arr): for i in range (0,len(arr)): e = arr[i] s_ind = i for j in range (i,len(arr)): if arr[j] < e : e = arr[j] s_ind = j arr[i], arr[s_ind] = arr[s_ind], arr[i] return arr

We will have a copy of same Function with some print-statement to show the iterations and elements in each steps. Here is the code ..

Here is screen shot of only three iteration of the Algorithm run-time.. |

We Done !! .. Another coding for Sorting Algorithms, New one will be published in coming days..

… Have fun with Coding … 🙂

To Download my Python code (.py) files

Click-Here

By: Ali Radwani

## Python: Sort Algorithm – 3 – Insertion Sort

**Learning : Python coding, Math, Algorithm, **

** Subject: Writing Merge Sorting Algorithm in Python**

NOTE:To keep the code as simple as we can,We WILL NOT ADDany user input Varevecations. Assuming that our user will Enter the right inputs.]

**Sorting Algorithm** is a way to sort a given list/Array of numbers, there are several sorting Algorithm as follow:

**Type of Sorting Algorithm**

1. Quick Sort. [**Click Here**]

2. Bubble Sort. [**Click Here**]

3. Merge Sort. [**Click Here**]

4. Insertion Sort. [Click Here]

5. Selection Sort. [Click Here]

6. Heap Sort. [Click Here]

7. Radix Sort. [Click Here]

8. Bucket Sort. [Click Here]

Here in this post we will write a function to take a given list and sort it then pass it back. We assume the user will enter a serial of numbers, that he want to sort, our function will sort it and print out the original numbers and the sorted one.

**Insertion Sort:** Steps of Insertion Sorting Algorithm are:

1. Start with index (x = 1), Compare the Element (k) in index [x] with the Element in index [x-1].

1.1 If Element in [x-1] SMALLER than Element in [x] we swap the two elements.

1.2 Once we Swap we will have new index for k , and again we will compare the (k) in (new index) with element before it (new index -1), and keep moving it to left until we stop at index [0] or we face an Element GRATER than k.

2. If the Element k GRATER than the element before it, we left k and take the Next Element (to be k) and start comparing K [in x index] with Element in [x-1] index.

3. We do this until k will be in index (length on the list)

Now starting with the codes, as our standard we follow in **Sorting Algorithm Applications** we will have a Main-Menu and three Items the user will chose among them, and Function to let the user to enter the Numbers [The List or the Array] to be sorted. The Options in the Main-Menu are :

1. Insertion Sort Algorithm – Fast Run.

2. Insertion Sort Algorithm – Step By Step.

9. Exit.

The Fasr-Run we call the create_list(): Function first so the user will Enter the Numbers in the Array, then the Fast-Run will show the sorted Array on the screen.

In the Step-By-Step (Option 2 in the Menu) again calling create_list(): Function first, after the user Enters the Array, we will print-out on the screen each steps of selecting the index, and index-1, the k values and when/if we will SWAP or not.

The last option in the Menu is to Exit the Application (option 9).

Now we start coding.. Here is the Main-Menu.

# Main-Menu def main_menu (): os.system('clear') print('\n\n',' '*5,'******************************') print(' '*5,' ***',' Sorting Algorithm ',' '*1,'***') print(' '*5,' ***',' Insertion Sort ',' '*1,'***') print(' '*5,' ***',' '*22,'***') print(' '*5,' ******************************\n\n') print(' '*7,'1. Insertion Sort Algorithm - Fast Run.') print(' '*7,'2. Insertion Sort Algorithm - Step By Step.') print(' '*7,'9. Exit.') user_choice = input('\n Select your choice. > ') return user_choice

Here is the codes for create_list(): to collect the Array from the user..

Finaly, here is the code for the Step-by-Step running for the Insetion Sort Algorithm. It is the same copy of the Fast-Run but with some print statements to show what is happening.

We Done another coding for Sorting Algorithms, another one will be published in coming days..

… Have fun with Coding … 🙂

To Download my Python code (.py) files

Click-Here

By: Ali Radwani

## Project: Knapsack Problem

**Learning : Python, Math, Algorithm **

** Subject: Solving Knapsack Problem using Python **

NOTE:To keep the code as simple as we can,We WILL NOT ADDany user input Varevecations. Assuming that our user will Enter the right inputs.]

**Definition:** The knapsack problem is a Problem in Combinatorial Optimization: Given a set of Items, Each with a Weight and a Value or Profit, We need to Determine the Number of Each Item to Include in a Collection so that the Total Weight is Less than or Equal to a Given Limit and the Total Value is as Large as Possible. **Source: Wikipedia**

In this post we will write three Functions, The Main Menu, one to Collect the data and another to solve the problem. So first, let’s see the Main-Menu ..

# Main Menu of the Project def main_menu (): os.system('clear') print('\n',' '*5,'******************************') print(' '*5,' ***',' Knapsack Problem',' '*1,'***') print(' '*5,' ***',' '*22,'***') print(' '*5,' ******************************') print('\n',' '*5,"==========[ Main Menu ]==========") print(' '*5,' 1. About Knapsack Problem.') print(' '*5,' 2. Collect the Items.') print(' '*5,' 3. Solve the Problem.') print(' '*5,' 9. Exit.') user_choice = input("\n Select from the Menu: > ") return user_choice

Above Menu will display three option that the user can select from:

1. About Knapsack Problem. [To give simple information about what is Knapsack Problem]

2. Collect the Items. [Will ask the user to Enter the Items and their coresponding Weights and Profits.]

3. Solve the Problem. [The user will Enter the Weight limit we have then we will Solve the problem]

Now we will write the Function to collect the Data from the user we will call it def collect_items(): the user will Enter the Item Name, the Weight and the Value or Profit and will save it in a list, then will return it as item_list. Here is the code and run-time screen.

**A**fter Collecting the Items, the user can select Number (3) from the Menu to Solve the Knapsack Problem. First we will ask user to Enter the Weights Limit we have, then calculating the Profit over Weight for each Items. In Knapsack we select the Items based on the Max w/p for each and store the indexs in a list, and with each selection we must not exceed the weight limits. Here is the code.. ..

So from the above example, we can achieve the Maximum Profit with weight limits to 50Kg if we take Full Amount of Item a, and Full Amount of Item b and 0.666666666 (0.67) amount of Item c.

1 * 60 = 60

1 * 100 = 100

0.67 * 120 = 80

60 + 100 + 80 = 240

NOTE: The Weight in Knapsack Problem can be weight in kg, or Number/Amount of the item (60 bags, 100 bags ..) or any Unit.

Have fun and do some coding .. 🙂

To Download my Python code (.py) files

Click-Here

By: Ali Radwani

## Python: Sorting Algorithm (3. Merge Sort)

**Learning : Python coding, Math, Algorithm, **

** Subject: Writing Merge Sorting Algorithm in Python**

NOTE:To keep the code as simple as we can,We WILL NOT ADDany user input Varevecations. Assuming that our user will Enter the right inputs.]

**Sorting Algorithm** is a way to sort a given list/Array of numbers, there are several sorting Algorithm as follow:

**Type of Sorting Algorithm**

1. Quick Sort. [**Click Here**]

2. Bubble Sort. [Click Here]

3. Merge Sort. [Click Here]

4. Insertion Sort. [Click Here]

5. Selection Sort. [Click Here]

6. Heap Sort. [Click Here]

7. Radix Sort. [Click Here]

8. Bucket Sort. [Click Here]

Here in this post we will write a function to take a given list and sort it then pass it back. We assume the user will enter a serial of numbers, that he want to sort, our function will sort it and print out the original numbers and the sorted one.

**Merge Sort:** Steps of Merge Sorting Algorithm are:

1. If the Array has 1 Element then return it.

2. If the givin Array has more than 1 Element then we Divide it into 2 Parts.

Left = from Element 0 T0 Element len(arr)//2

and Right = from Element len(arr)//2 To Element len(arr). And we keep repeating step 2 for each part.

3. Once we have All parts divided we tart merge them in a sorted order.

**Coding:** In this Post we will write the Function for Main-Mnu, another one to collect the Array [Not Sorted] Elements from the user, then we will write the Main Function, here we will have One to Divide the Array into parts and One to Merge the Element together again. And as we done with Quick & Bubble Sort projects we will have one Fast-Run Function and another one with Details Step-By-Step run to show the Algorithm.

__ NOTE: __ All the Code will be Available in the Download Page.

Let’s start with the Main-menu to list down three option were the user will select one among them, the menu options are: 1. Merge Sort Algorithm – Fast Run. & 2. Merge Sort Algorithm – Step By Step and the last one is 3. Exit.

Here is the code.

I will Not post the code for collecting the Array Element from the user [Find it in the .py file for this project]. Here is the code for merge_sort_divider Function, it takes two arguments the Array and the user_selection, so if the user selection is 2 (2. Merge Sort Algorithm – Step By Step) We will print-out the Dividing Steps and some other Text. [We are using If Statement to print-out Text lines]. Here is the Code ..

Now for **merging function**, for merging function we will have two copies, one as Fast-Run and another for Details to print-out the running Steps, this will make the Fast-Run Function short and easy to follow-up. So, here is the Fast-Run Function code for merge the two part of array returned from the merge_sort_divider. Here is the Code ..

Run time screen .. |

End of Merge Sorting Algorithm.

To Download my Python code (.py) files

Click-Here

By: Ali Radwani

## Python: Sorting Algoritm – Bubble Sort

**Learning : Python, Math, Algorithm **

** Subject: Sorting Algoritm – Bubble Sort**

NOTE:To keep the code as simple as we can,We WILL NOT ADDany user input Varevecations. Assuming that our user will Enter the right inputs.]

Sorting Algorithm is a way to sort a given list of numbers, there are several sorting Algorithm as follow:

**Type of Sorting Algorithm**

Quick Sort. [**Click to Read**]

Bubble Sort.

Merge Sort. [Commeing Soon]

Insertion Sort. [Commeing Soon]

Selection Sort. [Commeing Soon]

Heap Sort. [Commeing Soon]

Radix Sort. [Commeing Soon]

Bucket Sort. [Commeing Soon]

Here in this post we will write a function to take a given list and sort it then pass it back. We assume the user will enter a serial of numbers, that he want to sort, our function will sort it and print out the original numbers and the sorted one.

**Bubble Sort:** Steps of Bubble Sorting Algorithm are:

1. We will select the First Number (Current number) in the list and Compare it with the next number in the list. (Compare list[0] and list[1])

2. If the Next Number in the list IS SMALLER than Current Number SWAP the Two, then compare the Current with the third number and so on.

2.2 If the Next Number in the list IS NOT SMALLER than Current Number, Then we LEFT the Current Number in it’s Position and will Set the Next number as the Current. And will start Comparing Again as Step 2 until the last number in the list.

3. When we reach the end of the list and we perform a SWAP, then we start again with First Element as STEP 1.

4. If we reach the end of the list __Without any SWAP__ being made, then the list is ordered and the algorithm can stop.

**Coding** Starting with the Main Menu Function and a Function to ask the

User to enter the numbers in the list, here are those two Functions.

And here is the Main code that will call the Menu and trigger the Functions based on the User selecting.

Also we have the Function that will ask the user to Enter the Numbers for the List or Array to be sort.__All the code will be Available as a .py file__ in the **Download Page [Click Here]**

Now let’s see the code for **Bubble Sorting Algorithm**, we will have two version of the code, one for __Fast-Run__ that takes the list and return it back as Sorted, and another one will be to show the __Details Step By Step__ of applying the Algorithm. Both Functions are the same but the details one will have several **print** statements to show the steps, here I am posting the Fast-Run version.

Run Screen.. |

End of Bubble Sort Algorithm, hope you enjoy it.

.. Have Fun With Coding ..

To Download my Python code (.py) files

Click-Here

By: Ali Radwani