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 

Bubble sort on double linked list

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

 Following can be the pseudocode:

public void bubbleSort() {  
    boolean done = false;  
    while (!done) {  
        Node cur = head;  
        done = true;  
        while(cur != tail) {  
            if (cur.getNext().getCount()>cur.getCount()) {  
                swap(cur.getNext(),cur);  
                done=false;  
            }  
            cur = cur.getNext();  
        }  
    }  
}

Thanks.
Source : stackoverflow

bubble sort  kodeknight  sorting  Doubly Linked List  DLL 

Sort a linked list using merge sort

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  3 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. Merge sort is very special (in fact many standard sort libraries like in java internally uses a combination of merge sort and insertion sort) because it has the wonderful property of being a stable sort. [Read More]
kodeknight  merge  sorting  linked list  merge-sort 

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 

Find increasing 3-tuple (sub-sequence)

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

Problem: You given an array: 3, 2, 1, 6, 5, 4, 9, 8, 7 you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array. Answer can have multiple tuples, you have to find any one. In this array, answer will be 3, 6, 9 Solution: Simple. Time complexity = O(n ^ 2) Create an array of indexes, and sort the original array keeping track of the indexes in the second array. [Read More]
maxima  kodeknight  subsequence  minima  incomplete  array  increasing-sequence 

Merge two arrays efficiently - one sorted, another unsorted

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

Problem Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently. Solution Method 1 - Insert the elements in sorted array using binary search Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that. Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity. [Read More]
kodeknight  merge  union  sorting  array  two-arrays  two-sorted-arrays  sorted-array 

Red Black Tree vs AVL Tree vs B-Tree

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

B-tree when you’re managing more than thousands of items and you’re paging them from a disk or some slow storage medium. RB tree when you’re doing fairly frequent inserts, deletes and retrievals on the tree. AVL tree when your inserts and deletes are infrequent relative to your retrievals. think B+ trees are a good general-purpose ordered container data structure, even in main memory. Even when virtual memory isn’t an issue, cache-friendliness often is, and B+ trees are particularly good for sequential access - the same asymptotic performance as a linked list, but with cache-friendliness close to a simple array. [Read More]
kodeknight  red-black-tree  RBT  balanced trees  incomplete  avl 

Union Find

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

The Union-Find data structure is used to keep track of a partition of a set and supports two operations. The Union(x, y) operation merges the subsets containing x and y, and the Find(x) operation returns the name of the leader element of the subset to which x belongs. The implementation is based on a response to this post on StackOverflow, but extended with a makeSet operation, a getNumGroups operation, and tests. [Read More]
kodeknight  incomplete  union-find 

Bottom-up Merge Sort

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

Recursive algorithm In the earlier article I’ve described a recursive version of the Merge Sort Algorithm OR Top Down Merge sort. Of course every recursive algorithm can be written in an iterative manner . Non recursive algorithm So today I am going to present the bottom-up version of the same algorithm, written in a non-recursive fashion . The main idea of the bottom-up merge sort is to sort the array in a sequence of passes . [Read More]
kodeknight  merge  sorting  incomplete  top-down  merge-sort  bottom-up