Quick Sort in MATLAB | MATLAB Tutorial

Quick Sort in MATLAB | MATLAB Tutorial
  • Quick sort is also a divide and conquer algorithm like the merge sort hence it is also a recursive algorithm.
  • Quicksort is highly efficient algorithm and is based on partitioning the array.

Procedure:

A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the last item in the list. The role of the pivot value is to assist with splitting the list.

Make one pass through the array, called a partition step, re-arranging the entries so that:

  • the pivot is in its proper place.
  • entries smaller than the pivot are to the left of the pivot.
  • entries larger than the pivot are to its right.
  • Recursively apply quicksort to the part of the array that is to the left of the pivot, and to the right part of the array.

Example:

Given an unsorted array:

9

2

8

3

6

7

 

The element at the highest index is taken as the pivot element and we will try to place it in its correct position. So at the end of the partitioning method 7 is supposed to come into its correct position and all the elements to the left of 7 should be less than or equal to it and all the elements to the right of 7 should be greater than 7.

9

2

8

3

6

7

 

We will start with two pointers i, j. The purpose if j is it scans the list one by one and whenever j finds any element less than the last element i.e. 7 it will try to move it forward.

i

j = 9

2

8

3

6

7

 

9 is greater than 7 so no need to do anything, move j.

i

9

j = 2

8

3

6

7

 

Next 2 is less than 7. We want all the elements smaller than 7 in the starting of the list. So whenever we find an element less than the pivot we will increment i and sway it with j.

i= 9

j=2

8

3

6

7

 

i= 2

j=9

8

3

6

7

Wherever i is pointing the entire list to the left of i will contain the elements less than or equal to 7. Now j =8 which is greater than 7 so no need to do anything just increment j.

i= 2

9

j=8

3

6

7

 

Now j =8 which is greater than 7 so no need to do anything just increment j.

i= 2

9

8

j = 3

6

7

 

3 is less than 7 so again we have to increment i and then swap the elements.

2

i = 9

8

j = 3

6

7

 

2

i = 3

8

j =9

6

7

 

After swapping we again increment j.

2

i = 3

8

9

j =6

7

 

Again we compare value of j with the pivot i.e 6 < 7. So we increment i and swap i and j.

2

3

i =8

9

j =6

7

 

Swapping:

2

3

i = 6

9

j =8

7

 

As we can see that all the elements to the left of i are smaller than the pivot element. Here the algorithm would halt. We would now increment i and then swap it with pivot element.

2

3

6

i =9

j =8

7

 

Thus 7 will be in its correct position after end of 1 partitioning algorithm and all the element to its left would be smaller to it and all elements to its right would be bigger.

2

3

6

7

j =8

9

 

Now, we must apply this same procedure for two lists: 1) list to the left of 7, 2) list to the right of 7.

Hence after performing these operations we would get a completely sorted list.

 

Matlab Code:

We run this quicksort algorithm for arrays of different sizes to find the relation between the time taken by the algorithm to sort the array and the size of the array.

 

function sortedArr = quickSort(arr)

    if numel(arr) <= 1 %If the array has 1 element then it can't be sorted
        sortedArr = arr;
        return
    end

    piv = arr(end);
    arr(end) = [];

    %Create two new arrays which contain the elements that are less than or
    %equal to the pivot called "less" and greater than the pivot called
    %"greater"
    less = arr( arr <= piv ); greater = arr( arr > piv );

    %The sorted array is the concatenation of the sorted "less" array, the
    %pivot and the sorted "greater" array in that order
    sortedArr = [quickSort(less) piv quickSort(greater)];

end

Test Code:

i=1;
k = 1:100:10000;
val = zeros(1,length(j));
for j = 1:100:10000   %array size

    R = randn([1 j]); %generating array of size j containing random elements
    tic;              %starting the timer
    P = quickSort(R);%calling the Quick sort function
    val(i) =toc; %stopping the timer and creating an array of time difference
    i=i+1;

end

plot(k,val); %plotting array size vs time taken for sorting using Quick sort algorithm
grid on;
xlabel('array length');
ylabel('Time Taken in seconds');
title('Analysis Plot');
legend('Quick Sort')

Simulation Results:

 

 

Time Complexity:

  • Best Case: O (nlogn)
  • Worst Case: O (n2)
  • Average Case: O (nlogn)

Experienced Programmer skilled in Machine Learning, MATLAB, Java, MySQL, and MongoDB. Strong engineering professional persuing a Bachelor’s Degree focused in Information and Communication Technology from School of Engineering & Applied Sciences, Ahmedabad University.