Quick Sort

3BSA

Quick Sort

Sorting algorithm

start

Introduction

index

History

Explanation

Code

Compexity

01

Introduction

Divide et impera

01

Explanation

Pivot, divide et impera...

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.

01

Divide et impera

What is divide et impera?

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.

This algorithm solves problems in three fundamental steps:

Impera

Combine

Divide

Solves recursively the problems obtained

Correct combination of answers

Divide the problems in more under problems

02

History

Tony Hoare

02

Tony Hoare

L'ideatore del quick sort

1959

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

more

04

Biography

Tony Hoare

Professor

Degree

LAGOL

In 2000 he was nominated professor at Oxford and still is

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

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

1980-1985

1934

1959

1956-1958

1960

2000

Birth

Quick Sort

First prizes

11/01/1934, from English parents

He devises quicksort, which will make his name famous

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

03

Explanation

Graphic example

03

Explanation

Graphic example

PIVOT

03

Explanation

Graphic example

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

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

PIVOT

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

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

03

Explanation

Graphic example

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

PIVOT

NO !! Let's stop the counter.

03

Explanation

Graphic example

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

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

PIVOT

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

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

03

Explanation

Graphic example

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

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

PIVOT

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

NO !! Lets' stop the counter.

03

Explanation

Graphic example

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

PIVOT

03

Explanation

Graphic example

PIVOT

Let's swap the pivot with the cell Q

03

Explanation

Graphic example

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

PIVOT

04

Code

Language C++

04

Code

Print

04

Code

Populate

04

Code

Swap

04

Code

Find pivot 1

04

Code

Find Pivot 2

04

Code

Quick Sort

04

Code

Main

05

Complexity

Logarithmic

03

Complexity cases

Write a subtitle here

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

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

Asymptomatic analysis:

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

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.

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)

Lorem ipsum dolor sit amet

05

Dependance on input data

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

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

The best

Average

The worst

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.

Main sorting algorithms

Aim

Lorem ipsum dolor sit amet

04

Complexity Cases

All

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

05

Complexity of Quick Sort

Average case

Best case

Worst case

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

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

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

Lorem ipsum dolor sit amet

05

Graphic

O=n*log2n

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.