This week we have studied about sorting list by some ways such as Selection Sort, Insertion Sort, and Quick sort. The process of sorting rearranges the order of elements in a sample into a particular set. We compare the four ways of sorting below:
The selection sort takes one element at a time and places the element in the list according to the specific ordering rule. It places each element in its respective order in the list for example,
64 25 12 22 11
11 25 12 22 64
11 12 25 22 64
11 12 22 25 64
11 12 22 25 64
The code in python:
def find_min(L, i):
’’’(list, int) -> int
Return the index of the smallest item in L[i:].
’’’
smallest_index = i
for j in range(i + 1, len(L)):
if L[j] < L[smallest_index]:
smallest_index = j
return smallest_index
def selection_sort(L):
’’’(list) -> NoneType
Sort the elements of L in non-descending order.
’’’
for i in range(len(L) - 1):
smallest_index = find_min(L, i)
L[smallest_index], L[i] = L[i], L[smallest_index]
The insertion sort is similar to the selection sort in the sense that it takes one element at a time and put it in the list. However, the insertion sort maintains a sublist, which is an incomplete list, at the beginning of the list. Each new element is then inserted into the sublist by comparing it with the elements already in the sublist according to the ordering rule. For example:
Sort the list : 12 3 6 2 1
12 3 6 2 1
3 12 6 2 1
3 6 12 2 1
2 3 6 12 1
1 2 3 6 12
Code in python:
def insert(L, i):
’’’(list, int) -> NoneType
Move L[i] to where it belongs in L[:i].
’’’
v = L[i]
while i > 0 and L[i - 1] > v:
L[i] = L[i - 1]
i -= 1 L[i] = v
def insertion_sort(L):
’’’(list) -> NoneType
Sort the elements of L in non-descending order.
’’’
for i in range(1, len(L)):
insert(L, i)
The quicksort is the fastest method in sorting elements into a list because it has a lower amount of comparisons. This method arranges the elements by finding a mean and sorting the elements as bigger or smaller than the mean. Then we take each section of the list and find another mean to compare the elements to. We do so until the list is fully arranged.
The Mergesort divides all elements into groups of two. It can orders each group according to the ordering rule. Then, it compare two groups by comparing the first element in each group and placing it in a new merged group. It does so until the elements have been merged into one group.
Code:
def merge(list1, list2):
lst = []
i=0
j=0
while i < len(list1) and j < len(list2):
if list1[i] < list2[j]:
lst.append(list1[i])
i=i+1
else:
lst.append(list2[j])
j=j+1
lst.extend(list1[i:])
lst.extend(list2[j:])
return lst
def mergesort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = lst[:mid]
right = lst[mid:]
left_s = mergesort(left)
right_s = mergesort(right)
return merge(left_s, right_s)
