Sortings Data Structure - Java, Java Swing, OOAD, MIS, DSA

Data Structure

Sortings

QuickSort

        QuickSort(list[]){
            if(length of list > 1){
                pivot = select an first item of the list;
                while(length of list > 0){
                    if( element of list < pivot){
                        place element in left of pivot (sublistleft);
                    }
                    if (element of list > pivot){
                        place element in right of pivot (sublistright);
                    }
                } 
                QuickSort(sublistleft);
                QuickSort(sublistright);
            }
        }

MergeSort

        MergeSort(list){
            if (size of list >= 2){
                MergeSort(left half of list);
                MergeSort(right half of list);
                merge(left half of list and right half of list);
            }
        }
        merge(list1,list2,list3){
            initialize i1,i2,i3 properly;
            while( both list1 and list2 have elements){
                if(list2[i2] < list3[i3]){
                    list1[i1++] = list2[i2++];
                    list1[i1++] = list3[i3++];
                }
            store the remaining elements of either list2 or list3 to list1;
            }
        }

Heap Sort

Heap Sort was invented by John Williams. Heap sort uses approach similar to Selection Sort.

Heap sort uses a heap tree. There are two types of heap: max heap and min heap. A min heap tree is a binary tree having given properties:

value stored in children is greater than value stored in its parent node.
tree is perfectly balanced, and the leaves are in the last level are all in the leftmost positions.

        heapsort(list a){
            transform a to heap tree;
            for(int i = a.length; i > 1;i--){
                swap the root with the element in position i of the heap tree; 
                restore the heap property for the tree with element a[0] to a[i-1];
            }
        }

Quick Sort, Merge Sort and Heap sort's running time is O(n lgn). Bubble sort, insertion sort and selection sort take O(n²) time. Algorithms with O(n²) take longer time to complete their operations than algorithms with O(n lgn) running time.

Radix Sort Algorithm

            Consider a list of number
            make all numbers of list of same digits by appending zero's in beginning of each numbers if required
            for(int j=length of number;j>=0;j--){
                for(int i = 1 ;i< list.size;i++){
                    compare element[i].digit[j] with element[i-1].digit[j];
                    order elements
                }
            }

Note:

compare the last digit of each number of the list and order the numbers accordingly to the last digit.

compare the second last digit of each number of the ordered list and order the numbers accordingly to the second last digit

Selection Sort

        SelectionSort(list){
            for(i=0;i<list.length;i++){
                find largest element of the list of size: size(list)-i;
                swap the found largest element with the last element of the list of size: size(list)-i
            }
        }

Insertion sort

        InsertionSort(list){
            for(i=1;i<list.size();i++){
                temp = list[i];           
                j = i-1;      
                shift all elements before list[j] greater than temp by one position;
                place temp in its proper position; 
            }
        }

Online-Academy