Quick Sort

Sorting algorithm

start

Quick Sort

3BSA

Compexity

Code

Explanation

Introduction

History

index

Divide et impera

Introduction

01

What does it use?

Quick sort takes advantage of the "pivot", an element placed in a data structure where the minor elements are placed on the left and the major ones on the right. In addition, the divide et impera approach is essential for quick sort.

What is it?

Quicksort is an unstable in-place recursive sorting algorithm.

Pivot, divide et impera...

Explanation

01

This algorithm solves problems in three fundamental steps:

Divide et impera is a method that consists in dividing an initial problem into two or more simple sub-problems, easier to resolve. After that, sub-problem solutions must be combined in order to obtain the final result.

Combine

Correct combination of answers

Impera

Solves recursively the problems obtained

Divide

Divide the problems in more under problems

What is divide et impera?

Divide et impera

01

Tony Hoare

History

02

more

The birth of the algorithm that even today is among the most efficient and used

1959

L'ideatore del quick sort

Tony Hoare

02

2000

In 2000 he was nominated professor at Oxford and still is

Professor

1980-1985

Turing award from the association of computer machines. In 1985 he received the Faraday medal

First prizes

1960

Starts working for L'Ellie Brother Ltd (LAGOL) )

LAGOL

1959

He devises quicksort, which will make his name famous

Quick Sort

1956-1958

He graduated in 1956. In the same year, until 1958, he served in the navy

Degree

1934

11/01/1934, from English parents

Birth

Tony Hoare

Biography

04

Graphic example

Explanation

03

PIVOT

Graphic example

Explanation

03

YES!!Let's move j by one position.

Let's continue with i:Is the pivot 2 greater or equal. to the array element at index i?

YES!! Let's move j by one position.

Let's start from i:Is the pivot 2 greater or equal to the array element at index i?

PIVOT

Graphic example

Explanation

03

NO !! Let's stop the counter.

Let's continue again with i:Is the pivot 2 greater or equal to the array element at index i?

PIVOT

Graphic example

Explanation

03

YES!! Let's move j by one position.

Let's continue with j:Is the pivot 2 less than j=4 ?

YES!! Let's move j by one position.

Let's move on to j:Is the pivot 2 less than j=3 ?

PIVOT

Graphic example

Explanation

03

NO !! Lets' stop the counter.

Let's continue with j:Is the pivot 2 less than j=1 ?

YES!! Let's move j by one position.

Let's move on to j:Is the pivot 2 less than j=5 ?

PIVOT

Graphic example

Explanation

03

The stop condition has occurred: i<j = NOThe counters are respectively i=2 and j=1

PIVOT

Graphic example

Explanation

03

Let's swap the pivot with the cell Q

PIVOT

Graphic example

Explanation

03

Now the procedure is analogous to the previous arrays, until we'll get to arrays composed by a single cell.

PIVOT

Graphic example

Explanation

03

Language C++

Code

04

Print

Code

04

Populate

Code

04

Swap

Code

04

Find pivot 1

Code

04

Find Pivot 2

Code

04

Quick Sort

Code

04

Main

Code

04

Logarithmic

Complexity

05

However, it is a tool of mathematics, so to be able to use it youu have to transform the execution time of the algorithm into one of function T(n) as a function of the size n of the input data

At this point I can consider the most significant (highest) value as representive of the complexity of the algorithm. The result willl be O(n2)

You can calculate the complexity of an algorithm with the following method: once you calculate the execution number for each line of code, you can calculate the asymptomatic cost directly on each line.

T(n)= O(f(n))

Asymptomatic analysis:

The execution of a program involves an economic cost due to the use of resources, we generally speak of:

Lorem ipsum dolor sit amet

Write a subtitle here

Complexity cases

03

Main sorting algorithms

In the analysis of an algorithm the worst case is always used because it is the one that measures well its efficiency from a technical point of view.

Aim

Average

The worst

The best

In these situations it is necessary to distinguish three different cases:

Lorem ipsum dolor sit amet

How we calculate it

It often happens that the cost of an algorithm depends not only on the size of the input data, but also on their particular verbs

Dependance on input data

05

This table shows all the main results of the complexity calculation

The number of comparisons to search for an element of an array of size n is O(n).

Lorem ipsum dolor sit amet

All

Complexity Cases

04

The random choice of the pivot makes it probable that it will be divided into 2 parts having approximately the same number of elements.

Average case

At each step a pivot is chosen such that a subvector has length 0 n-1 activations of quick sort.

Worst case

At each step a pivot is chosen such that the vector halves, log2n quicksort activations.

Best case

Lorem ipsum dolor sit amet

Complexity of Quick Sort

05

O=n*log2n

After doing all the calculations, the Quick Sort has the complexity n*log2n.

• The independent variable x represents the number of data we want to sort.
• The dependent variable y represents the average number of steps in the algorithm.
• If we take our code as an example, with 10 elements to sort, the algorithm will have to make an average of 33.21 steps.

O=n*log2n

Graphic

05