Selection Sort

Another O(n2) sorting algorithm that can be adapted for linked lists is selection sort. This can be implemented very easily (assuming you have a doubly-linked list) by using this algorithm: Initialize an empty list holding the result. While the input list is not empty: Scan across the linked list looking for the smallest remaining element. Remove that element from the linked list. Append that element to the result list. [Read More]

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]

The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort. Pseudocode of selection sort Get the smallest element and put it in the first position Get the next smallest element and put it in the 2nd position …. [Read More]