NON-COMPARISON SORTING ALGORITHMS

NON-COMPARISON SORTING ALGORITHMS

1. Sorting Algorithms that do not use comparisons to perform a sort.

2. SORTING ALGORITHMS

   • COMPARISON SORT ALGORITHMS
     • Limits
       • there are N! ways of re-arraning the #s in the array, among all N! sorts, only ONE is the correctly sorted 1. The task of a sorting algorithm can be seen as finding the correct arrangement among all the different arrangements. ~ Ω(log(N!))

3. Counting Sort

   • DRAWBACKS: (1 )it can only sort integer numbers (2) extra memory used by array
     • #s in position of indices represent the number of times that index(#) appears in the array

4. Radix Sort

   • TIME COMPLEXITY: θ(d*(N+k)) ~ θ(N) - linear
   • Radix sort works with integer AND decimal numbers

5. Bucket Sort

   • Each number to be sorted is put into a 'bucket' (an empty linked list) corresponding to its value. The linked lists then are sorted, and then merged together as the sorter list.

Bilder und Dateien der Mindmap