Python: Sorting Algorithm


আশা করি এই কোড দেখে পাইথনের ডাটাস্ট্রাকচার সর্ম্পকে কিছু ধারনা নেয়া যাবে।

পাইথনের কোড বুঝার আগে মনে রাখার মত কিছু জিনিসঃ 

  • পাইথনে branching এর জন্য কোন কার্লি ব্রাকেট { … } নাই।
  • Branching করতে হয় স্পেস দিয়ে।
  • ৪ টা স্পেস standard.
  • তারমানে এখানে indentation এর ভূমিকা ব্যাপক। 🙂
  • পাইথনে single line কমেন্ট করা হয় # দিয়ে এবং multiple line কমেন্ট করা হয় “”” comment “”” দিয়ে।
  • if condition লিখা হয়  1. if condition: 2. if condition: elif conditoin: else:
  • range একটা ফাংশন যা লুপের রেঞ্জ ঠিক করে দেয় কত থেকে কত পর্যন্ত লুপ ঘুরবে। range(n) মানে লুপ ঘুরবে 0 থেকে n-1 পর্যন্ত। range(x,n) মানে লুপ ঘুরবে x থেকে n-1 পর্যন্ত।
  • for loop লিখা হয়,  1. for i in range(x,y): এখানে লুপ x থেকে y-1 পর্যন্ত ঘুরবে।  2. for i in Li: মানে Li লিস্টের প্রতিটা এলিমেন্ট i হিসেবে থাকবে প্রতি ইটারেশনে।
  • while loop লিখা হয় while condition:
  • function লিখা হয়ঃ def function_name(parameter_list): —-
  • Details about python


1.Bubble Sort:

Complexity:
Best case: O(N)
Average Case:O(N^2)
Worst Case: O(N^2)

def bubble_sort(Li,start,last):
    for i in range(start,last):   #take ith position from start
        for j in range(i+1,last): #start jth position from i+1th position
            if  Li[i] > Li[j] :   #compare ith position with jth position
                Li[i] , Li[j] = Li[j] , Li[i] #if ith position is greater than jth position then swap Li[i] & L[j]
            
if __name__=="__main__":
    L=[2,3,4,1,4,8,4,2,7]
    bubble_sort(L,0,len(L))
    print(L)

2. Insertion Sort:

Complexity:
Best case: O(N)
Average Case: O(N^2)
Worst Case: O(N^2)

def insertion_sort(Li,start,last):
    for i in range(start+1,last): # ith postion start with start+1
        key=Li[i] #insert Li[i] into the sorted sequence Li[0....... last-1]
        j=i-1
        while j>=start and Li[j]>key:
            Li[j+1]=L[j]
            j-=1
            Li[j+1]=key

if __name__=="__main__":
    L=[10,9,8,7,6,5,4,3,2,1]
    insertion_sort(L,0,len(L))
    print(L)

3.Quick Sort:

Complexity:
Best case: O(N log N)
Average Case: O(N log N)
Worst Case: O(N^2)

def Partition(Li,left,right): #partition for divide the list
    pivot=Li[right] #consider last element as pivot
    i=left-1;
    for j in range(left,right): # loop iteration left to right-1
        if Li[j]<=pivot:
            i=i+1
            Li[i],Li[j]=Li[j],Li[i]
    Li[i+1],Li[right]=Li[right],Li[i+1]
    return i+1

def Quick_Sort(Li,left,right):
    if left<right: 
        q=Partition(Li, left, right) #find out the partition point
        Quick_Sort(Li, left, q-1) #solve left sub problem part
        Quick_Sort(Li, q+1, right) #solve right sub problem part

if __name__=="__main__":
    Li=[1,2,3,4,5,67,8,-1,2,99,92,-1000,192,-178]
    Quick_Sort(Li, 0, len(Li)-1)
    print(Li)

4. Merge Sort:

Complexity:
Best case: O(N log N)
Average Case: O(N log N)
Worst Case: O(N log N)

def Merge(Li, left, mid, right): 
    left_Li =(Li[left : mid+1]) #divide left side in left_Li list
    right_Li =(Li[mid+1: right+1]) #divide right side in right_Li list
    left_Li.append(2147483647)
    right_Li.append(2147483647)
    i,j = 0,0
    for k in range(left, right+1): #k loop iterate left to right
        if left_Li[i] <= right_Li[j]: #merge condition
            Li[k] = left_Li[i]
            i += 1
        else:
            Li[k] = right_Li[j]
            j += 1

def Merge_Sort(Li, left, right): 
    if left < right:
        mid = int((left + right) / 2) 
        Merge_Sort(Li, left, mid) #List divide in left sub problem
        Merge_Sort(Li, mid+1, right) #List divide in right sub problem
        Merge(Li, int(left), int(mid), int(right)) #solve the sub problem

if __name__=="__main__":
    Li=[1,2,3,4,5,67,8,-1,2,99,92,-1000,192,-178]
    Merge_Sort(Li, 0, len(Li)-1)
    print(Li)

4. Counting Sort:

Complexity:
Best case: O(N)
Average Case: O(N)
Worst Case: O(N)

def Counting_Sort(Li):
    Max=max(Li) #find out maximum value in the list
    Min=min(Li) #find out minimum value in the list
    freq=[0]*(Max+1) #create new list for count frequency of the value
    for x in Li: #iterate the list
        freq[x]+=1 #count frequency
    sorted_list=[] #create new list for sorted value
    for i in range(Min,Max+1): #iterate minimum to maximum value
        while(freq[i]!=0): #this loop iterate until frequency > 0
            sorted_list.append(i) #insert i in the sorted list if its exist
            freq[i]-=1 #after insertion decrement its frequency
    l=len(Li)
    for i in range(0,l): 
        Li[i]=sorted_list[i] #store the sorted value in main list

if __name__=="__main__":
    li=[1,2,100,2,3,45,6,7,8,4,5,100,2,3,4,6,3,199]
    Counting_Sort(li)
    print(li)

বিদ্রঃ IDE থেকে কোড কপি পেষ্ট করাতে, indentation এ প্রবলেম হতে পারে। তাই কোড রান করানোর সময় error দিলে indentation ঠিক করে নিলেই হবে।

About Tanvir Hasan Anick

I can read and write code, :)
This entry was posted in Python. Bookmark the permalink.

1 Response to Python: Sorting Algorithm

  1. Thanks Bro for this Post.

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s