date posted: 2020-01-06
As you can tell by its name it is simply searching algorithm that searches for a value starting from either ends of a list and moving towards the opposite end. Move only in one direction hence called "Linear Search".
Since it searches sequentially one by one it has terrible performance however it is only way to search for a value when list is unsorted.
Furthermore just like any other terrible performance algorithms it is very easy to implement therefore a lot of people still implement sequential search when len(list) isn't too large and you do not need exceptional performance.
Main goal of self-organinzing search is it self-organizes list by placing recently searched value into desired position. It is like cache in our computer. Main goal is to organize frequently searched value to front of list to increase efficiency, there are three main ways.
Name itself if self-explantory... Searched value goes to the front of a list.
This method can be efficient when there are subsets of data that are being searched very often. However if a data that has not been called before are trying to be searched, it will take a while since it will likely be near the end.
Starting from first element in a list, when your value is searched simply switch place with previous value.
ex: search for value = 4. [1,3,6,5, 4]
checking 1, 3, 6, 5, when 4 is searched switch position with previous element which is 5. so list =[1, 3, 6, 4, 5]
Thus if 4 is called multiple times, each time it will get closer hence as an element gets searched more often it will be found more easily.
First, count frequency for each element and store it in alternative memory.
Second, re-organize by placing in order of most frequently appearing element to least.
Drawback, it needs extra memory to store frequency count and extra time to sort according to frequency count.