Sorting algorithms.
Sorting Algorithms:
Lets say we have pack of cards that are to be sorted.
Bubble sort:
Compare first with the second, choose the smaller and swap them. Then compare the second one with the third and so on. Once a iteration is done, repeat the steps again. Repeat the iterations till you have not done even a single swap in the last iteration.
Time complexity:
Worst case: O(n2)
Base case: O(n)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: Yes
Java implementation:
Selection sort:
Find out the smallest number in the given set of cards, you do this by taking the first card, compare it with the next set of the cards one by one, if you find a smaller card than the current card, you swap the smaller one on to your hand and continue with the comparison, once the list is exhausted. The card in your hand is the smallest, place it at the start of the list. Then continue to find the smallest in the next set. Once you do this for the entire list, the list would be in sorted order.
Worst case: O(n2)
Base case: O(n2)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: No (however with a with increased space complexity can be done)
Java implementation:
Insertion sort:
Insertion sort is like adding new card to an already ordered set of cards at hand.
You pick a key element which is the new number that you have picked up, then you go through the already arranged elements and compare them with key, if any number is greater than key, you move it to one place up, and once you dont find any number greater than key with in the current list, you insert the key at that place.
Worst case: O(n2)
Best case: O(n)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: yes
Javascript implementation:
Shell sort:
Its hard to explain shell sort. Basically you choose some gaps and then pick numbers with in that gap and sort/swap them. And repeat this process till the start end. You can find the video explaining this
Another better one.
The time complexity of the shell sort depends on the gap you have choosen. For
sequence (2 pow k − 1) complexity is (N pow 3/2)
successive numbers of the form (2 pow p) or (3 pow q)) complexity is (N((logN)pow 2)) - ex: 1, 2, 3, 4, 6, 8, 9, 12
Best case: O(n)
Space complexity: Inplace O(1)
IsStable: no
Java implementation:
Quick sort:
Pick a pivot card, and partition the numbers into to numbers less than pivot card, numbers greater than pivot card. This can be done by comparing the
You then repeat this process on the left and right hand side partitions by choosing another pivot with in them. The process continues till you cant select a pivot.
Time complexity:
Worst case: O(n2) (happens when the elements are already sorted in the opposite order, to avoid this we generally choose a randomized pivot)
Best case: nlogn
Average: nlogn
Space complexity: log n
IsStable: depends ??
Java implementation:
Merge sort:
Divide cards into two sublists of about half the size. Sort each sublist recursively. Till the list is of length 0 or 1, then it is already sorted. Merge the sublists back into one sorted list.
Time complexity:
Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: n
IsStable: yes
Java implementation:
Heap sort: Create a heap structure and then keep reading the min of the heap. Once the min is picked, keep deleting the min element. That would return the sorted list. This cannot be demonstrated using the cards.
Time complexity:
Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: 1
IsStable: No
Java implementation:
Binary sort: Construct a binary tree and do a inorder traversal to print the sorted sequence.
Radix sort:
Lsd radix sort, sort the numbers based on their least significat bits and repeat this process with each more significant bit.
Example:
Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1st place) gives:
170, 90, 802, 2, 24, 45, 75, 66
Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.
Sorting by next digit (10s place) gives:
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
Note the sorting the last digits etc takes O(n) time only as we can use bucket sort.
Time complexity:
Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: 1
IsStable: No
Java implementation:
Bucket sort: Place each card in a buckets which are alread in sorted order, and then retrieve them as per the sort order of the buckets.
Time complexity:
Worst case: O(n+r) (r is the range of numbers to be sorted - basically number of buckets)
Best case: O(n+r)
Average:O(n+r)
Space complexity: O(n+r)
IsStable: Yes
Java implementation:
Count sort:
Lets say we have pack of cards that are to be sorted.
Bubble sort:
Compare first with the second, choose the smaller and swap them. Then compare the second one with the third and so on. Once a iteration is done, repeat the steps again. Repeat the iterations till you have not done even a single swap in the last iteration.
Time complexity:
Worst case: O(n2)
Base case: O(n)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: Yes
Java implementation:
Selection sort:
Find out the smallest number in the given set of cards, you do this by taking the first card, compare it with the next set of the cards one by one, if you find a smaller card than the current card, you swap the smaller one on to your hand and continue with the comparison, once the list is exhausted. The card in your hand is the smallest, place it at the start of the list. Then continue to find the smallest in the next set. Once you do this for the entire list, the list would be in sorted order.
Worst case: O(n2)
Base case: O(n2)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: No (however with a with increased space complexity can be done)
Java implementation:
Insertion sort:
Insertion sort is like adding new card to an already ordered set of cards at hand.
You pick a key element which is the new number that you have picked up, then you go through the already arranged elements and compare them with key, if any number is greater than key, you move it to one place up, and once you dont find any number greater than key with in the current list, you insert the key at that place.
Worst case: O(n2)
Best case: O(n)
Average: O(n2)
Space complexity: Inplace O(1)
IsStable: yes
Javascript implementation:
function insertionsort() {
var a = [].slice.call(arguments);
var l = a.length;
for (i = 1; i < l; i++) {
k = i - 1;
key = a[i]; // hold the current value of key in key.
// check if the numbers which are sorted till now are greater than key, if you find any, move them one level up and insert the key there.
while ((k > = 0) &&(a[k] > key)) {
a[k + 1] = a[k];
k--;
}
a[k + 1] = key;
}
console.log(a);
}
Shell sort:
Its hard to explain shell sort. Basically you choose some gaps and then pick numbers with in that gap and sort/swap them. And repeat this process till the start end. You can find the video explaining this
Another better one.
The time complexity of the shell sort depends on the gap you have choosen. For
sequence (2 pow k − 1) complexity is (N pow 3/2)
successive numbers of the form (2 pow p) or (3 pow q)) complexity is (N((logN)pow 2)) - ex: 1, 2, 3, 4, 6, 8, 9, 12
Best case: O(n)
Space complexity: Inplace O(1)
IsStable: no
Java implementation:
Quick sort:
Pick a pivot card, and partition the numbers into to numbers less than pivot card, numbers greater than pivot card. This can be done by comparing the
You then repeat this process on the left and right hand side partitions by choosing another pivot with in them. The process continues till you cant select a pivot.
Time complexity:
Worst case: O(n2) (happens when the elements are already sorted in the opposite order, to avoid this we generally choose a randomized pivot)
Best case: nlogn
Average: nlogn
Space complexity: log n
IsStable: depends ??
Java implementation:
public static class QuickSort{
public void sort(int[] a, int left, int right){
int p;
if(left < right){
p = partition(a, left,right);
sort(a,left,p);
sort(a,p+1,right);
}
}
public int partition(int[] a, int left, int right){
int pivot = a[right];
int i=left;
int j= right;
int temp;
while(true){
while(a[i]<pivot){
i++;
}
while(a[j]>pivot){
j--;
}
if(i<=j){
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
else{
return j;
}
}
}
}
Divide cards into two sublists of about half the size. Sort each sublist recursively. Till the list is of length 0 or 1, then it is already sorted. Merge the sublists back into one sorted list.
Time complexity:
Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: n
IsStable: yes
Java implementation:
Heap sort: Create a heap structure and then keep reading the min of the heap. Once the min is picked, keep deleting the min element. That would return the sorted list. This cannot be demonstrated using the cards.
Time complexity:
Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: 1
IsStable: No
Java implementation:
Binary sort: Construct a binary tree and do a inorder traversal to print the sorted sequence.
Non Comparison sorts:
These sorts are done where in we are dealing only with number esp of some range. Hence better performance then nlogn is possible.Radix sort:
Lsd radix sort, sort the numbers based on their least significat bits and repeat this process with each more significant bit.
Example:
Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1st place) gives:
170, 90, 802, 2, 24, 45, 75, 66
Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.
Sorting by next digit (10s place) gives:
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
Note the sorting the last digits etc takes O(n) time only as we can use bucket sort.
Time complexity:
Worst case: O(n log n )
Best case: O(n log n )
Average: O(n log n )
Space complexity: 1
IsStable: No
Java implementation:
Bucket sort: Place each card in a buckets which are alread in sorted order, and then retrieve them as per the sort order of the buckets.
Time complexity:
Worst case: O(n+r) (r is the range of numbers to be sorted - basically number of buckets)
Best case: O(n+r)
Average:O(n+r)
Space complexity: O(n+r)
IsStable: Yes
Java implementation:
Count sort:
Asymptotic analysis: logn < n < n2 (n - square) <n3... < 2 to the power of n. big O notation. n2+2n+3n+logn = O(n2) ADT - Stack (with arrays) Stack implementation in Javascript. - Queue (with arrays / linked lists ) - Dqueue (with linked lists) - Dqueue can be used to implement stacks and queues - Circular lists with a sentinel is a efficient way to implement stacks / queues.?(this is interesting to implement) - Vector (ranks) - Position - List (based on positions) - Sequence (rank + positions) - Dictionary - Hash tables - Binary trees - Redblack trees - Avl trees - B-trees Binary Search: First sort and then divide and conquer the same to search O(log n base 2) Hash function: Hash codemap - key -> integer Hash compression map - integer -> [0, N-1] stack - creation tight strategy - (add constant) - f(N) = N+c - O(n2) growth strategy - (double up) - f(N) = 2N - O(n)
