Python Sorting

 

Sorting Techniques

 

Sorting is arranging Data in a particular order, either in Ascending or Descending order. Though the Language has inbuilt method Sort or Sorted for it. Let's learn a few Sorting Techniques being followed in most applications and also as a programming practice or concept learning.

 

There are several Sorting Technique available. To name a few

 

]      Bubble Sort

]      Selection Sort

]      Insertion Sort

 

All sorting techniques use LOOP Statements to get the solution. The Number of Loops may vary from technique to technique.

 

Bubble Sort

 

When you pour water into a bucket, we see Air Bubbles are formed at the bottom. These bubbles ,as we pour will start coming up and reach the top of the water. Have you wondered why this happens, it is because as the Air is lighter than Water, the Air bubbles though form at the bottom will come to the Top. Similarly in this technique of sorting, on end of each Iteration, the smallest value comes to the front. We use Nested Loop to achieve this. The technique is , the Elements are compared 1 by 1 and interchanged if not found in order.

 

You start the program with a List of Data of your choice or as given.

 

Program

 

N=[83,25,50,70,14,74,67,90]

print("The Unsorted list is")

print(N)

for i in range(0,len(N)-1):

                for j in range (i+1,len(N)):

 

                                if N[i]>N[j]:

                                                t=N[i]

                                                N[i]=N[j]

                                                N[j]=t

print("The Sorted list is")

print(N)

Output

 

The Unsorted list is

[83, 25, 50, 70, 14, 74, 67, 90]

The Sorted list is

[14, 25, 50, 67, 70, 74, 83, 90]

>>> 

 

In this program we are starting with static Data, if you want try with receiving Data during Runtime from the User, generate it as a List and use it.

 

Selection Sort

 

In this technique the interchange of values happens only once in the Outer Loop iteration. The inner loop checks for the position of the smallest Element in the balance List, so at the end of the Iteration the Smallest Element found is interchanged with the Starting element of the iteration. The Loop gets repeated till all elements fall in place.

 

Program

N=[83,25,50,70,14,74,67,90]

print("The Unsorted list is")

print(N)

for i in range(0,len(N)-1):

                mp=i

                for j in range (i+1,len(N)):

                            if N[mp]>N[j]:

                                       mp=j

                                       if i!=mp:

                                               t=N[mp]

                                               N[mp]=N[i]

                                               N[i]=t

print("The Sorted list is")

print(N)

Output

The Unsorted list is

[83, 25, 50, 70, 14, 74, 67, 90]

The Sorted list is

[14, 25, 50, 67, 70, 74, 83, 90]

>>> 

 

Insertion Sort

This technique assumes like it is working with 2 Lists. One is the unordered input and another empty List into which ordered elements gets added. The technique is an element from the unordered list is taken and compared with the elements in the Ordered one, based on the comparison it is inserted to the Left (if it is small) or to the right (if it is big) of the existing.

 

In our program , we will be using only one list. We start from the 2nd item to the Last assuming the Left side of the second one is another list. From each position the Element is compared with the Elements in the Left side, if the Element is larger than the current one then we interchange them, so that smaller one goes to left and bigger one to the right. This is continued till all elements in unordered list is exhausted.

 

Program

N=[83,25,50,70,14,74,67,90]

print("The Unsorted list is")

print(N)

for i in range(1,len(N)):

                cv=N[i]

                cp=i

                while cp>0 and N[cp-1]>cv:

                                N[cp]=N[cp-1]

                                N[cp-1]=cv

                                cp=cp-1

print("The Sorted list is")

print(N)

 

Output

The Unsorted list is

[83, 25, 50, 70, 14, 74, 67, 90]

The Sorted list is

[14, 25, 50, 67, 70, 74, 83, 90]

 

Search Techniques

 

For any Data Structure Sort and Search are 2 important algorithms required. We already saw few Sorting Techniques. Now let's see some Searching Algorithm. There are several Algorithms available , popular ones are,

 

] Linear Search

] Binary Search

 

Linear Search

 

This Algorithm compares our Data with each and every element from the beginning to the end, till the Data is found. If we reach the end and still the Data is not found means the Search Data is not available in the Sequence.

 

Algorithm

v          Get the element to search

v          Run a For loop from start to end for the List

v          Compare with each element

v          If matched Found break from search

v          If end of list Element not found

 

Here the Search list may or may not be sorted.

 

Program

 

N=[0,5,10,15,20,25,30,35,40,45,50]

m=int(input("Give the Number value to Search for:"))

print("The Search Value is",m)

i=0

for i in range(len(N)):

                if m==N[i]:

                                print("The Element is Found and the Position is ",i)

                                break

                else:

                                i=i+1

if i==len(N):

                print("The Element is not found in the List")

 

Output

Give the Number value to Search for:20

('The Search Value is', 20)

('The Element is Found and the Position is ', 4)

>>>

Give the Number value to Search for:23

('The Search Value is', 23)

The Element is not found in the List

 

Binary Search

This search technique requires the Search List to be sorted, only then it will work.

Algorithm

v          Get the element to search for

v          Find the mid element of the Search List

v          Compare the element in the middle with search element

v          If matching then

         a. Display element found

v          If not check whether the search element is less than mid element

a. If true repeat step 2,3,4 for the list from start to mid(Left side of Mid)

b.Else repeat step 2,3,4 for the list from mid+1 to the last (Right side of Mid)

v          If we are left with no other element to check then

         a. Display Element not found

        

Program

 

N=[0,5,10,15,20,25,30,35,40,45,50]

m=int(input("Give the Number value to Search for:"))

print("The Search Value is",m)

f=0

l=len(N)-1

while f<=1:

                mp=int((f+1)/2)

                if N[mp]==m:

                                print("The Element is Found and the Position is",mp)

                                break

                else:

                                if m<N[mp]:

                                                l=mp-1

                                else:

                                                f=mp+1

if f>1:

                print("The Given element is not found in the List")

 

Output

>>>Give the Number value to Search for:45

('The Search Value is', 45)

The Given element is not found in the List

>>>Give the Number value to Search for:27Give the Number value to Search for:45

('The Search Value is', 45)

The Given element is not found in the List