Explore topic-wise InterviewSolutions in .

output of diferent passes Pass One

[12,34,46,-34,90,23], {}

Pass Two

[34, 46, -34, 90, 23} , {12}

Pass Three

LISTS MANIPULATION AND IMPLEMENTATION

[46, -34, 90, 23} , {12, 34} Pass Six

Pass Four {23}, {-34,12, 34, 46, 90}

[-34, 90, 23} , { 12, 34, 46} Pass Seven

Pass Five {} , {-34,12, 23, 34, 46, 90}

{90,23} , {-34,12,34,46} It is the sorted list.

def selection_sort(DATA_LIST):

for i in range(0, len (DATA_LIST)):

min = i

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

if DATA_LIST[j] < DATA_LIST[min]:

min = j

# swapping

temp= DATA_LIST[min]

DATA_LIST[min] = DATA_LIST[i]

DATA_LIST[i]=temp

print DATA_LIST

NAME_LIST = [‘Neena’,’Beeta’,’Reeta’,’Geeta’,’Seeta’]

print “LIST BEFORE SORTING”,NAME_LIST

selection_sort(NAME_LIST)

LIST BEFORE SORTING [‘Neena’,‘Beeta’,‘Reeta’, ‘Geeta’, ‘Seeta’]

[‘Beeta’, ‘Neena’, ‘Reeta’, ‘Geeta’, ‘Seeta’]-Pass 1

[‘Beeta’, ‘Geeta’, ‘Reeta’, ‘Neena’, ‘Seeta’]-Pass 2

[‘Beeta’, ‘Geeta’, ‘Neena’, ‘Reeta’, ‘Seeta’]-Pass 3

[‘Beeta’, ‘Geeta’, ‘Neena’, ‘Reeta’, ‘Seeta’]-Pass 4

[‘Beeta’, ‘Geeta’, ‘Neena’, ‘Reeta’, ‘Seeta’]-Pass 5

def insertion_sort(DATA_LIST):

for K in range (1, len(DATA_LIST)):

temp=DATA_LIST[K] # ptr=K-1,

while(ptr>=0) and DATA_LIST[ptr]>temp:

DATA_LIST[ptr+l]=DATA_LIST[ptr]

ptr=ptr-1

DATA_LIST [ptr+1] =temp

print DATA_LIST

DATA_LIST = [15,-5,20,-10,10]

print “LIST BEFOR SORTING”,DATAJ.IST

insertion_sort(DATA_LIST)

[-5,15, 20, -10,10]

[-5,15,20,-10,10]-Pass 1

[-10,-5,15,20,10]-Pass 2

[-10,-5,10,15, 20]-Pass 3

def selection_sort(DATA_LIST):

for i in range(0, len (DATA_LIST)):

min = i

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

if DATA_LIST[j][2] > DATA_LIST[min][2]:

min = j

# swapping

DATA_LIST[min] [0] ,

DATA_LIST[i] [0] = DATA_LIST[i] [0] ,

DATA_LIST[mm] [0] DATA_LIST[min][l],

DATA_LIST[i][l] = DATA_LI ST [i] [ 1 ],

DATA_LI ST [min] [ 1 ] DATA_LIST[min] [2] ,

DATA_LIST[i] [2] = DATA_LIST[i] [2],

DATA_LIST[min] [2]

print DATA_LIST

maxrange=input(“Enter Number of Students: ”)

Students=[]

for i in range(maxrange):

Details=[]

Details. append(input(“Enter roll_no”))

Details.append(raw_input(“Enter name”))

Details. append(inprft(“Enter marks”))

Students.append(Details)

print Students

selection_sort(Students)

Selection sort performs the following steps:

1. Starting at index 0, search the entire array to find the next smallest or largest value.

2. Swap the smallest or largest value found with the value at index 0.

3. Repeat steps 1 & 2 starting from the next index.

Working:

1. 3rd iteration of selection sort: [1,20,46,78,54,90]

2. 4th iteration of bubble sort: [1, 20, 46, 54, 90, 78]

3. 5th iteration of insertion sort: [1, 20, 46, 54, 78, 90]

def selection_sort(DATA_LIST):

for i in range(0, len (DATA_LIST)):

min = i

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

if DATA_LIST[j] < DATA_LIST[min]:

min = j

# swapping

temp= DATA_LIST[min]

DATA_LIST[min] = DATA_LIST[i]

DATA_LIST [i]=temp

print DATA_LIST

DATA_LIST = [99 78 25 48 51 11]

print “LIST BEFOR SORTING”,DATA_LIST

selection_sort(DATA_LIST)

[79,19, 43, 52, 3, 95]-Pass 1

[19, 43,52,3,79, 95]-Pass 2

[19,43,3, 52, 79, 95]-Pass 3

def binary_search(SORTEDLIST, number):

low=0

high=len(SORTEDLIST)

found=False

while(low<high) and found==False:

mid=(int) (low+high/2)

if SORTEDLIST[mid]==number:

print “Number found at”,mid

found=True

break

elif SORTEDLIST[mid]<number:

low=mid+1

else:

high=mid-1

if low >= high:

print “Number not found”

maxrange = inputfEnter Count of numbers: ”)

numlist = []

for i in range(0, maxrange):

numlist.append(input(“?”))

numlist.sort()

print “Sorted list”,numlist

number = inputfEnter the number”)

binary_search(numlist,number)

from bisect import bisect

def listfunc(sortedlist,number) :

insert_point = bisect (sortedlist, number)

sortedlist.insert(insert_point,number)

print “List after Insertion”

print sortedlist

sortedlist.remove(number)

print “List after Deletion”

print sortedlist

maxrange = inputfEnter Count of numbers: ”)

numlist=[]

flag=False

for i in range(0, maxrange):

numlist.append(input(“ ?”))

numlist.sort()

number = inputfEnter the number”)

listfunc(numlist,number)

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list until no input elements remain. The choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm.

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is also Called a comparison sort.

class CITY:

def_init_(self): self.Ccode = 0

self.CName = self. Pop = 0

self.KM = 0 self.Density = 0

def DenCal (self) :

self.Density = self.Pop/self. KM

def Record (self)

self Ccode=input (“Enter Ccode”)

self.CName=raw_input (“Enter CName”)

self.Pop=input (“Enter population”)

self.KM=input (“Enter KM”)

DenCal(self) //or self.DenCal()

def View (self):

print Ccode, CName, Pop, KM, Density

if self.Density > 10000:

print (“Highly populated city”)

# OR print (“Highly populated city”)

def bubble_sort(DATA_LIST) :

i = 0

j = 0

l = len(DATA_LIST)

for i in range(l):

print “Bubble Sort Iterations – Asc order of Quantity”

for j in range(i+l,l):

if DATA_LlST[i][3] > DATA_LIST[j][3]:

# swapping

DATA_LIST[i][0], DATA_LIST[j] [0]=DATA LIST[j] [0],DATA_LIST[i] [0]

DATA_LIST[i][1], DATA_LIST[j][1]=DATA_ LIST[j][l],DATA_LIST[i][l]

DATA_LIST[i] [2], DATA_LIST[j] [2]=DATA_ LIST[j][2],DATA_LIST[i][2]

DATA_LIST[i][3], DATA_LIST[j][3]=DATA_ LIST[j][3] ,DATA_LIST[i] [3]

print DATA_LIST

def insertion_sort(DATA_LIST):

for K in range (1, len(DATA_LIST)):

temp=DATA_LIST[K][2]

ptr=K-1

print “Insertion Sort Iterations – Desc order of price”

while(ptr>=0) and DATA_LIST[ptr][2] < temp:

DATA_LIST[ptr+1] [0]=DATA_LIST[ptr] [0]

DATAJHST [ptr+1] [1]=DATA_LIST[ptr] [1]

DATA_LIST[ptr+1][2]=DATA_LIST[ptr][2]

DATA_LIST[ptr+1] [3]=DATA_LIST[ptr] [3]

ptr=ptr-1

DATA_LIST[ptr+1][2]=temp

print DATA_LIST

maxrange = input(“Enter Number of Items: “)

Items=[]

for i in range (maxrange):

Details=[]

Details. append(input(“Enter Item Code”))

Details.append(raw_input(“Enter Item name”))

Details.append(float(raw_input(“Enter price”)))

Details.append(input(“Enter Quantity”)) Items. append(Details)

print “BEFORE SORTING”,Items bubble_sort(Items)

insertion_sort(Items)