Algorithms 101: Sorting II

#computers

These three remaining sorting algorithms are better af than the previous three and more complicated af to implement. That said these three algorithms excel where the previous three didn't that is, in sorting the lists efficiently. Though the implementations I'm doing are too basic, these algorithms can be modified to accommodate the sorting involving huge data and huge in the sense millions and billions of items!!

It's too easy to understand but a little complicated than the previous when it comes to the implementation. So, how merge sort works? It just breaks an array of elements into its components and then pairs them up by arranging them in their proper respective places and rejoins them into one sorted array. That said, the time complexity of merge sort is O(n log n) and this is the case at worst-case too thereby making this a powerful algorithm. This algorithm can kick others out when it comes to handling a large amount of data by performing significantly faster than the previous ones.

method mergesort(arr)
if(arr.length==1)
return arr
arr1[0]...arr1[n/2]
arr2[n/2+1]...arr2[n]
arr1 = mergesort(arr1)
arr2 = mergesort(arr2)
return merge(arr1,arr2)
end mergesort
method merge(arr1, arr2)
take arr3
while(arr1 and arr2 have elements)
if(arr1[0] > arr2[0])
add arr2[0] to end of arr3
remove arr2[0] from arr2
else
add arr1[0] to end of arr3
remove arr1[0] from arr1
end if
end while
while(arr1 has elements)
add arr1[0] to end of arr3
remove arr1[0] from arr1
end while
while(arr2 has elements)
add arr2[0] to end of arr3
remove arr2[0] from arr2
end while
return arr3

Quick sort is effective when it comes to its speed but in its base form, its not quite stable enough. It has the worst-case time complexity of O(n²) but worst-case is rarely the case for quick sort thereby making it faster than the previous algorithms. It's in general time complexity is O(n log n) thus it can be faster and more efficient when used in proper scenarios. That said, quick sort can be a little confusing to understand which is troublesome. In quick sort we first select a pivot element in the array and place the rest of the numbers accoring to this pivot element, that is smaller ones before the pivot and larger ones after. So, when this is done we have the array with pivot in middle and left small ones and right large ones, both of which are yet to be sorted. Now we chose the new pivot numbers in both ends and again repeat the process until the array is sorted.

method quckSort(arr, low, high)
if(low < high)
middleElement = low+(high-low)/2
pivotElement = arr[middleElement] 
quickSort(arr, low, middleElement-1)
quickSort(arr, middleElement+1, high)
end

Let's take an array consisting of elements {7,8,12,11,2,19,4,62}. The code will be as follows:

This guy is hard of all the algorithms but has the time complexity of O(n log n) at the worst-case meaning even at worst this guy kicks ass of the rest. That said, heap sort uses a heap which is a special kind of binary tree where the nodes are greater than their children making the root the largest of all. To make it simple basically The Heapsort algorithm involves preparing the list by first turning it into a max heap. The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and shifting the new first value into its position in the heap. This algorithm needs additional reading to understand what's what. So, the best would be to refer the gog.

Heapsort(arr)
BuildHeap(arr)
for i = n to 1
swap(arr[1], arr[i])
n = n - 1
Heapify(arr, 1)

BuildHeap(arr)
n = elements_in(arr)
for i = floor(n/2) to 1
Heapify(arr,i,n)
Heapify(arr, i, n)
left = 2i
right = 2i+1
if (left <= n) and (A[left] > A[i])
max = left
else 
max = i
if (right<=n) and (A[right] > A[max])
max = right
if (max != i)
swap(arr[i], arr[max])
Heapify(arr, max) 

Let's take an array consisting of elements {2,8,5,3,9,1}. The code will be as follows:

So, this winds up all the sorting algorithms!! These three algorithms are very hard but are much preferred by the developers all around whenever sorting is required. Though I've done the in general implementations of all these algorithms the main tricky part will be choosing them in the right scenario and using them according to that scenario.