Sorting Methods

SortingMethods.md

SELECTION SORT

finds minimum elements and inserts at beginning Least swaps O(n)

for i in range(n):
  t=i
  for j in range(i+1,n):
    if arr[t]>arr[i]:
      t=i
  arr[i],arr[t]=arr[t],arr[i]

Time: O(n^2) Space: O(1) Unstable

BUBBLE SORT

swaps adjacent elements continuously

for i in range(n-1):
  for j in range(n-i-1):
    if arr[j]>arr[j+1]:
      arr[j],arr[j+1]=arr[j+1],arr[j]

Stable Time: O(n^2) Space: O(1) Optimize by breaking if no swaps done

INSERTION SORT

Split array into sorted and unsorted halves

for i in range(1,n):
  t=a[i]
  j=i-1
  while j>=0 and a[j]>t:
    a[j+1]=a[j]
    j-=1
  a[j+1]=t

Time: O(n^2) Space: O(1) Stable, used in almost sorted

MERGE SORT

divide and merge

def merge(a,s,m,e):
    x,y=m-s+1,e-m
    sa,ea=[],[]
    for i in range(x):
        sa.append(a[s+i])
    for i in range(y):
        ea.append(a[m+i+1])
    i1,i2=0,0
    im=s
    while i1<x and i2<y:
        if sa[i1]<=ea[i2]:
            a[im]=sa[i1]
            i1+=1
        else:
            a[im]=ea[i2]
            i2+=1
        im+=1
    while i1<x:
        a[im]=sa[i1]
        i1+=1
        im+=1
    while i2<y:
        a[im]=ea[i2]
        i2+=1
        im+=1
    


def sort(a,s,e):
    if s>=e:
        return
    m=s+(e-s)//2
    sort(a,s,m)
    sort(a,m+1,e)
    merge(a,s,m,e)

Time: O(nlogn) Space: O(n) Stable

QUICK SORT

Like merge sort, but uses a pivot element and partitions around it.

def partition(a,s,e):
    pi=a[e]
    i=s-1
    for j in range(s,e):
        if a[j]<=pi:
            i+=1
            a[i],a[j]=a[j],a[i]
    a[i+1],a[e]=a[e],a[i+1]
    return i+1

def sort(a,s,e):
    if s>=e:
        return
    pivot=partition(a,s,e)
    sort(a,s,pivot-1)
    sort(a,pivot+1,e)

Time: O(nlogn), O(n^2) Space: O(n) Unstable

Counting Sort

Using hashing and frequency

def sort(a):
    n=len(a)
    res=[0 for i in range(n)]
    cnt=[0 for i in range(256)]
    ans=["" for i in a]
    for i in a:
        cnt[ord(i)]+=1
    for i in range(256):
        cnt[i]+=cnt[i-1]
    for i in a:
        res[cnt[ord(i)]-1]=i
        cnt[ord(i)]-=1
    for i in range(n):
        ans[i]=res[i]

Time: O(n+k) Space: O(n+k) Unstable Used in character sorting

BUCKET SORT

Split values to Buckets and sort the Buckets internally into Bucket [n*[array*i]]

def internalInsertionSort(a):
    for i in range(1,len(a)):
        t=a[i]
        j=i-1
        while j>=0 and a[j]>t:
            a[j+1]=a[j]
            j-=1
        a[j+1]=t
    return a
    
def sort(a):
    res=[]
    slots=10
    for i in range(slots):
        res.append([])
    for i in a:
        res[int(slots*i)].append(i)
    for i in range(slots):
        res[i]=internalInsertionSort(res[i])
    i=0
    for j in range(slots):
        for k in range(len(res[i])):
            a[i]=res[j][k]
            i+=1
    return a