Please explain mergesort quicksort and bucketsort please sho

Please explain mergesort, quicksort, and bucketsort (please show how to organize numbers in each). What are the differences and which run faster

Solution

Merge sort:

    In this sorting techniques, all the elements can be sorted by using divide and conquer methodology. Here all the elements are in array is further divided untill the number of elements in array is 1 after that start merging the all array elements and comparision will be done while merging and this result in sorted elements ...

eg.. 3 2 4 1

    considered as 4 arrays with each an element

    3           2              4                 1.

now merge these elements and sort the elements by comparing with other array elements.

2 3           1 4

      1 2 3 4

hence the resultant sorted array is obtained and this algorithm runs at (nlogn) at best case and O(n) at worst case

space complexity

Quicksort:

          This sorting method is implemented based on the principle of finding the position of an element in array and all the elements lesser value to it are placed at left side and remaining are at right side hence by continuing this process we can sort the given unsorted array

First pivot element is labeled and position of this element is to be finded first and now from left check for the element which is greater than pivot and from right check for the element which is less than pivot then

   let left,right are two indexes then

    if left < right    then Swap(Arr[right],Arr[left]) and Swap(Arr[piv],Arr[left])

    if left>right       then Swap(Arr[piv],Arr[right])

e.g: 3 2 1 4

piv=0 and left=3 and right=2 are calculated based on the above thoery

then here left>right then Swap(Arr[piv],Arr[right]) then the resultant array is

1 2 3 4 which is sorted

In best case the time complexity is O(nlogn) and at worst case the space complexity is O(logn)

Bucket sort:.

Bucket sort or Bin sort is a sorting algorithm based on dividing the elements into buckets and grouped the array elemtns based on these buckets range. First consider a bucket of range 0-9 then all the elements between 0-9 in the array will be stored in this bucket and the elements in this bukcet are to be sorted and print the bucket values of all avaialble buckets

e.g. 9 3 13 10 15

consider two buckets B1 and B2 with ranges of 0-9 and 10-19 and hence all the elements in the array placed on their respective bucket based on the range values therefore.

   B1={9,3} and B2={13,10,15}

Now sort the elements in all available buckets and then print the elements if any bucket have more elements and consider subranges in the given range and repeat this process

B1={3,9} and B2={10,13,15}

hence elements are sorted using Bucket sort

In best case scenario the time complexity is given as O(n+k) and at worst case spcae complexity is O(n)

So based on the worst case space complexity values on comparing the three sorting methods Quick sort wil run faster because it have space complexity of O(logn) even at worst case...