Cosmic Techie

Heap Sort is a sorting algorithm based on the heap data structure. A heap is a tree based data structure where the tree is a complete binary tree. A complete binary tree is a binary tree in which all levels are completely filled, except the last level which may or may not be complelety filled. Heaps can be of two types: Max Heap: In max heap, every parent node must have value greater than or equal to it's child's value.  Min Heap: In min heap, every parent node must have value less than it's child's value. We are going to use the Max Heap for heap sort here. The sorting process includes: construction of a heap from the data, a max heap precisely, swapping of the first and last node, removing the last node from the heap and processing it for the remaining. With each cycle, the heap gets smaller and the list gets to sort.  Illustration: Algorithm: Construct max heap from the list Swap the first node with the last node Remove last node from heap Perform step 1 to 3 for the...

Quick Sort is an algorithm for sorting which is based on divide and conquer approach. An element is chosen as pivot and partitions the given list. The elements are swapped, based on comparison with pivot value, in order to obtain a sorted list. The partitioned sublists are recursively called to sort the elements in list. The selection of pivot can decide the efficiency of the quick sort. Illustration: Algorithm: partition(list,lowestIndex,highestIndex)     pointerI=lowestIndex-1     pivot=Element at highestIndex     for pointerJ from lowestIndex to HighestIndex         if ElementAtpointerJ < pivot             pointerI=pointerI+1             swap ElementAtpointerI with ElementAtpointerJ     swap Element at pointerI+1 with pivot     return i+1 quickSort(list,lowestIndex,highestIndex)     if lowestIndex < highestIndex         ...

Merge Sort is a sorting algorithm which is based on divide and conquer approach. The list is divided into two halves until each sublist has a single element, and the sublists are merged in a sorted manner that the sorted list is obtained. It is a very efficient algorithm for sorting. The technique simply involves: Divide the list into two subslists, Make recursion call for the sublists, and then Merge the sublists. Illustration: Algorithm: if length(list)>1     find point of divide,mid=length(list)//2     left sublist L,index 0 to mid     right sublist R, index mid+1 to length(list)-1     recursion,calling function itself for L     recursion,calling function itself for R     i=j=k=0     while i<length(L) and j<length(R)         if L[i] < R[j],then list[k]=L[i] and i=i+1         else, list[k]=R[j] and j=j+1         k=k+1     while i<le...

Selection sort is a sorting algorithm in which the list is considered into two parts, sorted part at left and unsorted part at right. It selects the smallest element from the unsorted list, in each iteration, and places that element at the beginning of unsorted list. Intitially, the sorted part in empty, that is, the whole list is unsorted. With each iteration, the smallest element is swapped with the leftmost element of the unsorted part of the list. After required iterations, we obtain a sorted list of elements. Illustration: Algorithm: for all elements in list,step=from step=0 to step=length(list)-1     min_idx=step     for i from step+1 to length(list)-1          if value at index i < value at index min_idx             min_idx = i     swap as (list[step],list[min_idx])=(list[min_idx],list[step]) Time Complexity: Worst Case: O(n 2 ) Average Case: O(n 2 ) Best Case: O(n 2 ) Space Complexity: O(1) P...

Insertion Sort is a simple sorting algorithm. It is like picking up an element from the list and inserting it to its rightful index as per intendent order of the elements in the list. Initially, the first element is considered to be at its right place and as we go through the elements of the list, the sorting takes place by comparing the elements. Illustration: Algorithm: for all elements in list,step=from step=0 to step=length(list)-1     first element is sorted,when step=0     key=list[step],the element to be extracted to insert at the right index     j=step-1     while j>=0 and key < value at index j         list[j+1]=list[j]         j=j-1     list[j+1]=key Time Complexity: Worst Case: O(n 2 ) Average Case: O(n 2 ) Best Case: O(n) Space Complexity: O(1) Program for insertion sort: Output:

Bubble sort is a simple sorting algorithm in which adjacent elements are compared to each other and swapped if the elements are not in intended order. It is a comparison based algorithm. This algorithm is not suitable for large data because of its not so good worst and average case time complexity O(n 2 ) , n is the number of elements. Illustration: Algorithm: for all elements in list     for adjacent elements of unsorted portion of list         if leftElement > rightElement             swap the elements Time Complexity: Worst Case:  O(n 2 ) Average Case:  O(n 2 ) Best Case:  O(n) Space Complexity: O(1) Program for Bubble Sort: Output: