Sorting is a process of arranging items in ascending or descending order. This process can be implemented via many different algorithms. Following is the list of sorting algorithms :
- Bubble Sort
- Selection Sort
- Count Sort
- Insertion Sort
- Merge Sort
- Quicksort
- Heap Sort
Time complexity of sorting algorithm
Quicksort
Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied in practice.
Algorithm
The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:
- Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in range of sorted values, even if it doesn’t present in the array.
- Partition. Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided in non-equal parts.
- Sort both parts. Apply quicksort algorithm recursively to the left and the right parts.
Partition algorithm in detail
There are two indices i and j and at the very beginning of the partition algorithm i points to the first element in the array and j points to the last one. Then algorithm moves i forward, until an element with value greater or equal to the pivot is found. Index j is moved backward, until an element with value lesser or equal to the pivot is found. If i ≤ j then they are swapped and i steps to the next position (i + 1), j steps to the previous one (j – 1). Algorithm stops, when i becomes greater than j.
After partition, all values before i-th element are less or equal than the pivot and all values after j-th element are greater or equal to the pivot. In other words
i : Boundary between the elements that are less than pivot and those greater than pivot
j : Boundary between the partitioned and unpartitioned part of array
Merge sort is based on Divide and conquer method. It takes the list to be sorted and divide it in half to create two unsorted lists. The two unsorted lists are then sorted and merged to get a sorted list. The two unsorted lists are sorted by continually calling the merge-sort algorithm; we eventually get a list of size 1 which is already sorted. The two lists of size 1 are then merged.
Algorithm:
This is a divide and conquer algorithm. This works as follows –
- Divide the input which we have to sort into two parts in the middle. Call it the left part and right part.
Example: Say the input is -10 32 45 -78 91 1 0 -16 then the left part will be -10 32 45 –
78 and the right part will be 91 1 0 6. - Sort each of them separately. Note that here sort does not mean to sort it using some other method. We use the same function recursively.
- Then merge the two sorted parts.
Heap Sort
Heap Sort is one of the best sorting methods being in-place and with no quadratic worst-case scenarios. It is an in-place sorting algorithm as it requires a constant amount of additional space. Heap sort algorithm is divided into two basic parts :
- Creating a Heap of the unsorted list.
- Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array.
- The heap is reconstructed after each removal.
What is Binary Heap?
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater (or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array.
How to build the heap?
Heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom up order.
Reference :-