GE8151 - Unit 4 - Sorting

Illustrative programs for using list, list function and methods. These cards capture the essence of the pre-requisites for understanding sorting algorithm programs. Start with insertion sort, selection sort and then merge sort.

20 flashcards · Programming Languages · by kgashok

1. Write a code snippet that produce a list (named alist) containing all positive integers upto and including 10.

   alist = list(range(1, 11)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Is zero a positive integer? Zero is defined as neither negative nor positive!

2. Write a code snippet for producing all the valid indexes of a list alist = ["dog", "monkey", "man", "flower"]

   indexes = list(range(len(alist)) # indexes = [0, 1, 2, 3]

3. For a list containing 15 numbers, the maximum index value is 14. The minimum index value is 0. True or False?

   True. alist = [11, 22, 33, 44, 55]assert alist[4] == 55# True

4. seasons = ['Spring', 'Summer', 'Fall', 'Winter'] slist = list(enumerate(seasons)) print(slist) What is the output?

   [(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]

5. What is the output of the following code? alist = range(4, 9) print(list(enumerate(alist)))

   [(0, 4), (1, 5), (2, 6), (3, 7), (4, 8)]

6. alist = range(4, 9) blist = list(enumerate(alist))) print(blist) [(0, 4), (1, 5), (2, 6), (3, 7), (4, 8)] Each tuple in the blist has two values: First element is the index ( 0, 1, 2, 3, or 4) Second element is a value (4, 5, 6, 7 or 8) True or False?

   True enumerate returns a tuple containing a count (from start which defaults to 0) and the values obtained from iterating over iterable

7. L = list(range(10))for _ in range(len(L)): print(L) L.pop() What is the output?

   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8] [0, 1, 2, 3, 4, 5, 6, 7] [0, 1, 2, 3, 4, 5, 6] [0, 1, 2, 3, 4, 5] [0, 1, 2, 3, 4] [0, 1, 2, 3] [0, 1, 2] [0, 1] [0]

8. What is the output of the following snippet? alist = [2, 4, 3] alist.pop(2) print("alist = ", alist)

   alist = [2, 4]

9. A alist = [0,1, 2, 3, 4, 5] Write a code snippet using slicing that returns a copy of alist which contains only the positive integers in the list.

   Returns # [1, 2, 3, 4, 5] Zero is the only element that is not positive. So slice code gets all the elements in alist without the 1st element at index 0.

10. A list contains [1, 2, 3, 4, 5, 0] Write a code snippet using slicing that returns a copy of alist which contains only the positive integers in the list.

    Zero is in the last position of the list at index -1. So the above slice returns the desired list.

11. Divide up a list exactly into two equal parts, and return the equal parts as a tuple of two lists . If the list contains odd number of elements, the second part should have the extra element. Write the code snippet for this.

12. What is the output of the following snippet? alist = [2, 4, 3] alist.pop(2) # pop out element at index 2 alist.insert(1, 3) # insert 3 at index 1 print("alist = ", alist)

    alist = [2, 3, 4] lst.insert(index, val) - look up the documentation

13. SHIFT LEFT alist contains [1, 2, 3, 4, 5]. Write a code snippet which helps shift the elements in the list by one place to the left. The first element in the list (i.e. 1) will be overwritten and that is okay. i.e. alist should eventually contain [2, 3, 4, 5, 5]

14. SHIFT RIGHT alist contains [1, 2, 3, 4, 5]. Write the code for shifting elements to the right. The last element in the list (i.e. 5) will be overwritten and that is okay. i.e. alist should eventually contain [1, 1, 2, 3, 4]

15. A list contains elements which are numbers. The code for shifting all elements to the right is as follows: If key contains a value, shift only those elements which are bigger than the key. Write the code snippet for this. for e.g. if key = 3, and alist contains [1, 2, 4, 5, 3], after running the snippet, alist must contain [1, 2, 4, 4, 5]

16. Is it possible to reduce the while block to one single line?

17. Is it possible to make the above snippet more efficient? CLUE: Use Slicing

    Line 53 represents a slicing code which helps move the relevant elements en masse. Trade-off: To get more speed (in this case ~25-30%), you may end up writing more lines of code and using more memory (in this case j).

18. What is the most simplest of sort algorithms write in Python code? InsertionSort SelectionSort MergeSort QuickSort

    InsertionSort

19. The insertionsort code provided can be sligthly optimized. How?

    Since any one element list is already sorted, we only need to handle the rest of the list which is obtained by providing two arguments to enumerate which are: L[1:] and start keyword argument to begin with 1.

20. You are asked to manually use the InsertionSort to sort an unsorted list. The list is [1, 0, 4, -1, 3, 2] Write down the contents of the list during each iteration.

    [0, 1, 4, -1, 3, 2] [0, 1, 4, -1, 3, 2] [-1, 0, 1, 4, 3, 2] [-1, 0, 1, 3, 4, 2] [-1, 0, 1, 2, 3, 4]