What is Algorithm?

• It is a logical and mathematical approach to solve or crack a problem using any possible method.
• Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.
  
  

Criteria of a Algorithm:

1. Input
2. Output
3. Definiteness
4. Finiteness
5. Effectiveness
   
   

Different types of Algorithms:

• [Searching Algorithms]
  • [Linear Search]
  • [Binary Search]
• [Sorting Algorithms]
• Divide and conquer algorithms
• Recursive algorithms
• Backtracking algorithms
• Brute force algorithms
• Greedy Algorithms
• Dynamic programming algorithms
  
  

Application of Algorithms:

• Searching Data
• Sorting Data
• Find out the Shortest Path
• Best Possible solution
  
  

Complexity Analysis of Algorithm:

• Time Complexity
• Space Complexity
  
  

Three Cases of Complexity Analysis:

• Best case depends on the input
• Average case is difficult to compute
• So We usually focus on worst case analysis:
  • Easier to compute
  • Usually close to the actual running time

Some common rates of growth:

Let n be the size of input to an algorithm, and k some constant. The following are common rates of growth-

• Search for a target data from a data set.

• Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.

Why Searching Algorithms:

• It is used for unsorted and unordered small list of elements.
• It has a time complexity of O(n), which means the time is linearly dependent on the number of elements, which is not bad, but not that good too.
• It has a very simple implementation.

Two possible outcomes:

• Target data is Found (Success)
• Target data is not Found (Failure)
  
  

Based on the type of search operation, two popular algorithms available:

• Linear Search / Sequential Search
• Binary Search
  
  

Linear Search

Check each and every data in the list till the desired element or value is found.

Algorithm:

• Best case: O(1)
• Worst Case: O(n)

   // First way...
   i = 1 
   while i < n && Z != X[i] do           // Z = searching variable
      i = i+1

   if i < n then
      FOUND
   else
      NOT FOUND


   // Second Way...
   flag = FALSE
   for i = 1 to n
      if A[i] == key        // key = searching variable
         flag = TRUE;
    
   if flag == TRUE
     FOUND
   else
     NOT FOUND

   After looking at the algorithm, you can see that there is an example in the above file [Linear_Search.java] to better understand.

Binary Search

To use binary search, your array / list must be sorted. If it is not sorted then you cannot do binary search. Or else you have to sort the array / list.

• Best case: O(1)
• Worst Case: O(n)

   Algorithm:

   low = 1                          //Start position
   high = n                         //Last position
   flag = false

   while low <= high and flag = = false do
        mid = (low + high) / 2
        Xm = A[mid]                   // Xm = a veriable where we store our mid variable

        case:
            Xm < Z : low = mid + 1    // z = searching number
            Xm > Z : high = mid - 1
            Xm == Z : flag = true
       
   if (flag == true){
      FOUND
   }
   else
      NOT FOUND
       

   After looking at the algorithm, you can see that there is an example in the above file [Binary_Search.java] to better understand. 

• Sorting refers to arranging data in a particular format.

• Most common orders are in numerical or lexicographical order.

Why Sorting Algorithms:

• The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner.

• Sorting is also used to represent data in more readable formats.

We will Learn:

1. Selection Sort
2. Insertion Sort
3. Merge Sort
4. Quick Sort

Selection Sort

• Best case: O(n^2)
• Average Case: O(n^2)
• Worst Case: O(n^2)

Idea:
1. Find the smallest element in the array
2. Exchange it with the element in the first position
3. Find the second smallest element and exchange it with the element in the second position
4. Continue until the array is sorted

Algorithm:
n ← length[A]
for i ← 1 to n - 1
    min ← i

    for j ← i + 1 to n
        if A[j] < A[min]
            min ← j

    exchange A[i] ↔ A[min]
    
After looking at the algorithm, you can see that there is an example in the above file [Selection.java] to better understand.        

Insertion Sort

• Best case: O(n)
• Average Case: O(n^2)
• Worst Case: O(n^2)

Idea:
1. Start with an empty left hand and the cards facing down on the table.
2. Remove one card at a time from the table, and insert it into the correct position in the left hand
3. Compare it with each of the cards already in the hand, from right to left
4. The cards held in the left hand are sorted 
5. These cards were originally the top cards of the pile on the table

Algorithm:
InsertionSort (A){

    for j = 2 to length(Array)
        key = Array[j]
        i = j - 1

        while ( i > 0 && Array[ i ] > key ){
            
            A[i+1] = Array[i]
            i = i -1

        }
        Array[i + 1] = key

    }
    
After looking at the algorithm, you can see that there is an example in the above file [Insertion.java] to better understand.