#Day2 #100DaysOfCode
Time complexity: O(nlogn) i.e: divide problem into two smaller problems
divide and conquer algorithm
partition the array into 3 parts. middle position is called the pivot. anything on the left of the pivot should be smaller than it. anything on the right should be larger than it. quicksort the left and right arrays till the whole array is sorted.
there are many ways to pick the pivot. (i.e: first, last, random, median)
quicksort is preferred on array than merge sort because
_ it is an in-place algorithm. doesnt need extra storage. sorting is done within that array. Since create extra arrays like in merge sort might increase cost and running time.
_ quicksort requires a lot of random access of elements. i.e: find the index of pivot in sub-array. which could not be done so easily like in linked list.
_
https://github.com/dbaocaca/data_structure_and_algorithm/blob/main/quick_sort.cpp
Time complexity: O(nlogn) i.e: divide problem into two smaller problems
divide and conquer algorithm
partition the array into 3 parts. middle position is called the pivot. anything on the left of the pivot should be smaller than it. anything on the right should be larger than it. quicksort the left and right arrays till the whole array is sorted.
there are many ways to pick the pivot. (i.e: first, last, random, median)
quicksort is preferred on array than merge sort because
_ it is an in-place algorithm. doesnt need extra storage. sorting is done within that array. Since create extra arrays like in merge sort might increase cost and running time.
_ quicksort requires a lot of random access of elements. i.e: find the index of pivot in sub-array. which could not be done so easily like in linked list.
_
https://github.com/dbaocaca/data_structure_and_algorithm/blob/main/quick_sort.cpp
