Archive

Posts Tagged ‘sort’

Python Sorting Algorithm – Heap Sorting -P3


Learning : Python, Math, Algorithm
Subject: Sorting Algorithm, Heap Sort P2

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


First let’s just remember that in Part-1 we wort the Following Functions:

  • Main Menu Function.
  • Entering/Creating the Array.
  • Print-Out or to Display the Array.
  • Sections Header.

In this Part-3 we will cover another Two important Functions that we need to talk about in our mission to understand the Heap Sorting Algorithm.

First Function
Check If The Array is in Max Heap: After the user Giveing/Entering the Array [Selecting Option 1 in the Menu] we need to Examen/Check if it is in a Max-Heap, to do so we will call the Function def check_if_max_heap(arr, inside): the Function will take Two arguments:
arr : The Array.
inside: Boolean Flag showing are we calling the Function from within another Function or Not.

Scope of Work: We will check and compare each Node [starting from last node in the leaves] with it’s Parent using this formula parent_index = ((child_index-1)//2) to get the parent index, then comparing the Values of the Child and Parent, If the Child is GRATER Than his Parent we SWAP them. Then going to the Next Child and so-on until the Root-Node. .. Here is the Code ..

Ali radwani ahradwani.com python code heap sorting algorithm

for each print statement I am using this code if not inside : then print ..
Example: if not inside : print(‘\n The Array is a Max-Heap Array.’)
So if the inside = True then the print code will not work, that’s mean we are calling the Function from inside another function and we just want the return value, the return here will be a boolean True/False as is_max [if the array is in Max-Heap].

Second Function
Convert to Max-Heap: In this Function we will convert a given Array to a Max-Heap Array. The way this Function is working is by checking/Examining all the Childs starting from the Leaves, and if any Child is Grater than his Parent we do a SWAP. After we Finish, we will call the Function def check_if_max_heap(arr, inside): to check if the Array is in Max-Heap, If NOT we will call the convert Function and so-on until we get the is_max = True from the def check_if_max_heap(arr, inside):. Both Functions def check_if_max_heap(arr, inside): and def convert_to_max_heap (arr,inside): will be run in a while loop until def check_if_max_heap(arr, inside): will return True. .. Here is the code for def convert_to_max_heap (arr,inside):

Ali Radwani python code heap sorting algorithm


And here is the while loop to keep Examining the Array until fully converted to a Max-Heap Array.

 # While loop in Option 3 from the Main-Menu, In the main body code..

    while not is_max:
             arr = convert_to_max_heap (arr,True)
             is_max = check_if_max_heap (arr,True)
                



We will stop here in this part. In Part-4 we will Add new Node to the Array, and Delete a Node from the Array.

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

To Download my Python code (.py) files Click-Here



ali radwani ahradwani.com python projects codeFollow me on Twitter..

By: Ali Radwani

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 ADD any 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..

ali radwani ahradwani.com python project code radix sorting algorithm

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



ali radwani ahradwani.com python projects codeFollow me on Twitter..

By: Ali Radwani