Sorting Search Based Problems

BUBBLE

_______________________________________________________________

  public static void sortAsending(int[] num) {  
           int temp;  
           for (int i = 0; i < num.length - 1; i++) {  
                for (int j = 1; j < num.length - i; j++) {  
                     if (num[j - 1] '>' num[j]) {  
                          temp = num[j - 1];  
                          num[j - 1] = num[j];  
                          num[j] = temp;  
                     }  
                }  
           }  
      }  
      public static void sortDesending(int[] num) {  
           int temp;  
           for (int i = 0; i < num.length - 1; i++) {  
                for (int j = 1; j < num.length - i; j++) {  
                     if (num[j - 1] '<' num[j]) {  
                          temp = num[j - 1];  
                          num[j - 1] = num[j];  
                          num[j] = temp;  
                     }  
                }  
           }  
      }  




INSERTION


_______________________________________________________________



  /*  
      Step 1 − Store  number in copynumber  & store its index in j
      Step 2 − Search the minimum element in the list  
      Step 3 − Iterate while loop until  these 2 conditions are valid
             a) j>0
             b) copynumber< arr[j-1]
      Step 4 − arr[j] = arr[j-1]
               Decrement j--
      Step 5 −  numbers[j] = copyNumber;  
   */ 

 public static void insertion () {  
            int[] numbers = {2,3,31,24,5,6,61,7,8,92};  
            for (int i = 0; i < numbers.length; i++) {  
               int copyNumber = numbers[i];   
               int j = i;  
               while (j > 0 && copyNumber < numbers[j-1]) {  
                 numbers[j] = numbers[j-1];  
                 j--;  
               }  
               numbers[j] = copyNumber;  
        }  
          
SELECTION


_______________________________________________________________


/*  
      Step 1 − Set MIN to location 0  
      Step 2 − Search the minimum element in the list  
      Step 3 − Swap with value at location MIN  
      Step 4 − Increment MIN to point to next element  
      Step 5 − Repeat until list is sorted  
   */  


QUICKSORT


_______________________________________________________________


1.PASS LOWER INDEX & HIGHER INDEX ,SAY LOWER,HIGHER
2.STORE THEM IN TWO LOCAL VARIABLES say 1,h
3.CALCULATE PIVOT
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; 
4. WHILE L
     4.1 WHILE L
     4.2 WHILE H> PIVOT, DECREMENT H
5.  IF(L
      5.1 EXCHANGE L & H
      5.2 INCREMENT L ,DECREMENT H
6. IF[LOWER
     6.1 QUICKSORT(LOWER,H)
7. IF(L
      6.1 QUICKSORT(L,HIGHER)
]
_______________________________________________________________





public class QuickSort {
  
 private int array[]; 
 private int length; 
 public void sort(int[] inputArr) { 
    if (inputArr == null || inputArr.length == 0) { 
           return; 
    } 
    this.array = inputArr; 
    length = inputArr.length; 
    quickSort(0, length - 1); 
 } 

 private void quickSort(int lowerIndex, int higherIndex) { 

 int l = lowerIndex; 
 int h = higherIndex; 

 // calculate pivot number, I am taking pivot as middle index number 
 int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; 
 // Divide into two arrays 
 while (l <= h) { 
 
   /** 
 * In each iteration, we will identify a number from left side which 
 * is greater then the pivot value, and also we will identify a number 
 * from right side which is less then the pivot value. Once the search 
 * is done, then we exchange both numbers. 
 */ 
  
 while (array[l] < pivot) { 
     l++; 
 } 
 
 while (array[h] > pivot) { 
      h--; 
 } 
 if (l <= h) { 
   exchangeNumbers(l, h); 
   //move index to next position on both sides 
   l++; 
   h--; 
 } 
 } 
 // call quickSort() method recursively 
 if (lowerIndex < h) 
   quickSort(lowerIndex, h); 
 if (l < higherIndex) 
   quickSort(l, higherIndex); 
 } 

 private void exchangeNumbers(int l, int h) { 
  int temp = array[l]; 
  array[l] = array[h]; 
  array[l] = temp; 
 } 


 public static void main(String a[]){ 

   QuickSort sorter = new QuickSort(); 
   //int[] input = {24,2,45,20,56,75,2,56,99,53,12}; 
   int[] input = {2,3,31,24,5,6,61,7,8,92};
   sorter.sort(input); 
   for(int ip:input){ 
     System.out.print(ip); 
     System.out.print(" "); 
   } 
 }  
 }

_______________________________________________________________

MERGE SORT
_______________________________________________________________

1.PASS LOWER INDEX & HIGHER INDEX ,SAY LOW,HIGH
2.CALCULATE MID , MID = LOW +(HIGH-LOW)/2
3. WHILE LOW
     2.1 SORT LEFT mergesort(low, middle)


     2.2 SORT RIGHT mergesort(middle+1, high)
     2.3 merge(low,middle,high)
  ]
5. merge(start,mid,end)

      1 Create a)tempArray, b)tempArrayIndex
      2 a) startIndex = start      2 b) midIndex = mid+1
      3 while(startIndex<=mid&& midIndex<=end)[

       IF(arr[startIndex] 

         tempArray[tempArrayIndex++] =arr[startIndex++]; 

        ELSE

            tempArray[tempArrayIndex++] = arr[midIndex++];  ]
       4.COPY REMAINING ELEMENTS
        WHILE(STARTINDEX<=MID)
         TEMPARRAY[TEMPARRAYINDEX++] = ARR[STARTINDEX++]
        WHILE(MIDINDEX<=END)
         TEMPARRAY[TEMPARRAYINDEX++] = ARR[MIDINDEX++]



       5.COPY TEMPARRAY TO ACTUAL ARRAY AFTER SORTING

/ Use of arraycopy() method

        System.arraycopy(source_arr, sourcePos, dest_arr, 

                                            destPos, len);

_______________________________________________________________




_______________________________________________________________




HEAP SORT
_______________________________________________________________






0. ITERATE OVER ARRAY & CALL HEAPIFY 


for(int i=(arr.length-1)/2; i>=0; i--){

     heapify(arr,i,arr.length-1);

      }


1.PASS ARRAY,LOWER_INDEX, HIGHER_INDEX, LENGTH
2.HEAPIFY
 2.1 LEFT = 2* LOWER_INDEX +1
 2.2 RIGHT = 2* LOWER_INDEX + 2
 2.3 DEFINE : int MAX
 2.4 IF[LEFT <= SIZE && ARR[LEFT]>ARR[LOWER_INDEX]]
      MAX = LEFT
   ELSE 
      MAX = LOWER_INDEX
2.STORE THEM IN TWO LOCAL VARIABLES say 1,h
3.CALCULATE PIVOT
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; 
4. WHILE L
     4.1 WHILE L<PIVOT, INCREMENT L
     4.2 WHILE H> PIVOT, DECREMENT H
5.  IF(L
      5.1 EXCHANGE L & H
      5.2 INCREMENT L ,DECREMENT H
6. IF[LOWER
     6.1 QUICKSORT(LOWER,H)
7. IF(L
      6.1 QUICKSORT(L,HIGHER)
8. IF()
]





















_______________________________________________________________




COUNT SORT
_______________________________________________________________





_______________________________________________________________




HEAP SORT
_______________________________________________________________









_______________________________________________________________




RADIX SORT
_______________________________________________________________




_______________________________________________________________




BINARY SEARCH
_______________________________________________________________

1.ASSUPTIO


________________________________________________________________


REFERENCES

Sequence sorting[edit]

Main article: Sorting algorithm


Subsequences[edit]Exchange Sorts

Bubble sort: for each pair of indices, swap the items if out of order
Cocktail shaker sort or bidirectional bubble sort, a bubble sort traversing the list alternately from front to back and back to front
Comb sort
Gnome sort
Odd–even sort
Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice


Humorous or ineffective

Bogosort
Stooge sort


Hybrid

Flashsort
Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level
Timsort: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7.


Insertion sorts

Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
Library sort
Patience sorting
Shell sort: an attempt to improve insertion sort
Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list
Cycle sort: in-place with theoretically optimal number of writes


Merge sorts

Merge sort: sort the first and second half of the list separately, then merge the sorted lists
Strand sort


Non-comparison sorts

Bead sort
Bucket sort
Burstsort: build a compact, cache efficient burst trie and then traverse it to create sorted output
Counting sort
Pigeonhole sort
Postman sort: variant of Bucket sort which takes advantage of hierarchical structure
Radix sort: sorts strings letter by letter


Selection sorts

Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
Smoothsort


Other

Bitonic sorter
Pancake sorting
Spaghetti sort
Topological sort


Unknown class

Samplesort