By hand. Sort the sequence 5, 6, 2, 9, 5, 1, 4, 1, 3 using quick sort, by using
ID: 3825189 • Letter: B
Question
By hand. Sort the sequence 5, 6, 2, 9, 5, 1, 4, 1, 3 using quick sort, by using the code below. Please show steps, thank you!
----------------------------------------------------------------------------------------------------
template <typename Comparable>
void quicksort( vector<Comparable> & a, int left, int right ){
//Use quick sort if we have at least four elements.
if( left + 3 <= right ){
const Comparable & pivot = median3( a, left, right );
//Begin partitioning
int i = left, j = right - 1;
for( ; ; ){
while( a[ ++i ] < pivot ) { }
while( pivot < a[ --j ] ) { }
if( i < j )
std::swap( a[ i ], a[ j ] );
else
break;
}
std::swap( a[ i ], a[ right - 1 ] ); // Restore pivot
quicksort( a, left, i - 1 ); // Sort small elements
quicksort( a, i + 1, right ); // Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort( a, left, right );
}
template <typename Comparable>
const Comparable & median3( vector<Comparable> & a, int left, int right ){
int center = ( left + right ) / 2;
if( a[ center ] < a[ left ] )
std::swap( a[ left ], a[ center ] );
if( a[ right ] < a[ left ] )
std::swap( a[ left ], a[ right ] );
if( a[ right ] < a[ center ] )
std::swap( a[ center ], a[ right ] );
// Place pivot at position right - 1
std::swap( a[ center ], a[ right - 1 ] );
return a[ right - 1 ];
}
Explanation / Answer
5 6 2 9 5 1 4 1 3
left points to 5 right points to 3
pivot = median = 5
5 6 2 9 5 1 4 1 3
as a[left] is not <5 and a[right] = 3< 5
so swap 5 and 3
3 6 2 9 5 1 4 1 5
left points to 6 and right points to 1
swap 6 and 1
3 1 2 9 5 1 4 6 5
left points to 9 and right points to 4
swap 9 and 4
3 1 2 4 5 1 9 6 5
left points to pivot element 5 and right points to 1
swap 5 and 1
3 1 2 4 1 5 9 6 5
sublist1 = 3 1 2 4 1
pivot = 5
sublist2 = 9 6 5
sublist1 = 3 1 2 4 1
3 1 2 4 1
left points to 3 ,right points to 1, pivot = 2
3 1 2 4 1
swap 3 and 1
1 1 2 4 3
sublist 11 = 1 1
pivot = 2
sublist 12 = 4 3
swap 3 and 4
3 3
combile sublists
1 1 2 3 4
pivot = 5
sublist 2 = 9 6 5
left points to 9,right points to 5, pivot = 6
swap 9 and 5
5 6 9
combine all sublists
1 1 2 3 4 5 5 6 9
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.