Chapter: Programming and Data Structures - Sorting And Searching

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Radix sort

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value

RADIX SORT:

 

Definition:

 

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value 

·        sort by the least significant digit first (counting sort)

Numbers with the same digit go to same bin

o  reorder all the numbers: the numbers in bin 0 precede the numbers in bin 1, which precede the numbers in bin 2, and so on

o  sort by the next least significant digit

o  continue this process until the numbers have been sorted on all k digits

 

 

Algorithm:

Extra information: every integer can be represented by at most k digits 

o d1d2…dk where di are digits in base r

o d1: most significant digit 

o dk: least significant digit


Example: 275, 087, 426, 061, 509, 170, 677, 503




Complexity Analysis:

 

k passes over the numbers (i.e. k counting sorts, with range being 0..r) 

each pass takes O(N+r)

total: O(Nk+rk)

r and k are constants: O(N)

 


MERGE SORT

 

Definition;

The Merge sort algorithm is based on divide and conquers strategy. First, the sequence to be sorted is decomposed into two halves ( Divide ). Each half is sorted independently ( Conquer ). Then the two sorted halves are merged to a sorted sequence ( Combine ).


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.