Quicksort

Quicksort is a sorting algorithm which applies divide and conquer paradigm. Quicksort has a worst case running time of \( O(n^{2}) \) , however, it has running time of \( O(n​ logn) \) on average which makes quicksort very efficient. Moreover, it works in-place but not stable. The performance of quicksort depends on selecting the pivot, and starting to partition around it. During the partition procedure subarrays divided into four regions; \( \leq x \), \( > x \), \( unrestricted \) ,and finally the \( pivot \).

Selection Sort

Selection sort is an in-place comparison sort algorithm which has \( O(n^2) \) running time complexity in both best and worst case. Even though its logic is similar to insertion sort, it's a very inefficient sorting algorithm. List is both divided into two parts as sorted and unsorted where initially sorted part is empty. Every turn, algorithm finds the minimum (or maximum) key in unsorted sublist then swaps it with the leftmost element of unsorted part. Due to the reason which elements in any place could get swapped selection sort is not stable.

Merge Sort

Merge sort is another comparison based sort algorithm. It closely follows divide-and-conquer paradigm, and provides \( O(n​lgn) \) run time complexity in worst and average cases, however, \( O(n) \) in space complexity. Merge sort can be used for sorting huge data sets that can not fit into memory. It is also a stable sort which preserves the order of equal elements.

Binary Search

Binary search is a searching algorithm which works on a sorted (ascending or descending) array. In each turn, the given key is compared with the key at the middle of the array, if it is equal to it then its index is returned. Otherwise, if the given key is less than key at the middle then binary search continues its operation on left sub-array \( ( A[0..Mid-1] ) \), and similarly on right sub-array \( ( A[mid+1..N-1] ) \) if given key greater than it. If the given key cannot be found then an indication of not found is returned.

Heaps

The binary heap data structure is an array object that represents a nearly complete binary tree. Thus, each element of the array corresponds to a node of the tree. Heaps are useful data structures for heapsort ,and they are underlying data structure of priority queues. So for simplicity we can say priority queue is a synonym for a heap. There are two kind of heaps;

This tutorial will continue with min-heaps. Supported operations by a heap is listed below;