Searching
Sorting
task task Sandeep_Jain tried to write algo for bubble sort in class but wasn’t able to in the first go.Insertion sort is used where size of array is less, it is used inbucket_sort where bucket size is small.
Most internal implementation are hybrid with main implementation starting withmerge_sort andquick_sort
quick_sort andmerge_sort aredivide_and_conquer algorithm.Individe_and_conquer the range keeps becoming smaller and theninsertion_sort is used in the subroutine.
selection_sort finds the minimum in the array puts it in first place, find minimum in remaining sub array puts in second place and so on.If array is almost sorted then useinsertion_sort
heap_sort is based onselection_sort , takestime_complexity of Theta(n*logn)Forheap_sort convert to tree and then heapify it,Sandeep_Jain got confused when creating this between min-heap and max-heap.
Parallel processors helpmerge_sort andquick_sort since they aredivide_and_conquer
heap_sort takes same time asmerge_sort but is not executed parallel.merge_sort is stable andquick_sort is not stable.Yash will be taking a class tomorrow.
Java for primitive types usedstable_sort and for non primitive types it uses some other type.quick_sort → Three types of partition algos,
Naive (stable)
Lomuto (not stable)
Hoores (not stable, fastest)
Mostly in libraries random element is picked as a pivot inquick_sort , why?
stable_sorting_algorithm retain the position of element for equal elements, so stable sorting is basically how sorting algo treats equal elements.In_place_algorithms are allowed to used recursion call stack but shouldn’t create new array.counting_sort ,radix_sort andbucket_sort are linear time algorithms.How many minimum sorts are required to sort an array,cycle_sort .
Sir, I’m trying to understand the application of stable and unstable sorting, so if in a question if any array contains duplicate elements should be prefer stable sorting algorithms.
Array of objects thenstable_sorting_algorithm
Problem solving class by Yash
Links
