Searching:
There is nothing much new i can say about searching. It's one of the most basic operations that you can do on a given set of data. It forms one of the basic steps in many complex algorithms.
For example,
You need a book in a library... you search for it.
You need the mobile number of a person in your mobile.. you search it
You need to find how much is an idly in menu card... you search it
Searches are integral part of our life.
In digital world too they become hugely important. Each example given above is different from others.
You search for a book by going to the particular section-->room-->rack and then scan the names of books in that rack.
You search for mobile number by directly entering the name of the person.
You search for an item in menu by scanning the list element by element.
What i mean is that searching algorithms used varies from situation to situation and depends on data structure used.
For example,
a sorted array can be searched using binary search algorithm.
Unsorted array is searched using linear search.
A pattern within a text is searched using KMP or Rabin-Karp algorithm.
Hash maps can be searched in constant time!
Usage of correct algorithm ensures efficiency.
I guess explaining search algorithms is not necessary here. There are plenty of searching techniques which you can learn easily from many websites.
Sorting:
Sorting is another basic operation. In my words i would say it creates ‘order out of chaos’. In many places the set of data which you have may be useless without sorting them.
For example,
Mark list of students would be of no use unless you give rank to them (imagine college counselling !)
A dictionary would make no sense if the words are not sorted
Different sorting algorithms available are,
selection sort, bubble sort, insertion sort, shell sort, heap sort,counting sort, merge sort, quick sort etc..
These algorithms are differentiated based on their complexity. First 3 sorts have quadratic complexity.
Shell sort was the first algorithm to break this quadratic complexity barrier !!
Merge sort and Quicksort are the most commonly used sorting practices. Quicksort is preferred in most circumstances because it sorts in place. ( it uses stack space for performing recursion! ) In place --> Overwriting output over input and not using any extra space !
It is also an interesting point to be noted that quick sorts worst case complexity is O(n^2) whereas for merge sort it is O(nlogn) !
Currently almost all languages provide libraries that have built in sorting function. But understanding what happens inside is necessary according to me.
Cu in next blog !
audio blog of data structures--searching and sorting
Trained @ Sourcebits
There is nothing much new i can say about searching. It's one of the most basic operations that you can do on a given set of data. It forms one of the basic steps in many complex algorithms.
For example,
You need a book in a library... you search for it.
You need the mobile number of a person in your mobile.. you search it
You need to find how much is an idly in menu card... you search it
Searches are integral part of our life.
In digital world too they become hugely important. Each example given above is different from others.
You search for a book by going to the particular section-->room-->rack and then scan the names of books in that rack.
You search for mobile number by directly entering the name of the person.
You search for an item in menu by scanning the list element by element.
What i mean is that searching algorithms used varies from situation to situation and depends on data structure used.
For example,
a sorted array can be searched using binary search algorithm.
Unsorted array is searched using linear search.
A pattern within a text is searched using KMP or Rabin-Karp algorithm.
Hash maps can be searched in constant time!
Usage of correct algorithm ensures efficiency.
I guess explaining search algorithms is not necessary here. There are plenty of searching techniques which you can learn easily from many websites.
Sorting:
Sorting is another basic operation. In my words i would say it creates ‘order out of chaos’. In many places the set of data which you have may be useless without sorting them.
For example,
Mark list of students would be of no use unless you give rank to them (imagine college counselling !)
A dictionary would make no sense if the words are not sorted
Different sorting algorithms available are,
selection sort, bubble sort, insertion sort, shell sort, heap sort,counting sort, merge sort, quick sort etc..
These algorithms are differentiated based on their complexity. First 3 sorts have quadratic complexity.
Shell sort was the first algorithm to break this quadratic complexity barrier !!
Merge sort and Quicksort are the most commonly used sorting practices. Quicksort is preferred in most circumstances because it sorts in place. ( it uses stack space for performing recursion! ) In place --> Overwriting output over input and not using any extra space !
It is also an interesting point to be noted that quick sorts worst case complexity is O(n^2) whereas for merge sort it is O(nlogn) !
Currently almost all languages provide libraries that have built in sorting function. But understanding what happens inside is necessary according to me.
Cu in next blog !
audio blog of data structures--searching and sorting
Trained @ Sourcebits
No comments:
Post a Comment