Sorting

Sorting:

  • Selection Sort
    • Finding minimum element from unsorted part and putting at beginning
    • Algo maintain two subarray
      • One which is sorted and
      • Other remaining which are not sorted
    • Complexity O(n2)
  • Bubble Sort
    • Repeatedly swapping adjacent elements if they are in wrong order
    • Complexity O(n2)
  • Insertion Sort
    • Putting element at correct location
    • Done as we do with playing card
    • Complexity O(n2)
  • Merge Sort
    • Divide And Conquer approach
    • Divide in two halfs then merge them in sortd manner
    • Complexity : O(nLogn)
    • Inversion Count
      • How far array is sorted
      • For sorted it zero for reverse order is maximum
  • Heap Sort
    • Comparison based algo on binary heap DS
    • Find the maximum at place at end
    • Binary Heap
      • Complete Binary tree (All nodes except leaf are completely filled as left as)
      • Parent value should be greater or smaller than children (Max/Min Heap)
    • Array Representation : If Parent at I then Left : 2I+1, Right: 2I+2
    • Decreasing order
      • Build Max Heap Tree
      • Largest at top , replace if with last item of heap
      • Reduce size and repeat till heap have 1 size
    • Increasing order have to build Min Tree
    • In place algorithm
    • Time Complexity : O(nLogn)
    • Usage: k largest ele, sorting nearly sorted array
  • Quick Sort
    • Pick an element as pivot and divide around that
    • Ways to pick pivot
      • First ele
      • Last ele
      • Random ele
      • Median ele
    • Time Complexity : O(nLogn)
    • Single Linked list
      • Choose pivot as tail ele
      • If node have value greater than add it to tail
    • Double Linked List
      • Choose last ele as pivot
      • Element smaller that put before pivot
      • Element greater than put after pivot
    • Quicksort over Mergesort because it don’t use O(N) space extra it is in place
    • Can be reduced auxiliary space to O(LogN)
  • Counting Sort
    • Sort elements in array when array have value in range
    • Place element in on index of array and counter as value
    • Time Complexity O(n+k) when value of ele are in range of 1<k
    • No efficient if data is significant greater than elements to be sorted
  • Radix Sort
    • Only used to sort numbers
    • Do Sorting digit by digit from least significant digit to most significant
    • Counting sort is used as subroutine
    • Do following for each digit from least to most
      • Use counting to order
    • 10=>100=>1000 so on
  • Bucket Sort
    • Useful when input uniformly distributed over range
    • Example
      • Sorting float point numbers 0 to 1
        • Create n buckets
        • Insert arr[i] into bucket[n*arr[i]]=arr[i]
        • Sort individual bucket using insertion sort
      • Sorting negative no from -1 to 1
        • Use two array one for -ve no and other for +ve no
        • Sort -ve in descending order and +ve in increasing order
  • Shell Sort
    • Compare element far than adjacent similar to insertion sort
    • Find gap n/2, then move to right one by one and Reduce gap to 1
  • Comb Sort
    • Improvement in bubble sort
    • Use cap n/1.3 O(n){a} O(n^2) {w} | space O(1)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: