You work at the college library. You're in the middle of a quiet afternoon when suddenly a shipment of 1,280 different books arrives. The books have been dropped of in one long straight line, but they're all out of order, and the automatic sorting system is broken. To make matters worse, classes start tomorrow, which means that first thing in the morning, students will show up in droves looking for these books. How can you get them all sorted in time? One way would be to start at one end of the line with the first pair of books. If the first two books are in order, then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach the end of the line. At some point, you'll come across the book that should be last, and keep swapping it with every subsequent book, moving it down the line until it reaches the end where it belongs. Then, start from the beginning and repeat the process to get the second to last book in its proper place, and keep going until all books are sorted. This approach is called Bubble Sort. It's simple but slow. You'd make 1,279 comparisons in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second, the process would take over nine days. A second strategy would be to start by sorting just the first two books. Then, take the third book and compare it with the book in the second spot. If it belongs before the second book, swap them, then compare it with the book in the first spot, and swap again if needed. Now you've sorted the first three books. Keep adding one book at a time to the sorted sub-line, comparing and swapping the new book with the one before it until it's correctly placed among the books sorted so far. This is called Insertion Sort. Unlike Bubble Sort, it usually doesn't require comparing every pair of books. On average, we'd expect to only need to compare each book to half of the books that came before it. In that case, the total number of comparisons would be 409,280, taking almost five days. You're still doing way too many comparisons. Here's a better idea. First, pick a random book. Call it the partition and compare it to every other book. Then, divide the line by placing all the books that come before the partition on its left and all the ones that come after it on its right. You've just saved loads of time by not having to compare any of the books on the left to any of the ones on the right ever again. Now, looking only at the books on the left, you can again pick a random partition book and separate those books that come before it from those that come after it. You can keep creating sub-partitions like this until you have a bunch of small sub-lines, each of which you'd sort quickly using another strategy, like Insertion Sort. Each round of partitioning requires about 1,280 comparisons. If your partitions are pretty balanced, dividing the books into 128 sub-lines of ten would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add about 22 seconds each. All in all, this method known as QuickSort could sort the books in under three and a half hours. But there's a catch. Your partitions could end up lopsided, saving no time at all. Luckily, this rarely happens. That's why QuickSort is one of the most efficient strategies used by programmers today. They use it for things like sorting items in an online store by price, or creating a list of all the gas stations close to a given location sorted by distance. In your case, you're done quick sorting with time to spare. Just another high-stakes day in the library.
Trabalhas na biblioteca da faculdade. Estás no meio de uma tarde tranquila quando, subitamente, chega um carregamento de 1280 livros diferentes. Os livros foram descarregados numa longa linha reta mas estão todos fora de ordem, e o sistema de classificação está avariado. Para piorar as coisas, as aulas começam amanhã o que significa que, logo de manhã cedo, todos os estudantes vão aparecer à procura desses livros. Como é que podes ordenar todos os livros a tempo? Uma forma seria começar pelos dois primeiros livros, num dos extremos da fila. Se os dois primeiros livros estiverem por ordem, deixa-os ficar onde eles estão. Caso contrário, troca-os de lugar. Depois, observa o segundo e o terceiro livros. e repete o procedimento. Continua até chegares ao fim da fila. A certa altura, encontras o livro que devia ser o último. Vai-o trocando sempre de lugar com os livros posteriores, até ele chegar ao fim da fila, ao lugar que lhe pertence. Volta a começar do princípio e repete o procedimento. até colocar o penúltimo livro no seu devido lugar. Volta a repetir tudo até todos os livros estarem nos seus lugares. Este método chama-se "Ordenação por Flutuação". É simples, mas lento. Tens que fazer 1279 comparações na primeira ronda, depois, 1278, e assim sucessivamente, num total de 818 560 comparações. Se cada uma delas demorar só um segundo, o processo demorará nove dias. Uma segunda estratégia seria começar por ordenar os dois primeiros livros. Depois, comparar o terceiro livro com o livro no segundo lugar. Se ele deve ficar antes do segundo livro, troca-os de lugar. Depois compara-o com o livro no primeiro lugar e troca-os, se necessário. Tens os três primeiros livros ordenados. Continua com um livro de cada vez comparando e trocando o novo livro com os que estão antes dele até ele ficar corretamente colocado entre os livros ordenados até aí. Este método chama-se "Ordenação por Inserção". Ao contrário da "Ordenação por Flutuação" não exige que se comparem todos os pares de livros. Em média, só precisamos de comparar cada livro com metade dos livros que estão antes dele. Neste caso, o número total de comparações seria de 409 280, o que levaria quase cinco dias. Continuas a ter que fazer demasiadas comparações. Esta é uma ideia melhor. Primeiro, agarra num livro ao acaso. Chama-lhe "partição" e compara-o com o outros livros todos. Depois divide a fila colocando à esquerda todos os livros que devem ficar antes da partição e à direita, os que devem ficar depois da partição. Poupaste imenso tempo porque não precisas de comparar nenhum dos livros da esquerda com os da direita. Depois, olha só para os livros da esquerda. Podes voltar a agarrar num livro ao acaso, outra "partição" e separar os livros antes dela dos livros depois dela. Podes continuar a criar subpartições como estas até teres um grupo de pequenas sublinhas, cada uma das quais podes ordenar rapidamente, usando outra estratégia como a "Ordenação por Inserção". Cada ronda de partição exige cerca de 1280 comparações. Se as partições estiverem equilibradas, dividir os livros em 128 sublinhas de 10, deve precisar de sete rondas, ou seja 8960 segundos. Ordenar as sublinhas, demorará mais 22 segundos cada. Ao todo, este método, conhecido por "Ordenação Rápida" pode ordenar os livros em menos de três horas e meia. Mas há um inconveniente. As partições podem ficar desequilibradas, e não poupar tempo nenhum Felizmente, isso acontece raramente. É por isso que a Ordenação Rápida é uma das estratégias mais eficazes usadas hoje pelos programadores. Usam-na para ordenar, por preço, os artigos numa loja online ou para criar uma lista de todas as estações de gasolina perto de uma dada localidade ordenadas pela distância. No teu caso, fizeste uma ordenação rápida, com tempo de sobra.