# # Sorting a list

# ## Swapping

Examine the function defined below, and **run the code to define the function. **

#

# ##### Need help in the Questions:

# * What is the name of the function?

# * How many parameters does it have?

# In[ ]:

# Swaps two elements in the list named items

# at positions i and j.

def swap(items,i,j):

temp = items[i]

items[i] = items[j]

items[j] = temp

# Before running the code below, **predict the output**. Then run the code and see if you were correct.

# In[ ]:

myList = [5, 10, 15, 20, 25, 30]

swap(myList, 1, 4)

print(myList)

# Now **modify the above code** to swap the first and last elements of myList.

# ## Bubble sort

We now define a `bubbleSort` function that does an in-place sort of the list called `items`.

There is no need to return a new list, because the function actually changes the original list.

**Run the code to define the function.** There will not be any output.

# In[ ]:

def bubbleSort(items):

fullySorted = False

while not fullySorted: #outer loop

print(items)

i = len(items) - 1 #len() gets length, start at end of list

fullySorted = True

while i > 0: #inner loop, stop at top of list

if items[i] < items[i-1]: #if two neighbouring items out of order

swap(items,i,i-1) #use our swap function to swap them

fullySorted = False #list may not yet be sorted

i = i - 1 #decrement i

# #### Testing bubble sort

# If you want to see some output, you need to call the function, and pass in an argument to be used as the list `items`.

#**Run the code below** to call the function.

# In[ ]:

otherList = [395,2,-4,20,47,200,-50,-12] #a list for testing

print('Before sorting:', otherList)

bubbleSort(otherList)

print('After sorting:', otherList)

Help for the Below questions:-

# * What are the contents of `otherList` after a single iteration of the outer loop of `bubbleSort`?

# * How many iterations of the outer loop happen when sorting `otherList`?

#* Then run both blocks of code (the def block and the test block) again.

#* Examine the output to answer the question about iterations.

#(New Part) Now create a new list below, with 8 elements, called `yourList` -- a list where you think you can get `bubbleSort` to stop early (do fewer iterations). How many times did the outer loop run for `yourList`?

# In[ ]:

yourList = [] #fill in this list with 8 elements separated by commas

print('Before sorting:', yourList)

bubbleSort(yourList)

print('After sorting:', yourList)

# ## Selection sort

# Recall selection sort from class. You will write your own version of the selection sort function.

#Remember, we already defined a `swap` function at the beginning of the notebook.

#Below is another function you will need for selection sort, called `minIndexAfter`.

#This function returns the index of the minimum element in `items` between `startPos` and the end of the list.

#**Run the code** to define the function.

# In[ ]:

def minIndexAfter(items, startPos):

minIndex = startPos

i = startPos + 1

while(i < len(items)):

if(items[i] < items[minIndex]):

minIndex = i

i = i + 1

return minIndex

# Define a function called `selectionSort` below. In the body of the function, you will need to call the `swap` function and the `minIndexAfter` function.

# In[ ]:

#define selectionSort here:

# Use the following code to test your `selectionSort` function.

# In[ ]:

items = [395,2,-4,20,47,200,-50,-12]

selectionSort(items)

print(items)