683 views
0 votes
0 votes

. Write Quicksort Algorithm using last element as pivot element. Apply this algorithm to sort the  following list of array element. Show action step by step.  

23, 12, -7, 16, 18, 35, 35, 28, 5 

1 Answer

1 votes
1 votes

Source Code: https://github.com/YamanSahu/Quick-Sort/blob/main/quickSort.cpp

Output : 

Initial Array
0  1  2  3  4  5  6  7  8  
23 12 -7 16 18 35 35 28 5 

--------------  Quick Sort  --------------

        QuickSort(arr, 0, 8) 
Pivot element : 5
i = -1 j = 0 arr[0] < 5: False

0  1  2  3  4  5  6  7  8  
23 12 -7 16 18 35 35 28 5 

i = -1 j = 1 arr[1] < 5: False

0  1  2  3  4  5  6  7  8  
23 12 -7 16 18 35 35 28 5 

i = -1 j = 2 arr[2] < 5: True
i = i + 1
 swap (arr[i] , arr[j])

0  1  2  3  4  5  6  7  8  
-7 12 23 16 18 35 35 28 5 

i = 0 j = 3 arr[3] < 5: False

0  1  2  3  4  5  6  7  8  
-7 12 23 16 18 35 35 28 5 

i = 0 j = 4 arr[4] < 5: False

0  1  2  3  4  5  6  7  8  
-7 12 23 16 18 35 35 28 5 

i = 0 j = 5 arr[5] < 5: False

0  1  2  3  4  5  6  7  8  
-7 12 23 16 18 35 35 28 5 

i = 0 j = 6 arr[6] < 5: False

0  1  2  3  4  5  6  7  8  
-7 12 23 16 18 35 35 28 5 

i = 0 j = 7 arr[7] < 5: False

0  1  2  3  4  5  6  7  8
-7 12 23 16 18 35 35 28 5

(arr[i+1] , arr[right])

0  1  2  3  4  5  6  7  8
-7 5 23 16 18 35 35 28 12


--------------

Partion position : 1
QuickSort(arr, 0, 0)
QuickSort(arr, 2, 8)
Pivot element : 12
i = 1 j = 2 arr[2] < 12: False

0  1  2  3  4  5  6  7  8
-7 5 23 16 18 35 35 28 12

i = 1 j = 3 arr[3] < 12: False

0  1  2  3  4  5  6  7  8
-7 5 23 16 18 35 35 28 12

i = 1 j = 4 arr[4] < 12: False

0  1  2  3  4  5  6  7  8
-7 5 23 16 18 35 35 28 12 

i = 1 j = 5 arr[5] < 12: False

0  1  2  3  4  5  6  7  8
-7 5 23 16 18 35 35 28 12

i = 1 j = 6 arr[6] < 12: False

0  1  2  3  4  5  6  7  8
-7 5 23 16 18 35 35 28 12 

i = 1 j = 7 arr[7] < 12: False

0  1  2  3  4  5  6  7  8
-7 5 23 16 18 35 35 28 12

(arr[i+1] , arr[right])

0  1  2  3  4  5  6  7  8
-7 5 12 16 18 35 35 28 23


--------------

Partion position : 2
QuickSort(arr, 2, 1)
QuickSort(arr, 3, 8)
Pivot element : 23
i = 2 j = 3 arr[3] < 23: True
i = i + 1
 swap (arr[i] , arr[j])

0  1  2  3  4  5  6  7  8
-7 5 12 16 18 35 35 28 23

i = 3 j = 4 arr[4] < 23: True
i = i + 1
 swap (arr[i] , arr[j])

0  1  2  3  4  5  6  7  8
-7 5 12 16 18 35 35 28 23

i = 4 j = 5 arr[5] < 23: False

0  1  2  3  4  5  6  7  8
-7 5 12 16 18 35 35 28 23

i = 4 j = 6 arr[6] < 23: False

0  1  2  3  4  5  6  7  8
-7 5 12 16 18 35 35 28 23

i = 4 j = 7 arr[7] < 23: False

0  1  2  3  4  5  6  7  8
-7 5 12 16 18 35 35 28 23 

(arr[i+1] , arr[right])

0  1  2  3  4  5  6  7  8
-7 5 12 16 18 23 35 28 35


--------------

Partion position : 5
QuickSort(arr, 3, 4)
Pivot element : 18
-7 5 12 16 18 23 28 35 35

(arr[i+1] , arr[right])

0  1  2  3  4  5  6  7  8
-7 5 12 16 18 23 28 35 35


--------------

Partion position : 7
QuickSort(arr, 6, 6)
QuickSort(arr, 8, 8)
--------------  Quick Sort Completed --------------
Final Array
0  1  2  3  4  5  6  7  8
-7 5 12 16 18 23 28 35 35
PS E:\my program\ada\Sorting\Quick Sort> 

Related questions

0 votes
0 votes
1 answer
2
Edwees asked Feb 6, 2017
1,895 views
We have a list of pairs [("Tariq",71),("Brinda",85),("Shweta",71),("Sunita",85),("Salma",72),("Uday",60)], where each pair consists of a student's name and his/her marks ...