Java Reference
In-Depth Information
m++; // we extend left side array
}
} // place pivot now
swap(array , left ,m) ;
return m;
}
Once this partition has been done according to the pivot element, we simply
recurse on the left/right sub-arrays as follows:
Program 6.11 Recursive sorting
static void quicksort( int [ ]
array , int left , int right)
{ if (right > left)
{ int pivot=partition(array , left , right);
quicksort(array , left , pivot 1) ;
quicksort(array , pivot+1,right ) ;
}
}
static void QuickSort( int [] array)
{ quicksort(array ,0 , array . length 1) ; }
6.5.1 Complexity analysis of QuickSort
Let us analyze the running time of QuickSort on an arbitrary array of size n :
- The worst-case running time is quadratic: O ( n 2 ),
- The expected running time is O ( nlogn ),
- The best case is linear O ( n ). It is reached whenever all elements are identical.
In theoretical computer science, we furthermore analyze lower bounds, which
are time complexity bounds that can not be beaten by any algorithm. It is
known that sorting requires of the order of n log n time (comparison operations)
whatever the method/algorithm. This lower bound complexity is denoted as
follows: Ω ( n log n ).
6.6 Searching by hashing
Hashing is a fundamental technique often used in practice since it is quite a
simple technique to implement that has excellent empirical performances. The
 
Search WWH ::




Custom Search