# 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

- Sorting float point numbers 0 to 1

- 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