Δυαδική αναζήτηση και ταξινόμηση

README.md

Δυαδική αναζήτηση

Σε ταξινομημένη λίστα (binsearch.py).

Ταξινόμηση

• Insertion sort (inssort.py)
• Αναδρομικός quick sort (qsort.py)

binsearch.py

# -*- coding: utf-8 -*-

def binsearch(l,i):

	""" search list l for number i,
	return position if found, None otherwise """
	
	# initial search limits
	start = 0	
	end = len(l)-1
	
	while end>=start:
		
		mid = (start+end)//2	# middle position in list
		print start,mid,end
		
		if i==l[mid]: return mid
		
		if i<l[mid]:
			end = mid-1	# use lower half
		else:
			start = mid+1	# i>l[mid], use upper half
		
	# if here, i not found - return None
	

# example sorted list
l = [-11,-7,1,3,5,10,10,12,23]

# search for numbers
print binsearch(l,1)	# will print 2
print binsearch(l,11)	# will print None (not found)

inssort.py

# -*- coding: utf-8 -*-

def insertion_sort(l):
	
	# for all items except 1st, beginning -> end
	for i in range(1,len(l)):

		j = i		
		# move selected item to correct position, towards beginning
		while j>0 and l[j-1]>l[j]:
			
			l[j-1],l[j] = l[j],l[j-1]	# swap l[j] and l[j-1]
			j -= 1
			print l
		
		print
		
# test list
l = [10,3,-7,12,-11,5,10,23,1]
print 'initial',l
print

insertion_sort(l)
print 'final',l

qsort.py

# -*- coding: utf-8 -*-

def quick_sort(l):
	
	if len(l)<=1:	# end of recursion
		print '*',l
		return l
	
	# split list to lower/higher than 1st element parts	
	low,p,high = partition(l)	# low and high are lists
	print low,p,high		# p is a single element
	
	# recurse into sublists then combine results
	newlist = quick_sort(low)+[p]+quick_sort(high)

	print '*',newlist
	return newlist
	
def partition(l):

	""" utility function to split list l into
	lower/higher than 1st element parts """
	
	p,rest = l[0],l[1:]
	low = [x for x in rest if x<=p]
	high = [x for x in rest if x>p]

	return low,p,high
	
			
# test list
l = [2,3,-7,12,-11]
print 'initial',l
nl = quick_sort(l)
print 'final',nl