Friday, December 21, 2018

Selection Sort

Algorithm:
  • Find smallest element with linear scan
  • Move it to the front
  • Continue until all elements are in place
Time Complexity:
Space Complexity:
  • O(1) - usually no extra space is required 
In-place: yes
Stable: yes

Python Implementation:
def selection_sort(arr):
    n = len(arr)
    for i range(n):
        min_index = i
        for j in range(i+1, n):
            if a[min_index] > a[j]:
                 min_index = j
    a[i], a[min_index] = a[min_index], a[i]

Bubble Sort

Algorithm:
  • Start at the beginning
  • Swap first two element if first is greater than second
  • Continue to next pair
  • Repeat until sorted
Time Complexity:
  • Best: O(n) - when the list is already sorted
  • Worst: O(n2) - when required to reverse the list
Space Complexity:
  • O(1) - usually no extra space is required
In-place: yes
Stable: yes

Python Implementation

def bubble_sort(array):
    n = len(array)
    for j in range(n):
        for i in range(n-1-j):
            if a[i] > a[i+1]:
                a[i+1], a[i] = a[i], a[i+1]

Thursday, December 20, 2018

Stable Sorting Algorithms

A sorting algorithm is called stable sorting algorithms if the order of the original values with same precedence is retained over in the final output.

e.g. a list of names [alex, bob, alice, judy, tom] has the output [alex, alice ,bob, judy, tom]. Here the precedence of alex over alice is retained in the output.

Sorting Algorithm that are stable:
Not stable sorting algorithms:
  • Heap Sort
  • Quick Sort

In Place Algorithm

In place algorithms:
  • focus on space efficiency
  • uses no auxiliary data structures and uses very small extra space
  • have O(1) space complexity (strict definition) to O(log n) space complexity (broad definition)
Side Effects:
  • usually overwrites the original data to create the modified output
  • may need more time in some cases
Examples:
Reversing a sorted list in-place.
a = [1,2,3,4,5]
n = len(a)
temp = 0
for i in range(n/2):
     temp = a[n-1-i]
    a[n-1-i] = a[i]
    a[i] = temp

In-place sorting algorithms: