Nut and Bolt Problem (OR Key and Lock Problem) - Matching Nuts and Bolts when nuts cannot be compared with nuts and bolts with bolts

 Posted on May 1, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem You are given a collection of nuts of different size and corresponding bolts. You can choose any nut & any bolt together, from which you can determine whether the nut is larger than bolt, smaller than bolt or matches the bolt exactly. However there is no way to compare two nuts together or two bolts together. Suggest an algorithm to match each bolt to its matching nut. Compute time complexity of your algorithm. [Read More]
kodeknight  quicksort  partition 

Sort a linked list using quick sort

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. We have discussed the sorting options for linked list here. Here we will discuss about quick sort. Another O(n log n) sort that you can implement on linked lists is a modification of quicksort. [Read More]
kodeknight  quicksort  sorting  linked list 

What's the fastest algorithm for sorting a linked list?

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Merge sort is the best choice. At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. It is reasonable to expect that you cannot do any better than O(N log N) in running time, whenever we use comparison based sorts. [Read More]
bubble sort  kodeknight  merge  quicksort  sorting  linked list  Selection Sort  merge-sort  insertion-sort 

Sorting

 Posted on August 9, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

What is a sorting algorithm ?

A sorting algorithm is an algorithm that sorts the data into some order, say from ascending to descending.

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

Classification of sorting algorithms
Sorting algorithm can be classified in various ways.

Comparison sorts vs non comparison sorts

Various sorts

kodeknight  Page  quicksort  selection-sort  binary-sort  shell-sort  sorting  radix-sort  merge-sort  Comparison Sort  insertion-sort 

Sorting Array of Three Kinds or The Dutch National Flag Problem OR three color sort

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), write an algorithm to sort the array. For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c). This problem is also called three color sort. Solution: the Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors. [Read More]
kodeknight  quicksort  binary array  sorting  incomplete  array  integer-sort  zero 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

in your Pseudocode, the if condition should be if …

RM - May 3, 2014

in your Pseudocode, the if condition should be if (low < high).

Thanks Rish. I have made the change a[low] > a[high] rather than low < low. :). Thanks for correcting me.

kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort. Example Input - Binary unsorted array A = {0,1,1,0,0,1}; Output - binary sorted array B = {0,0,0,1,1,1} Solution This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n). [Read More]
kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Quick sort

 Posted on January 14, 2010  (Last modified on August 7, 2020)  |  8 minutes  |  Kinshuk Chandra

Hoore cisca discovered it in 1961. Why quicksort? Definitely a greatest hit algorithm  Prevalent in practice O(n log n) time “on average” minimal extra memory needed (which gives it leverage over merge sort) The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Quicksort helps us solving this problem. What is quick sort? [Read More]
pathological data  Algorithms  kodeknight  randomized algorithm  time complexity  divide and conquer  quicksort  sorting  programCPP  Data Structure