Search code examples
sortingdata-structuresdoubly-linked-list

find out which sorting alogorithm used in this function


Hi can someone help me out which sorting algorithm used in this function

public void sortList() {  
        Node current = null, index = null;  
        int temp;  
        //Check whether list is empty  
        if(head == null) {  
            return;  
        }  
        else {  
            //Current will point to head  
            for(current = head; current.next != null; current = current.next) {  
                //Index will point to node next to current  
                for(index = current.next; index != null; index = index.next) {  
                    //If current's data is greater than index's data, swap the data of current and index  
                    if(current.data > index.data) {  
                        temp = current.data;  
                        current.data = index.data;  
                        index.data = temp;  
                    }  
                }  
            }  
        }  
    }  

By the way it is Doubly Link List


Solution

  • The current node is fixed and then iteration is done from next node to the end(via index variable), at the end of one iteration of outer loop the node pointed to by current has correct value, then the current is progressed to next node. This is Selection Sort, the most elementary sort

    Fun fact : although slow because of complexity O(n^2) selection sort can be used when the write operation is expensive because it only swaps max n times for a list of size n