Some Quick Sort Facts

By Tapos Pal
Some facts for quick sort

  • Uses the divide-and-conquer paradigm
  • Best and Average case - O(nlogn)
  • Worst Case - O(n^2)
  • Key part is the Partitioning which comprise with comparison and swapping 
  • For Partitioning Hoare's algorithm works best. 
  • In place sorting
  • Works well in virtual memory env as well.

Comments

Post a Comment

Popular posts from this blog

Scala Learning: Finding Square Root

By
I am renewing my learning in Scala and I have started the course Functional Programming Principles in Scala  in Coursera. Here is some code which is taken from that course object SqrtCalculator extends App{ def abs(x: Double): Double = if(x < 0) - x else x def sqrt (x: Double) : Double = { def sqrtIterator(guess: Double): Double = if (isGoodEnough(guess)) guess else sqrtIterator(improve(guess)) def isGoodEnough(guess: Double): Boolean = abs(guess * guess - x) / x < 0.0001 def improve(guess: Double): Double = (guess + x / guess) / 2 sqrtIterator(1.0) } println(sqrt(2)) println(sqrt(3)) println(sqrt(4)) println(sqrt(1e60)) } Output: 1.4142156862745097 1.7320508100147274 2.0000000929222947 1.0000000031080746E30 Process finished with exit code 0
Read more

Deleting a hidden user in MAC

By Tapos Pal
If you have a normal user and want to delete, you can go to System Preference => User Groups => Unlock Pan => Select User to Remove => Click "-" (minus) Button But if user is hidden, the easiest way is to do it with command line. Here is the process Open "Termial" Run command "sudo dscl . delete /Users/<hidden user's short name>" You are done
Read more

Problem Solving: Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node

By Tapos Pal
Problem Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e Solution The question is a bit confusing. I first though its asking to remove the middle element of the list and I thought we have the full list. But later I think I got it. As per my understanding is we clear the node which we have access only and it will be somewhere in the middle. What we can do, we can migrate the data from next one to this one and set next to next of next. Code https://github.com/tapos/ctci/tree/master/src/p23
Read more