View
216
Download
0
Category
Preview:
Citation preview
Projeto e Análise
Aula 1: Algoritmos
Prof. Carlos de Terças-feiras, 8h20
Análise de Algoritmos
Algoritmos de Ordenação
Prof. Carlos de Salles, 8h20 às 11h10
Algoritmos de
• Insertsort
• Mergesort
• Heapsort
• Quicksort• Quicksort
de Ordenação
Algoritmos de
� Dado um vetor v com Nordenação consiste em organizar todos esses N elementos em uma ordem (nãonão-decrescente etc)
� Exemplo:
� v = {1, 9, 8, 5, 3, 7, 4}
− Depois de ordenado de forma não
− v = {1, 3, 4, 5, 7, 8, 9}
de Ordenação
N elementos, a ordenação consiste em organizar todos esses
elementos em uma ordem (não-crescente,
Depois de ordenado de forma não-decrescente, v fica:
Insert Sort
� Outros nomes:
� Bubble sort
� Selection sort
� Consite em posicionar� Consite em posicionarelemento em seu lugarconsecutivas
Insert Sort
o menor ou o maioro menor ou o maiorlugar correto N vezes
Insert Sort
for i=1,N do
for j=i+1,N do
if v[i]>v[j]
v[i],v[j] = v[j],v[v[i],v[j] = v[j],v[
end
end
end
Insert Sort
]>v[j] then
],v[j] = v[j],v[i]],v[j] = v[j],v[i]
Insert Sort
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort
1 9 8 5 3 7 41 9 8 5 3 7 4
Insert Sort
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort
1 9 8 5 3 7 41 9 8 5 3 7 4
Insert Sort
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort
1 9 8 5 3 7 41 9 8 5 3 7 4
Insert Sort
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort
1 9 8 5 3 7 41 9 8 5 3 7 4
Insert Sort
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort
1 9 8 5 3 7 41 9 8 5 3 7 4
Insert Sort
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort
1 9 8 5 3 7 41 9 8 5 3 7 4
j
Insert Sort
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort
5 3 7 45 3 7 4
Insert Sort
1 8 9 5 3 7 4
i
1 8 9 5 3 7 4
j
Insert Sort
3 7 43 7 4
Insert Sort
1 5 9 8 3 7 4
i
1 5 9 8 3 7 4
j
Insert Sort
7 47 4
Insert Sort
1 3 9 8 5 7 4
i
1 3 9 8 5 7 4
j
Insert Sort
1 3 9 8 5 7 41 3 9 8 5 7 4
Insert Sort
1 3 9 8 5 7 4
i
1 3 9 8 5 7 4
j
Insert Sort
1 3 9 8 5 7 41 3 9 8 5 7 4
j
Insert Sort
1 3 9 8 5 7 4
i
1 3 9 8 5 7 4
j
Insert Sort
5 7 45 7 4
Insert Sort
1 3 8 9 5 7 4
i
1 3 8 9 5 7 4
j
Insert Sort
7 47 4
Insert Sort
1 3 5 9 8 7 4
i
1 3 5 9 8 7 4
j
Insert Sort
1 3 5 9 8 7 41 3 5 9 8 7 4
Insert Sort
1 3 5 9 8 7 4
i
1 3 5 9 8 7 4
j
Insert Sort
44
j
Insert Sort
1 3 4 9 8 7 5
i
1 3 4 9 8 7 5
j
Insert Sort
7 57 5
Insert Sort
1 3 4 8 9 7 5
i
1 3 4 8 9 7 5
j
Insert Sort
55
Insert Sort
1 3 4 7 9 8 5
i
1 3 4 7 9 8 5
j
Insert Sort
55
j
Insert Sort
1 3 4 5 9 8 7
i
1 3 4 5 9 8 7
j
Insert Sort
77
Insert Sort
1 3 4 5 8 9 7
i
1 3 4 5 8 9 7
j
Insert Sort
77
j
Insert Sort
1 3 4 5 7 9 8
i
1 3 4 5 7 9 8
j
Insert Sort
9 89 8
j
Insert Sort
1 3 4 5 7 8 91 3 4 5 7 8 9
Insert Sort
1 3 4 5 7 8 91 3 4 5 7 8 9
Insert Sort
1 3 4 5 7 8 91 3 4 5 7 8 9Número de operações:
(N-1) + (N-2) + (N-3) + … + 3 + 2 + 1
N*(N-1)2
Insert Sort
1 3 4 5 7 8 91 3 4 5 7 8 9Número de operações:
3) + … + 3 + 2 + 1
1)
Insert Sort
� Ideia:
� Se o vetor já estiver ordenadointeração, seria interessantealgoritmo.
Como detecto se um vetor� Como detecto se um vetor
ordenado = true
for i=1,N do
if v[i]>v[i+1] then ordenado
end
Insert Sort
ordenado em algumainteressante detectar isso e parar o
vetor está ordenado?vetor está ordenado?
ordenado = false end
Insert Sort (
for i=N,2,-1 do
trocas = false
for j=1,i-1 do
if v[j]>v[j+1] then
v[j],v[j+1] = v[j+1],v[j]v[j],v[j+1] = v[j+1],v[j]
trocas = true
end
end
if not trocas then break
end
Insert Sort (melhoria)
then
v[j],v[j+1] = v[j+1],v[j]v[j],v[j+1] = v[j+1],v[j]
break end
Insert Sort (
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort (melhoria)
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
Insert Sort (
1 9 8 5 3 7 4
i
1 9 8 5 3 7 4
j
Insert Sort (melhoria)
5 3 7 4
i
5 3 7 4
Insert Sort (
1 8 9 5 3 7 4
i
1 8 9 5 3 7 4
j
Insert Sort (melhoria)
3 7 4
i
3 7 4
Insert Sort (
1 8 5 9 3 7 4
i
1 8 5 9 3 7 4
j
Insert Sort (melhoria)
7 4
i
7 4
Insert Sort (
1 8 5 3 9 7 4
i
1 8 5 3 9 7 4
j
Insert Sort (melhoria)
4
i
4
Insert Sort (
1 8 5 3 7 9 4
i
1 8 5 3 7 9 4
j
Insert Sort (melhoria)
9 4
i
9 4
Insert Sort (
1 8 5 3 7 4 9
i
1 8 5 3 7 4 9
j
Insert Sort (melhoria)
1 8 5 3 7 4 91 8 5 3 7 4 9
Insert Sort (
1 8 5 3 7 4 9
i
1 8 5 3 7 4 9
j
Insert Sort (melhoria)
3 7 4 93 7 4 9
Insert Sort (
1 5 8 3 7 4 9
i
1 5 8 3 7 4 9
j
Insert Sort (melhoria)
7 4 97 4 9
Insert Sort (
1 5 3 8 7 4 9
i
1 5 3 8 7 4 9
j
Insert Sort (melhoria)
4 94 9
Insert Sort (
1 5 3 7 8 4 9
i
1 5 3 7 8 4 9
j
Insert Sort (melhoria)
99
Insert Sort (
1 5 3 7 4 8 9
i
1 5 3 7 4 8 9
j
Insert Sort (melhoria)
1 5 3 7 4 8 91 5 3 7 4 8 9
Insert Sort (
1 5 3 7 4 8 9
i
1 5 3 7 4 8 9
j
Insert Sort (melhoria)
7 4 8 97 4 8 9
Insert Sort (
1 3 5 7 4 8 9
i
1 3 5 7 4 8 9
j
Insert Sort (melhoria)
1 3 5 7 4 8 91 3 5 7 4 8 9
Insert Sort (
1 3 5 7 4 8 9
i
1 3 5 7 4 8 9
j
Insert Sort (melhoria)
8 98 9
Insert Sort (
1 3 5 4 7 8 9
i
1 3 5 4 7 8 9
j
Insert Sort (melhoria)
7 8 97 8 9
Insert Sort (
1 3 5 4 7 8 9
i
1 3 5 4 7 8 9
j
Insert Sort (melhoria)
7 8 97 8 9
Insert Sort (
1 3 5 4 7 8 9
i
1 3 5 4 7 8 9
j
Insert Sort (melhoria)
7 8 97 8 9
Insert Sort (
1 3 4 5 7 8 9
i
1 3 4 5 7 8 9
j
Insert Sort (melhoria)
1 3 4 5 7 8 91 3 4 5 7 8 9
Insert Sort (
1 3 4 5 7 8 9
i
1 3 4 5 7 8 9
j
Insert Sort (melhoria)
1 3 4 5 7 8 91 3 4 5 7 8 9
Insert Sort (
1 3 4 5 7 8 91 3 4 5 7 8 9
Insert Sort (melhoria)
1 3 4 5 7 8 91 3 4 5 7 8 9
Mergesort
� Ordena inicialmente subou 2 e recursivamente dobra esse tamanho até ordenar o vetor total de tamanho N
� Baseia-se no merge de dois vetores ordenadosBaseia-se no merge de dois vetores ordenados
Mergesort
Ordena inicialmente sub-vetores de tamanho 1 ou 2 e recursivamente dobra esse tamanho até ordenar o vetor total de tamanho N
se no merge de dois vetores ordenadosse no merge de dois vetores ordenados
Merge de dois vetores ordenados
� Dados dois vetores V1 e V2, já ordenados, o merge cria um outro vetor V ordenado com os elementos de V1 e V2
local i,j,k = 1,1,1
for k=1,#v1+#v2 do
if j>#v2 then v[k]=v1[i]; i=i+1
else if i>#v1 then v[k]=v2[j]; j=j+1
else if v1[i]<=v2[j] then
else v[k]=v2[j]; j=j+1 end
end
Merge de dois vetores ordenados
Dados dois vetores V1 e V2, já ordenados, o cria um outro vetor V ordenado com os
v[k]=v1[i]; i=i+1
v[k]=v2[j]; j=j+1
then v[k]=v1[i]; i=i+1
end
Merge de dois vetores
1 3V1=
i
j
5 7V2=
V= 1
k
Merge de dois vetores
3 7 18 20
7 8 11 13
Merge de dois vetores
1 3V1=
i
j
5 7V2=
V= 1 3
k
Merge de dois vetores
3 7 18 20
7 8 11 13
Merge de dois vetores
1 3V1=j
5 7V2=
V= 1 3 5
k
Merge de dois vetores
3 7 18 20
i
7 8 11 13
Merge de dois vetores
1 3V1=j
5 7V2=
V= 1 3 5 7
k
Merge de dois vetores
3 7 18 20
i
7 8 11 13
Merge de dois vetores
1 3V1=j
5 7V2=
V= 1 3 5 7
Merge de dois vetores
3 7 18 20
i
7 8 11 13
7
k
Merge de dois vetores
1 3V1=
5 7V2=
V= 1 3 5 7
Merge de dois vetores
3 7 18 20
i
j
7 8 11 13
7 8
k
Merge de dois vetores
1 3V1=
5 7V2=
V= 1 3 5 7
Merge de dois vetores
3 7 18 20
i
j
7 8 11 13
7 8 11
k
Merge de dois vetores
1 3V1=
5 7V2=
V= 1 3 5 7
Merge de dois vetores
3 7 18 20
i
j
7 8 11 13
7 8 11 13
k
Merge de dois vetores
1 3V1=
5 7V2=
V= 1 3 5 7
Merge de dois vetores
3 7 18 20
i
j
7 8 11 13
7 8 11 13 18
k
Merge de dois vetores
1 3V1=
5 7V2=
V= 1 3 5 7
Merge de dois vetores
3 7 18 20
i
j
7 8 11 13
7 8 11 13 18 20
k
Merge de dois vetores
1 3V1=
5 7V2=
V= 1 3 5 7
Merge de dois vetores
3 7 18 20
i
j
7 8 11 13
7 8 11 13 18 20
k
Mergesort
1 9 8 5 3 7 4
Mergesort
1 9 8 5 3 7 4
Mergesort
1 9 8 5 3 7 4
1 9 8 5
Mergesort
1 9 8 5 3 7 4
3 7 4
Mergesort
1 9 8 5 3 7 4
1 9 8 5
1 9 8 51 9 8 5
Mergesort
1 9 8 5 3 7 4
3 7 4
Mergesort
1 9 8 5 3 7 4
1 9 8 5
1 9 5 81 9 5 8
Mergesort
1 9 8 5 3 7 4
3 7 4
Mergesort
1 9 8 5 3 7 4
1 5 8 9
Mergesort
1 9 8 5 3 7 4
3 7 4
Mergesort
1 9 8 5 3 7 4
1 5 8 9
Mergesort
1 9 8 5 3 7 4
3 7 4
Mergesort
1 9 8 5 3 7 4
1 5 8 9
Mergesort
1 9 8 5 3 7 4
3 7 4
3 7 43 7 4
Mergesort
1 9 8 5 3 7 4
1 5 8 9
Mergesort
1 9 8 5 3 7 4
3 7 4
3 7 43 7 4
Mergesort
1 9 8 5 3 7 4
1 5 8 9
Mergesort
1 9 8 5 3 7 4
3 4 7
Mergesort
1 3 4 5 7 8 9
Mergesort
1 3 4 5 7 8 9
Mergesort -
1 9 8 5 3 7 4
1 9 8 5
1 9 8 51 9 8 5
- operações
1 9 8 5 3 7 4
3 7 4
3 7 43 7 4
Mergesort -
1 9 8 5 3 7 4
1 9 8 5
1 9 8 51 9 8 5
Total de operações:N * log
N operações em cada nível
- operações
1 9 8 5 3 7 4
3 7 4
3 7 4
log2 N
níveis
3 7 4
Total de operações:N * log
2 N
N operações em cada nível
Heapsort
� Ordenação baseada na estrutura de dados heap
� A heap é um vetor que pode ser visto como uma árvore binária completa
� Cada nó da árvore equivale a um valor no vetor
Heapsort
Ordenação baseada na estrutura de dados
é um vetor que pode ser visto como uma árvore binária completa
Cada nó da árvore equivale a um valor no vetor
Primitivas da Heap
� length(V)
� número de elementos no vetor V
� heap-size(V)
� número de elementos da � número de elementos da vetor V
Primitivas da Heap
número de elementos no vetor V
número de elementos da heap armazenados no número de elementos da heap armazenados no
Vetor Heap – primitivas de árvore
� parent(i)
� return i/2
� left(i)
� return 2i� return 2i
� right(i)
� return 2i+1
primitivas de árvore
Heap como um vetor
1 9 8 5
1
9
5 3
Heap como um vetor
5 3 7 4
1
8
7 4
Propriedade da Heap
� Para cada nó i que não seja a raiz, então:
� V[ parent(i) ] >= V[i]
� Exemplo:
99
5
1 3
Propriedade da Heap
Para cada nó i que não seja a raiz, então:
99
8
7 4
Primitiva Heapify
� Função para manter a propriedade da heapfunction heapify(V, i)
l = left(i)
r = right(i)
if l<=heap-size(V) and V[l]>V[i] if l<=heap-size(V) and V[l]>V[i] else largest = i end
if r<=heap-size(V) and V[r]>V[largest] then largest=r end
if largest != i thenV[i], V[largest] = V[largest], V[i]heapify(V, largest)
end
end
Primitiva Heapify
Função para manter a propriedade da heap
V[l]>V[i] then largest = lV[l]>V[i] then largest = l
V[r]>V[largest]
V[i], V[largest] = V[largest], V[i]
Construindo uma Heap
� Primitiva que constrói uma vetor de N elementos
function build_heap
heap-size(V) = lengthheap-size(V) = length
for i=length(V)/2,1,
heapify(V,i)
end
end
Construindo uma Heap
Primitiva que constrói uma heap a partir de um
build_heap(V)
length(V) -- #Vlength(V) -- #V
(V)/2,1,-1 do
Construindo uma Heap
1 9 8 5
1
9
5 3
Construindo uma Heap
5 3 7 4
1i
8
7 4
heapify
Construindo uma Heap
1 9 8 5
1i
9
5 3
heapify
Construindo uma Heap
5 3 7 4
1
8
7 4
Construindo uma Heap
1 9 8 5
1i
9
5 3
i
Construindo uma Heap
5 3 7 4
1i
heapify
8
7 4
i
Construindo uma Heap
9 1 8 5
9i
1
5 3
iheapify
Construindo uma Heap
5 3 7 4
9i
8
7 4
i
Construindo uma Heap
9 5 8 1
9i
5
1 3
i
heapify
Construindo uma Heap
1 3 7 4
9i
8
7 4
i
Construindo uma Heap
9 5 8 1
9
5
1 3
Construindo uma Heap
1 3 7 4
9
8
7 4
Heapsort
function heapsort(V)
for i=length(V),2,
V[1], V[i] = V[i], V[1]
heap-size(V) = heap-size(V) =
1
heapify(V,1)
end
end
Heapsort
heapsort(V)
(V),2,-1 do
V[1], V[i] = V[i], V[1]
(V) = heap-size(V)-(V) = heap-size(V)-
(V,1)
Heapsort
9 5 8 1
9
5
1 3
Heapsort
1 3 7 4
9
8
7 4
i
Heapsort
4 5 8 1
4
5
1 3
Heapsort
1 3 7 9
4 heapify
8
7 9
i
Heapsort
8 5 4 1
8
5
1 3
Heapsort
1 3 7 9
8
4
7 9
iheapify
Heapsort
8 5 7 1
8
5
1 3
Heapsort
1 3 4 9
8
7
4 9
i
heapify
Heapsort
8 5 7 1
8
5
1 3
Heapsort
1 3 4 9
8
7
4 9
i
Heapsort
4 5 7 1
4
5
1 3
Heapsort
1 3 8 9
4 heapify
7
8 9
i
Heapsort
7 5 4 1
7
5
1 3
Heapsort
1 3 8 9
7
4
8 9
iheapify
Heapsort
7 5 4 1
7
5
1 3
i
Heapsort
1 3 8 9
7
4
8 9
Heapsort
3 5 4 1
3
5
1 7
i
Heapsort
1 7 8 9
3 heapify
4
8 9
Heapsort
5 3 4 1
5
3
1 7
iheapify
Heapsort
1 7 8 9
5
4
8 9
Heapsort
5 3 4 1
5
3
1 7
i
Heapsort
1 7 8 9
5
4
8 9
Heapsort
1 3 4 5
1
3
5 7
i
Heapsort
5 7 8 9
1 heapify
4
8 9
Heapsort
4 3 1 5
4
3
5 7
i
Heapsort
5 7 8 9
4
1
8 9
heapify
Heapsort
4 3 1 5
4
3
5 7
Heapsort
5 7 8 9
4i
1
8 9
i
Heapsort
1 3 4 5
1
3
5 7
Heapsort
5 7 8 9
1 heapify
i
4
8 9
i
Heapsort
3 1 4 5
3
1
5 7
heapify
Heapsort
5 7 8 9
3i
4
8 9
i
Heapsort
3 1 4 5
3i
1
5 7
i
Heapsort
5 7 8 9
3
4
8 9
Heapsort
1 3 4 5
1i
3
5 7
i
Heapsort
5 7 8 9
1 heapify
4
8 9
Heapsort
1 3 4 5
1
3
5 7
Heapsort
5 7 8 9
1
4
8 9
Operações do Heapsort
1 3 4 5
1
3
5 7
N-1 (i varia de 1 a N
Operações do Heapsort
5 7 8 9
1
4
8 9
log2N
(heapify –depende da
altura da heap)
(i varia de 1 a N-1)
Operações do Heapsort
1 3 4 5
1Total de operações:
3
5 7
N-1 (i varia de 1 a N
operações:(N-1) * log
2N
Operações do Heapsort
5 7 8 9
1
4
8 9
log2N
(heapify –depende da
altura da heap)
(i varia de 1 a N-1)
Quicksort
� Ordena o vetor particionando recursivamente
� A cada iteração, localiza a posição final de um elemento aleatório (pivôem duas partes para prosseguir a ordenaçãoem duas partes para prosseguir a ordenação
Quicksort
Ordena o vetor particionando recursivamente
A cada iteração, localiza a posição final de um pivô) e subdivide o vetor
em duas partes para prosseguir a ordenaçãoem duas partes para prosseguir a ordenação
Partição
� Localiza a posição final do aleatório do vetor) e divide o vetor em duas partes, garantindo:
� Todos os elementos à esquerda do pivô são menores ou iguais a elemenores ou iguais a ele
� Todos os elementos à direita do pivô são que ele
Partição
Localiza a posição final do pivô (um elemento aleatório do vetor) e divide o vetor em duas
Todos os elementos à esquerda do pivô são a elea ele
Todos os elementos à direita do pivô são maiores
Partiçãofunction partition(V, left, right)
pivot = V[left]i = left-1
j = right+1while true do
repeat j=j-1 untilrepeat i=i+1 untilrepeat i=i+1 until
if i<j thenV[i], V[j] = V[j], V[i]
else
return jend
end
end
Partiçãopartition(V, left, right)
until V[j]<=pivotuntil V[i]>=pivotuntil V[i]>=pivot
V[i], V[j] = V[j], V[i]
Quicksort
function quicksort(V, left, right)
if left<right then
middle = partition
quicksort(V, left, middle)(V, left, middle)
quicksort(V, middle+1, right)
end
end
Quicksort
quicksort(V, left, right)
partition(V, left, right)
(V, left, middle)(V, left, middle)
(V, middle+1, right)
Quicksort - quicksort
5 9 8 11 2 3 4 5 6 7
quicksort(1,7)
1 3 7 41 2 3 4 5 6 7
Quicksort - partition
5 9 8 1i
partition(1,7)
1 3 7 4j
Quicksort - partition
5 9 8 1i
until V[j]<=5 ?
partition(1,7)
1 3 7 4j
until V[j]<=5 ?
Quicksort - partition
5 9 8 1i
until V[i]>=5 ?
partition(1,7)
1 3 7 4j
until V[i]>=5 ?
Quicksort - partition
4 9 8 1i
V[i], V[j] = V[j], V[i]
partition(1,7)
1 3 7 5j
V[i], V[j] = V[j], V[i]
Quicksort - partition
4 9 8 1i
until V[j]<=5 ?
partition(1,7)
1 3 7 5jj
until V[j]<=5 ?
Quicksort - partition
4 9 8 1i
until V[j]<=5 ?
partition(1,7)
1 3 7 5jj
until V[j]<=5 ?
Quicksort - partition
4 9 8 1i
until V[i]>=5 ?
partition(1,7)
1 3 7 5jj
until V[i]>=5 ?
Quicksort - partition
4 3 8 1i
V[i], V[j] = V[j], V[i]
partition(1,7)
1 9 7 5jj
V[i], V[j] = V[j], V[i]
Quicksort - partition
4 3 8 1i
until V[j]<=5 ?
partition(1,7)
1 9 7 5jj
until V[j]<=5 ?
Quicksort - partition
4 3 8 1i
until V[i]>=5 ?
partition(1,7)
1 9 7 5jj
until V[i]>=5 ?
Quicksort - partition
4 3 1 8i
V[i], V[j] = V[j], V[i]
partition(1,7)
8 9 7 5jj
V[i], V[j] = V[j], V[i]
Quicksort - partition
4 3 1 8i
jjjj
until V[j]<=5 ?
partition(1,7)
8 9 7 5
until V[j]<=5 ?
Quicksort - partition
4 3 1 8i
jjjj
until V[i]>=5 ?
partition(1,7)
8 9 7 5i
until V[i]>=5 ?
Quicksort - quicksort
4 3 1 8middle
4 3 14 3 1quicksort(1,3)
quicksort(1,7)
8 9 7 5
8 9 7 58 9 7 5quicksort(4,7)
Quicksort - quicksort
4 31 2 3
quicksort(1,3)
3 11 2 3
Quicksort - partition
4 3
i
partition(1,3)
3 1
j
Quicksort - partition
4 3
i
until V[j]<=4 ?
partition(1,3)
3 1
j
until V[j]<=4 ?
Quicksort - partition
4 3
i
until V[i]>=4 ?
partition(1,3)
3 1
j
until V[i]>=4 ?
Quicksort - partition
1 3
i
V[i], V[j] = V[j], V[i]
partition(1,3)
3 4
j
V[i], V[j] = V[j], V[i]
Quicksort - partition
1 3
i j
until V[j]<=4 ?
partition(1,3)
3 4
until V[j]<=4 ?
Quicksort - partition
1 3
i
j
i
until V[i]>=4 ?
partition(1,3)
3 4
until V[i]>=4 ?
Quicksort - partition
1 3
j
until V[i]>=4 ?
partition(1,3)
3 4
ii
until V[i]>=4 ?
Quicksort - partition
1 3
middle
partition(1,3)
3 4
Recommended