What is a sorting problem ? 


By simply, a sorting algorithm is an algorithm that solves a problem related to sorting, for example in the input we'll put a sequence containing n objects((a0,a1,..,aN)(string, integer, float, bool..)) with the possibility of sorting them using a relation of order , in the output we'll get an arrangement of the input sequence such as : a0<=a1<=..<=aN. To achieve this we have different soring algorithms. 

 Why sorting is important in computer science ? 

  • we need often to sort information (grades, names, pictures..)
  • sorting algorithms form an important part of many programmes
  • the diversity of sorting algorithms makes them ideal for teaching algorithmic thinking 

To simplify we'll look at sorting algorithms applied to a list of numbers in python.


1- Selection sort : 

The idea is to take a value with the index i from the list, then find the minimum value in the remaining list with the index k , then swapping the values and repeating this process until getting a sorted list.

code in python : 
def selection_sort(l):
    for i in range(len(l)-1) :
        k = i
        for j in range(i+1,len(l)):
            if l[j] <= l[k] :
                k = j
        l[i],l[k] = l[k],l[i]
    return l

2- Bubble sort : 

The idea is to loop over the list and swap elements two by two according to the biggest value, at the end we'll have the maximum value at the end, but the rest is still not sorted, we'll repeat the same process for the entire list except the last element, and again we'll have the maximum value at end, we'll keep doing those iterations until the list is sorted. this is a great video explaining it in two minutes :

code in python : 
def bubble_sort(l) :
    for i in range(len(l)-1,0,-1) :
        for j in range(i) :
            if l[j] > l[j+1] :
                l[j],l[j+1] = l[j+1],l[j]
    return l


3 - Insertion sort : 

The idea is the compare each item with the items on it's left, starting from the beginning of the list, and then swapping elements according to the biggest value, this is a great video explaining it in two minutes : Insertion sort in 2 minutes - YouTube

code in python : 
def insertion_sort(l) :
    for i in range(1,len(l)) :
        j = i
        while j > 0 and l[j-1] > l[j] :
            l[j-1],l[j] = l[j],l[j-1]
            j = j - 1
    return l

4- Merge sort : 

the idea is to " divide and conquer ", well begin by splitting the list into two nearly equal lists, and do same for the two sub-list until we're left with a list containing just two element and finally grouping all the lists in the correct order, this is a good video explaining this in 3 minutes : 

code in python : 

def merge(l1,l2) :
    if l1 == [] : return l2
    if l2 == [] : return l1
    if l1[0] < l2[0] :
        return [l1[0]] + merge(l1[1:],l2)
    else :
        return [l2[0]] + merge(l1,l2[1:])

def merge_sort(l) :
    if len(l) == 1 :
        return l
    else :
        return merge(merge_sort(l[:len(l)//2]),l[len(l)//2:])







to be continued...


Buy Website Traffic