Archive

Posts Tagged ‘Quick Sort’

Python: Sorting Algorithm (1.Quick Sort)

May 23, 2021 8 comments

Learning : SQL, Python, sqlite, DataBase
Subject: Testing the SQL Join commands using Python.

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.
Bubble Sort.
Merge Sort.
Insertion Sort.
Selection Sort.
Heap Sort.
Radix Sort.
Bucket Sort.

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.

Quick Sort Steps of Quick Sorting Algorithm are:
1 – Save the first element of the list as pivot. We will call it as pv .
2 – Define Two variables i and j. We will call them as fc, lc fc will be 0 (first element position in the list) and lc will be the length of the list.(last element position in the list) .
3 – Increment fc until the number in the list in fc position is smaller or equal to pv (the first element).
4 – Decrement lc until the number in the list in lc position smaller than pv.

until list[j] < pivot then stop.
5 – If fc less than lc then we swap the two elements in the location of fc and lc. (SWAP list[fc] and list[lc]).

7 – Exchange the pivot element with list[j] element.

Coding First we will write a sort Menu for the project, we will have tree items to select from, Quick Sort Algorithm – Fast Run and Quick Sort Algorithm – Step By Step This will show sorting details.

 # Main Menu

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



And this is the main code body that will call the menu and check the user selection ..

 # The Main application Body

while True:
    
    user_select = main_menu()

    if user_select == '1' :
        user_list = create_list()
        
        fpos = 0  # first position index
        lpos = len(user_list)-1  # last position index
        
        original_list = user_list 
        print('\n   The original List is: ',original_list)

        user_sorted_list = quick_sort(user_list,fpos,lpos)
        
        print('\n   DONE .. We Finish Sorting .. ')
        print('   The Sorted List is: > ',user_sorted_list)
        input('\n   ...Press any key to continue.  ')
    
    if user_select == '2' :
        user_list = create_list()
        
        print('\n   We will show the Quick Sorting Step By Step... \n')
        fpos = 0  # first position index
        lpos = len(user_list)-1  # last position index
        original_list = user_list

        print('\n   The Original List is: ',original_list)
        user_list = quick_sort_details(user_list,fpos,lpos)
        
        print('\n   DONE .. We Finish Sorting .. ')
        print('   The Sorted List is: > ',user_list)
        input('\n   ...Press any key to continue.  ')

    if user_select == '9' :
        break



Also we will have a Function to take the List of Elements from the user, the user input will be as a string, we will convert it to an integer List and will return it back.. Here is the code ..

 # Create the List

def create_list():
    print('\n   Enter the List Elements separated by SPACE, when Finish just Press Enter.')
    the_list = input('\n   Start Entering the Numbers in the List. >  ')
    
    # Convert user input to List
    the_list = the_list.split()        
    
    # Convert str list to int list  
    the_list = [int(each) for each in the_list]

    return the_list



Now let’s write the Quick_sort function, then we will duplicaet it and add some print statements to show sorting steps. So first the code for Quick Sort Algorithm – Fast Run. Here is the code ..

Screen shot of the Quick Sort Algorithm – Fast Run.
python project code Quick Sort Algorithm ali radwani



Running this Function will return the sorted list and display it on the screen, I thought it will be nice if we show the sorting process Step by Step, so I copy the same Function with adding some print-statement in-between .. here is the code and the run-output..

Screen shot of the Quick Sort Algorithm – Detail Run.
python project code Quick Sort Algorithm ali radwani



End of Sorting Algorithm (1.Quick Sort)

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



Follow me on Twitter..

By: Ali Radwani