Blog 206 — Sorting and Algorithms

We learning about sorting algorithms. A sorting algorithm is an algorithm used to reorder items in a list or an array according to a specific requirement. For example, sorting algorithms can organize an array of items from smallest to largest.

An efficient sorting algorithm is important for optimizing the efficiency of other algorithms (such as search and compression algorithms).

Sorting algorithms are made up of a series of instructions. They take an array or list as an input, perform operations, and output a sorted array.

There are a number of popular sorting algorithms. The nine most popular are:

  • Insertion sort
  • Merge sort
  • Quicksort
  • Selection sort
  • Counting sort
  • Bucket sort
  • Radix sort
  • Heapsort

2. What are the pros and cons of immutability?

In object oriented programming, An immutable object is an object whose state, once initialized by the constructor, cannot be modified throughout the lifetime of the object.

  • An immutable object can not be extended.
  • All fields must be marked final.
  • Immutable classes may not expose mutable fields, either through getters or through public fields.

https://medium.com/tribalscale/understanding-immutability-fdd627b66e58

3. How can you achieve immutability in your own code?

Mutable objects are those whose state is allowed to change over time. An immutable value is the exact opposite — after it has been created, it can never change. Strings and Numbers are inherently immutable in javascript. Refer this article for further answers.

4. What are Divide and Conquer algorithms? Describe how they work. Can you give any common examples of the types of problems where this approach might be used?

  • Conquer: Sub problem by calling recursively until sub problem solved.
  • Combine: The Sub problem Solved so that we will get find problem solution.
DAC(a, i, j)
{
if(small(a, i, j))
return(Solution(a, i, j))
else
m = divide(a, i, j) // f1(n)
b = DAC(a, i, mid) // T(n/2)
c = DAC(a, mid+1, j) // T(n/2)
d = combine(b, c) // f2(n)
return(d)
}

5. How do insertion sort, heap sort, quick sort, and merge sort work?

Sorting in programming involves placing elements in a list or an array in a certain order. Efficient sorting is important for optimizing other algorithms that require input data to be in sorted lists.

While you may not be required to implement a sorting algorithm in your day-to-day as a software developer, it’s important to know how some of these algorithms work internally. These are common for coding interviews and make you a more efficient developer.

6. What are the key advantages of insertion sort, quick sort, heap sort and merge sort? Discuss best, average, and worst case time and memory complexity.

Quick sort — is an internal algorithm which is based on divide and conquer strategy.

Insertion sort — The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Heap sort — Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Merge sort — is an external algorithm and based on divide and conquer strategy.

7. Explain the difference between mutable and immutable objects.

Mutability and Immutability are core principles in various programming paradigms.

Mutable objects are objects whose value can change once created, while immutable objects are those whose value cannot change once created. In JavaScript numbers, strings, null, undefined and Booleans are primitive types which are immutable. Objects, arrays, functions, classes, maps, and sets are mutable.

Mutable types have individual identities and are compared by reference, that is, variables hold references to objects, or rather they point to the memory location of an object. Immutable types don’t have individual identities hence are compared by value, i.e. the value in the variable and not the location they are referencing.

8. What are the three laws of algorithm recursion? Describe them in your own words and what they mean to you.

2. A recursive algorithm must change its state and move toward the base case.

3. A recursive algorithm must call itself, recursively.

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Fixing Click Event Issue on Mobile Web UI

Why beginners should avoid using ExpressJS?

How to download CSV and JSON files in React

Don’t go breaking my loops

Typescript discriminator

Blog-207

New guide on Java Objects

Choose the best Testing Library for React

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Meng Fu

Meng Fu

More from Medium

Polymorphism in VB6

Finding Luke through the command line by consuming an API

How to install Git

What is a Class? What is an object? What is an instance?