Searching and Sorting I

Search Problem Definition

Given a list L of length n and an item e, is item e present in L?

  • If it is in L, return its location (index) in L;
  • otherwise return -1 indicating its not in L.

Searching in an Unsorted List

Let's start with a unsorted list first and revisit our linearSearch algorithm.

In [ ]:
def linearSearch(L, e):
    n = len(L)
    for item in L:
        if item == e:
            return True
    return False
In [ ]:
linearSearch([12, 16, 23, 2, 7], 16)
In [ ]:
linearSearch([12, 16, 23, 2, 7], 13)
In [ ]:
linearSearch(['a', 'e', 'i', 'o', 'u'], 'u')
In [ ]:
linearSearch(['a', 'e', 'i', 'o', 'u'], 'a')
In [ ]:
linearSearch(['hello', 'world', 'silly'], 'hi')

Searching in a Sorted List

Can we do better if the given list L is sorted?

Let's implement binary search below.

In [1]:
def binarySearch(L, e):
    """Assume L is sorted.  
    If e in L, return True;
    else return False."""
    n = len(L)
    if n == 0:
        return False
    else:
        m = n//2
        if e == L[m]:
            return True
        elif e < L[m]:
            return binarySearch(L[:m], e)
        else:
            return binarySearch(L[m+1:], e)
In [2]:
binarySearch(['a', 'e', 'i', 'o', 'u'], 'a')
Out[2]:
True
In [3]:
binarySearch(['a', 'e', 'i', 'o', 'u'], 'b')
Out[3]:
False
In [4]:
binarySearch(sorted(['hello', 'world', 'silly']), 'hi')
Out[4]:
False
In [5]:
binarySearch(sorted(['hello', 'world', 'silly']), 'hello')
Out[5]:
True
In [6]:
numList = sorted([23, 1, 2, 90, 0, 10, 12, 120, 45])
binarySearch(numList, 11)
Out[6]:
False
In [7]:
binarySearch(numList,0)
Out[7]:
True
In [8]:
binarySearch(numList, 45)
Out[8]:
True

Sorting Algorithms

There are several algorithms for sorting. Let's explore selection sort first.

Selection Sort

  • Find ith smallest element, put it in the ith position.
In [9]:
def selectionSort(L):
    """Destructive sort of list L, 
    returns sorted list."""
    n = len(L)
    for i in range(n):
        minPosition = i
        for j in range(i+1, n):
            if L[minPosition] > L[j]:
                minPosition = j
        L[i], L[minPosition] = L[minPosition], L[i]
    return L
In [10]:
selectionSort([1, 43, 22, 99, 100])
Out[10]:
[1, 22, 43, 99, 100]
In [11]:
list('shikha')
Out[11]:
['s', 'h', 'i', 'k', 'h', 'a']
In [12]:
selectionSort(list('shikha'))
Out[12]:
['a', 'h', 'h', 'i', 'k', 's']
In [13]:
selectionSort(list('We hate Covid-19'))
Out[13]:
[' ',
 ' ',
 '-',
 '1',
 '9',
 'C',
 'W',
 'a',
 'd',
 'e',
 'e',
 'h',
 'i',
 'o',
 't',
 'v']