Explore
For Enterprise
Join for Free
Log In

Artes e Humanas
Negócios
Ciência da Computação
Ciência de Dados
Tecnologia da informação
da saúdesaúde
Matemática e Lógica
Desenvolvimento Pessoal
Ciência e Engenharia Física
Ciências Sociais
Línguas
Diplomas e certificados

Explore todo o Coursera

Navegar
Pesquisar
For Enterprise
Entrar
Inscreva-se gratuitamente

Bottom-up Mergesort

Loading...

Algoritmos, Parte I

Universidade de Princeton

4.9 (5,054 classificações) | 390K alunos inscritos

Visualizar o programa do curso

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free. It does not offer a certificate upon completion.

Habilidades que você aprenderá

Data Structure, Priority Queue, Algorithms, Java Programming

Avaliações

4.9 (5,054 classificações)

5 stars
4,735 ratings
4 stars
273 ratings
3 stars
26 ratings
2 stars
7 ratings
1 star
13 ratings

BJ

Jun 03, 2018

Good contents and the logic of the whole course structure is very clear for a novice like me. The weekly homework is also awesome. Would recommend to anyone who wants to learn about computer science.

GG

Nov 01, 2016

Extremely well designed course. The assignments touch all the concepts taught in the class. Lot of concepts get clarified when you try to reach 100% on each assignment. Highly recommend this course.

Na lição

Mergesort

We study the mergesort algorithm and show that it guarantees to sort any array of n items with at most n lg n compares. We also consider a nonrecursive, bottom-up version. We prove that any compare-based sorting algorithm must make at least n lg n compares in the worst case. We discuss using different orderings for the objects that we are sorting and the related concept of stability.

Bottom-up Mergesort3:20

Sorting Complexity9:05

Comparators6:43

Ministrado por

Kevin Wayne
Phillip Y. Goldman '86 Senior Lecturer
Robert Sedgewick
William O. Baker *39 Professor of Computer Science

Next, we're going to look at a bottom-up version of Mergesort. Well, Mergesort is

easy to understand as a recursive program. This bottom-up version that has no

recursion, it's also quite simple to understand and to code up. The basic idea

is to think of the array as being a little at the begining a set of little sorted sub

arrays of size one. And then what this method will do is go through and merge

those little subarrays of size one together in pairs to get subarrays of size

two. Then, the whole array consists of sorted subarrays to size two, and

then we make another pass through to get size four, and then size eight, and so

forth. So, as you can see in this example we start out by merging the first two sub

arrays of size one to make a array of size two - E, M - that's sorted, and then do the same

thing for the next two elements and the next two and so forth until eventually

instead of sixteen individual elements we have eight sorted subarrays of size two.

Then on another pass through, we can take the E, M and the G, R and merge them

together to make EGMR, and the E, S and the O, R merge those together to make EORS, and

so forth. And we have four subarrays of size four. One more pass makes two

subarrays of size eight, and the last pass is just a sorted array. The bottom line in

this is sequence of passes through the whole array and there's no recursion

needed at all. It's extremely easy to code up as you can see from this code. We use

the same merge code as before and we take a nested for loop. The first one is the

size of the subarray and this loop gets executed on a log N times because each time

we double the size of the subarray until we get to N. And then we pass through

picking out from low to low+size-1, and then the next part is low+size+size-1

until we run to the end of the array where we might not have a full

subarray of size sz. That is a fully complete industrial strength code for

sorting. The only downsize as would regular Mergesort is that it uses extra

space proportional to the size of the array. But otherwise, that's a fine method

for merging. That's a bottom-up Mergesort. If you look at this visual trace you can

see how it works. The thing is totally unsorted, then it gets sorted until

subarrays to size four, then eight, sixteen, and 32. Now in this case the

second subarray to be sorted is smaller but the merge routine doesn't really care

about that so much. You can merge things that are not equal in size. And then we get

a final sorted array. Whatever the size, bottom of Mergesort gets the job done in

log N passes. Each pass using about N compares for a total cost of about N log N.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play

Coursera
Sobre
Liderança
Carreiras
Lista de cursos
Certificados
Certificados MasterTrack™
Notas
For Enterprise
For Government

Comunidade
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

Mais
Termos
Privacidade
Ajuda
Acessibilidade
Imprensa
Contato
Diretório
Afiliados