Selection Sort - using Python

Selection sort is also one of the basic sort algorithms and run in quadratic time O(n^2) same as Insertion sort.  The Selection sort is better than Insertion sort in terms of space complexity but has slower  than insertion sort in terms of time complexity.

Here we do not swap numbers after every comparison; rather we find the smallerst/largest numbers, save it in a temporary variable and replace it with the leftmost element in right array. In result we get sorted array on left hand side.

Explanation

Given an unsorted list the algorithm finds the smallest element and swap it with first element. Then it searches for smallest element in list excluding the 1^st element  and so on till the list got sorted finally.

Below are the differences between Selection sort and Insertion sort 

Implementation

__author__ = 'Dharmjit'
def selection_sort(list):
    for index in range(0, len(list)):
        iSmall = index
        for i in range(index,len(list)):
            if list[iSmall] > list[i]:
                iSmall = i
        list[index], list[iSmall] = list[iSmall], list[index]
    return list

if __name__ == '__main__':
    print(selection_sort([5,2,4,6,1,3,]))

Bubble Sort - using Python

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.


Explanation

Let us take the array of numbers "7 6 5 4 3 2 1", and sort the array from lowest number
to greatest number using bubble sort. In each step, elements written in blue  are being compared.
 six passes will be required.

First Pass: swaps- 6
(7 6 5 4 3 2 1) --> (6 7 5 4 3 2 1)
(6 7 5 4 3 2 1) --> (6 5 7 4 3 2 1)
(6 5 7 4 3 2 1) --> (6 5 4 7 3 2 1)
(6 5 4 7 3 2 1) --> (6 5 4 3 7 2 1)
(6 5 4 3 7 2 1) --> (6 5 4 3 2 7 1)
(6 5 4 3 2 7 1) --> (6 5 4 3 2 1 7)

Second Pass: swaps -5
(6 5 4 3 2 1 7) --> (5 6 4 3 2 1 7)
(5 6 4 3 2 1 7) --> (5 4 6 3 2 1 7)
(5 4 6 3 2 1 7) --> (5 4 3 6 2 1 7)
(5 4 3 6 2 1 7) --> (5 4 3 2 6 1 7)
(5 4 3 2 6 1 7) --> (5 4 3 2 1 6 7)
(5 4 3 2 1 6 7) --> (5 4 3 2 1 6 7)

Third Pass: swaps - 4
(5 4 3 2 1 6 7) --> (4 5 3 2 1 6 7)
(4 5 3 2 1 6 7) --> (4 3 5 2 1 6 7)
(4 3 5 2 1 6 7) --> (4 3 2 5 1 6 7)
(4 3 2 5 1 6 7) --> (4 3 2 1 5 6 7)
(4 3 2 1 5 6 7) --> (4 3 2 1 5 6 7)
(4 3 2 1 5 6 7) --> (4 3 2 1 5 6 7)

Forth Pass: swaps - 3
(4 3 2 1 5 6 7) --> (3 4 2 1 5 6 7)
(3 4 2 1 5 6 7) --> (3 2 4 1 5 6 7)
(3 2 4 1 5 6 7) --> (3 2 1 4 5 6 7)
 (3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)
(3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)
(3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)

fifth pass: swaps - 2
(3 2 1 4 5 6 7) --> (2 3 1 4 5 6 7)
(2 3 1 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)

sixth pass : swaps - 1
(2 1 3 4 5 6 7)--> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
------------------------

__author__ = 'kamal'def bubblesort(alist):
    for numofpass in xrange(0, len(alist)-1):
        for i in xrange(0, len(alist)-1):
            if alist[i] > alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [7, 6, 5, 4, 3, 2, 1]
bubblesort(alist)
print("----O-u-t-p-u-t-----")
print(alist)

Output--

----O-u-t-p-u-t-----
[1, 2, 3, 4, 5, 6, 7]