java - Why is selection sort performing better than insertion AND quick sort -

i have below algorithms insertion sort, selection sort , quick sort respectively. i've run test sorting array of 10,000 integers between 0 - 1000 10 times each algorithm. curious thing average selection sort lower both insertion sort , quick sort. averages 182044.4, 217.9, , 545.4 milliseconds insertion, selection, , quick sort respectively. allowing fact can make small enhancements insertion , quick sort, wouldn't expect lack of enhancements result in such large differences. wrong in implementation here? again, not small enhancements such moving indices or checks, actual errors.

i've provided, code tests , results below

thanks

public final static <e extends comparable<e>> arraylist<e> insertionsort(arraylist<e> arr) {     for(int = 1; < arr.size(); i++)     {         for(int j = i; j > 0; j--)         {             if(arr.get(j).compareto(arr.get(j - 1)) < 0)             {                 swap(arr, j, j-1);             }else{                 break;             }         }     }            return arr; } 

`

public final static <e extends comparable<e>> arraylist<e> selectionsort(arraylist<e> arr)     {         for(int = 0; < arr.size() - 1; i++){             int min = i;             for(int j = + 1; j < arr.size(); j++){                 if(arr.get(j).compareto(arr.get(min)) < 0){                     min = j;                 }             }             swap(arr, i, min);         }         return arr;     }` 

`

public final static <e extends comparable<e>> arraylist<e> quicksort(arraylist<e> arr)     {         quicksort(arr, 0, arr.size() -1);         return arr;     }     private static <e extends comparable<e>> void quicksort(arraylist<e> arr, int lo, int hi)     {         if(hi - lo < 1)         {             return;         }         if((hi - lo) == 1)         {             if(arr.get(lo).compareto(arr.get(hi)) > 0)             {                 swap(arr, lo, hi);             }             return;         }         int pivot = (hi - lo) / 2 + lo;         int j;         swap(arr, pivot, hi);         pivot = hi;         for(int = lo; < pivot; i++)         {             if(arr.get(i).compareto(arr.get(pivot)) > 0 )             {                 for(j = + 1; j < pivot; j++)                 {                     if(arr.get(j).compareto(arr.get(pivot)) < 0)                     {                         swap(arr, i, j);                         break;                     }                 }                 if(j == pivot)                 {                     swap(arr, i, pivot);                     pivot = i;                 }             }         }         //do sort op here         quicksort(arr, lo, pivot - 1);         quicksort(arr, pivot + 1, hi);     } 

`

the code test - genrans(n) generates array list of random numbers between 0 , n ` int n = 10000; arraylist list = new arraylist();

    int tries = 10;     double[] times = new double[tries];     double sum = 0;     double time = 0;     long starttime = 0;     long endtime = 0;      for(int = 0; < tries; i++)     {         list = genrans(n);         starttime = system.nanotime();         //system.out.println("before " + list);         sort.selectionsort(list);         //system.out.println("after" + list);         endtime = system.nanotime();          time = (endtime - starttime) / 1000000;          times[i] = time;          sum += time;      }      system.out.println("times selection sort = " + arrays.tostring(times));     system.out.println("avg time selection = " + sum / tries);     sum = 0;      for(int = 0; < tries; i++)     {         list = genrans(n);         starttime = system.nanotime();         sort.insertionsort(list);         endtime = system.nanotime();          time = (endtime - starttime) / 1000000;          times[i] = time;          sum += time;      }      system.out.println("times insertion sort = " + arrays.tostring(times));     system.out.println("avg time insertion = " + sum / tries);     sum = 0;      for(int = 0; < tries; i++)     {         list = genrans(n);         starttime = system.nanotime();         sort.quicksort(list);         endtime = system.nanotime();          time = (endtime - starttime) / 1000000;          times[i] = time;          sum += time;      }      system.out.println("times quick sort = " + arrays.tostring(times));     system.out.println("avg time quick = " + sum / tries); } 

` results: times selection sort = [235.0, 214.0, 216.0, 216.0, 216.0, 216.0, 217.0, 216.0, 217.0, 216.0] avg time selection = 217.9 times insertion sort = [182936.0, 181976.0, 182571.0, 182448.0, 180757.0, 180567.0, 181593.0, 185073.0, 181241.0, 181282.0] avg time insertion = 182044.4 times quick sort = [629.0, 487.0, 579.0, 557.0, 547.0, 482.0, 543.0, 571.0, 525.0, 534.0] avg time quick = 545.4

your quicksort partitioning step quadratic-time, , buggy.

when find i such arr[i] > arr[pivot], you're scanning forward i+1 find position j swap with: result in same array elements being skipped on many times. suppose first n/2 items > arr[pivot], , rest < arr[pivot]: each of first n/2 iterations of outer loop (that increments i) necessitate n/2 iterations of inner loop increments j find partner swap with, o(n^2) iterations overall.

also if can't find partner j swap i with, swap pivot position i. means if there more values above pivot below it, pivot wind in wrong location -- after values less have been exhausted (as partners swapping values greater it), keep sliding right.