CS - SORTING/SEARCHING ALGORITHMS

 

SORTING ALGORITHMS

                     SORTING ALGORITHM PDF LINK

#Bubble Sort

       ·       The outer loop iterates through the entire array.

·       The inner loop compares adjacent elements and swaps them if they are out of order.

·       The outer loop runs n times, and each pass moves the largest element to its correct position.

arr=[3,8,5,2,1]

n = len(arr)

print(n)

for i in range(n):  #traverse through all the elements

        # Last i elements are already sorted, no need to check them

        for j in range(0, n-i-1):

             # Swap if the element found is greater than the next element

             if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]        

print(arr)

SELECTION SORT ALGORITHM EXPLANATION

num=[64,25,12,22,11]

print(num)

for i in range(len(num)):

        # Find the minimum element in the remaining unsorted array

        mini = i

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

                if num[j] < num[mini]:  

                    mini = j

        # Swap the found minimum element with the first element of the unsorted part

        num[i], num[mini] = num[mini], num[i]

print(num)

REFER PDF FOR DRY RUN :SORTING ALGORITHM PDF LINK

#INSERTION SORT

list1=[]

n=int(input("enter no of elements"))  

i=0

while i<n:

    list1+=[int(input("enter element"))]  

    i+=1

for i in range(1,n):

    temp=list1[i]  

    j=i-1  

    while temp<list1[j] and j>=0:

        list1[j+1]=list1[j]  

        j-=1

        list1[j+1]=temp

print(list1)

#SEARCHING ALGORITHM

#Linear / Sequential Search

list = [2, 4, 7, 10, 13, 17, 20, 24, 27, 31]

element=4

found=0

for i in range(len(list)):

    if list[i]==element:

        print("found at index :",i)

        found=1

        break

if not found:

    print("Element not found")

    

#BINARY SEARCH

n=[10,20,30,40,50,60,70]

target=60

beg=0

low=len(n)-1

while beg<=low:

    mid=(beg+low)//2

    if n[mid]==target:

        print("element found:",mid)

        break

    elif n[mid]<target:

        beg=mid+1

    else:

        low=mid-1

else:

    print("target not found")