Java DS Algorithms

July 17, 2021

Java DS Algo

• Java DS Algo
• Introduction
  • Keyterms
    • Complexity
    • Stable_Unstable
    • Arrays
    • Sort Algorithms
      • Bubble sort
      • Selection sort
      • Insertion sort
      • Shell sort
    • Search Algorithms
      • Linear Search
      • Binary Search
    • References
  • Next: Agile Software Methodology

Introduction

• organises and store data
• Which one to use ? depends on the application use, as a developer choose the best based on the scenario
• fds

Keyterms

Complexity

• Time : compare the worst-case in all scenarios, as we cannot compare the best or the average case.
• Memory : It is cheap, mostly now a day we dont see.
• Big (O) notation : compare the time complexity of different algorithms (no of steps)
  • e.g [Best -> Worst] : O(1) - Constant, O(log₂n) - Logarithmic, O(n) - Linear, O(nlog₂n) - n log*n, O(n²) - Quadratic

Stable_Unstable

• When relative order of duplicate item is preserved it is a stable sort, else unstable.
• But who cares for integers, they can come anywhere, however OBJECTS you need to care.

Arrays

• not dynamic, fixed size.
• Contiguous block in memory (Static length), so size to be initialized during declaration.
• Every item occupies same memory
• Object references(Strings) are of the same size.
• To calculate address : X(starting addr) + ith elem * Y(Size of each elem) - 3 steps
• Time to retrieve is same, if we know the index of elem. Constant time complexity - which is always 3 steps - O(1)
• Worst time complexity O(n)

public class Arrays_ {
    public static void main(String[] args) {
        int[] array_ = new int[2];
        array_[0] = 1;
        array_[1] = 5;
        for (int i = 0; i < array_.length; i++) {
            System.out.println("Elem[" + i + "] : " + array_[i]);
        }
    }
}

Sort Algorithms

Bubble sort

• Compare it with the next element
• In-Place algorithm, O(n^2) - quadratic
• 100 steps to sort 10 items, 10,000 for 100 items, algorithm degrades as steps increases.
• It is stable sort, because we swap only when it is greater than > but not greater than equal >=

Selection sort

• Keep track of the largest index
• In-Place algorithm, O(n^2) - quadratic
• Reduces swapping (only once per traversal) compared to bubble sort
• Unstable algorithm - because we swap the largest with the last index, so we might pick up the twin and place it front.

Insertion sort

• Pick 1 element from unsorted and place it in correct sorted position. It does by shifting right, making extra room for the new element
• In-Place algorithm, O(n^2) - quadratic
• Stable algorithm - we stop when we find <= elem, so the duplicate elem, will be placed next to it.
• Sometimes there is lot of shifitng involved, when the small number is places at the last.

Shell sort

• In-place, time complexity depends on gap, Worst case O(n^2)
• Unstable
• Can improve even bubble sort using this, can decrease the swaps

Search Algorithms

Linear Search

  public static int linear_search(int searchElem) {
      for (int i = 0; i < arr_.length; i++) {
          if (arr_[i] == searchElem) {
              return i;
          }
      }
      return -1; // searchElem not found
  }

• TC : O(N) is worst case, if element is not found and we have to iterate the whole list.

Binary Search

• Data must be sorted

References

• Data Structures and Algorithms: Deep Dive Using Java

Next: Agile Software Methodology