Uma introdução a algoritmos em Python | Herman M. | Skillshare

Velocidade de reprodução


  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x

Uma introdução a algoritmos em Python

teacher avatar Herman M., Enthusiastic video game developer and creator

Assista a este curso e milhares de outros

Tenha acesso ilimitado a todos os cursos
Oferecidos por líderes do setor e profissionais do mercado
Os temas incluem ilustração, design, fotografia e muito mais

Assista a este curso e milhares de outros

Tenha acesso ilimitado a todos os cursos
Oferecidos por líderes do setor e profissionais do mercado
Os temas incluem ilustração, design, fotografia e muito mais

Aulas neste curso

6 aulas (43 min)
    • 1. Apresentação

      2:06
    • 2. Complexidade computacional

      5:24
    • 3. Tipo de bolha

      9:01
    • 4. Tipo de inserção

      6:59
    • 5. Tipo de mesclagem

      11:09
    • 6. Tipo rápido

      8:44
  • --
  • Nível iniciante
  • Nível intermediário
  • Nível avançado
  • Todos os níveis

Gerado pela comunidade

O nível é determinado pela opinião da maioria dos estudantes que avaliaram este curso. Mostramos a recomendação do professor até que sejam coletadas as respostas de pelo menos 5 estudantes.

808

Estudantes

--

Sobre este curso

fdccbcfe

Esta introdução ao curso de algoritmos é um início abrangente para o belo mundo da ciência da computação. Este curso vai preparar você para um ótimo trabalho em um campo técnico e é um passo essencial para aprofundar as estruturas de dados e algoritmos e programação em geral.

Neste curso, vamos dar uma olhada no que é complexidade computacional e a importância dele, seguido de 4 algoritmos de classificação básicos (tipo de bolhas, tipo de inserção, tipo de mesclagem e tipo rápido) por visualização e demonstração em Python.

Todo o conteúdo do curso é simples de entender e relevante para aplicativos do mundo real.

Conheça seu professor

Teacher Profile Image

Herman M.

Enthusiastic video game developer and creator

Professor

I am an enthusiastic programer, video-game developer and creator. I've been working as a programmer and designer for a number of years now, building all kinds of things from small mobile games to fully immersive VR experiences.

I used to work in web and application development for big and small companies, building e-Commerce systems and websites. This was until I found game development and teaching hit the spot for me.

I have a passion for creation and a knack for teaching (both my parents and grandparents were teachers).

Visualizar o perfil completo

Nota do curso

As expectativas foram atingidas?
    Superou!
  • 0%
  • Sim
  • 0%
  • Um pouco
  • 0%
  • Não
  • 0%
Arquivo de avaliações

Em outubro de 2018, atualizamos nosso sistema de avaliações para melhorar a forma como coletamos feedback. Abaixo estão as avaliações escritas antes dessa atualização.

Por que fazer parte da Skillshare?

Faça cursos premiados Skillshare Original

Cada curso possui cursos curtas e projetos práticos

Sua assinatura apoia os professores da Skillshare

Aprenda em qualquer lugar

Faça cursos em qualquer lugar com o aplicativo da Skillshare. Assista no avião, no metrô ou em qualquer lugar que funcione melhor para você, por streaming ou download.

Transcrições

1. Apresentação: Bom dia, senhoras e senhores, bem-vindos a este vídeo eleições Siris sobre uma introdução aos algoritmos em Python. Meu nome é Harmon. Eu sou designer e desenvolvedor de videogames atualmente trabalhando na Sea Monster Entertainment na Cidade do Cabo, África do Sul. Eu trabalhei na indústria de I T por um tempo agora. Eu costumava construir sistemas de comércio gigante, mas descobri que o design do jogo era mais do meu gosto. E eu realmente gosto de ensinar. Estudei ciência da computação e multimídia na Universidade de Pretória e sempre fiquei fascinado com a forma como os algoritmos funcionam nas mentes brilhantes por trás dessas estruturas de dados e algoritmos. Nesta série de vídeos, vamos dar uma olhada em algoritmos de classificação especificamente. Então, por que você deve aprender algoritmos de fornecimento? Então eles são um ótimo lugar para começar ao aprender algoritmos. Então você pode estar dizendo, Por que você deve aprender quartos tão individuais, eles já estão incluídos em muitas linguagens de programação. Bem, isso é verdade, uh, Python Say, por exemplo, tem o algoritmo Tim vendido. Isto é mais um exercício académico. Teoh te deu um pé na porta sobre como os Albertans funcionam. Ele dá a uma pessoa mais insight sobre como esses sistemas realmente funcionam em sua relevância para problemas do mundo real. E, finalmente, é porque eles precisam muito deles. Muito legal. Então primeiro vamos aprender sobre a complexidade computacional e a eficiência dos algoritmos. Então vamos estar fazendo a fonte mais básica, esse tipo de bolha. Em seguida, a classificação de inserção. Depois disso, vamos dar uma olhada no meu favorito pessoal, o tipo de mesclagem, e finalmente, o semi apropriadamente chamado Quick Sort. Cada lição é dividida em uma descrição, um detalhamento da complexidade do Oliver, eles melhor média e pior caso. Então vamos dar uma olhada em uma visualização da função Halabi executa, seguido por uma queda na codificação desse algoritmo Onda. Vamos encerrar tudo isso fazendo uma visualização um ganho como você vai então saber o que está acontecendo atrás da cortina. Isto é para estudantes que estão interessados em algoritmos sobre as sutilezas da ciência da computação . Se você está apenas começando ou são chapéu velho, será algo dentro deste vídeo eleição Siris para você 2. Complexidade computacional: Bom dia, senhoras e senhores, e bem-vindos a esta lição sobre o Big O sobre complexidade computacional. A razão pela qual precisamos aprender maior e complexidade computacional é porque é a maneira que medimos a eficiência dos algoritmos que usamos. Portanto, é muito importante na ciência da computação e especificamente insultando algoritmos definir o que é um bom ou um ruim sobre eles. A notação Big O é usada em ciência da computação para descrever o desempenho ou complexidade. Muitas vezes o algoritmo Big oh descreveu especificamente o pior cenário caso, mas ele pode ser usado para descrever o tempo de execução necessário ou o espaço usado na memória ou no disco pelo algoritmo, especificamente com algoritmos de classificação. Também podemos usá-lo para descrever um caso médio ou um cenário de melhor caso, como algoritmos de classificação podem ter uma média pior ou melhor caso estado pré-ordenado. O que quero dizer com isso é, se tivermos uma matriz de cinco números, que é 38216 que é completamente sem sal, certo? Mas não está completamente na ordem inversa, o que significa que seria um cenário normal. O pior cenário seria se fosse 54321 A razão pela qual isso seria pior é porque o algoritmo tem toe realmente reverter toda a matriz. Então esse seria o pior cenário. Fort Melhor cenário caso seria 12345, o que significa que as matrizes realmente já classificadas , e nós estamos apenas verificando para ver que ele é. Como programador, descobri que a melhor maneira de entender Big 0 30 é através de código, e vamos fazer isso durante todo o curso. O que vou fazer é descrever para vocês os diferentes estados fora do grande. Você vai vê-los aparecendo aqui em que primeiro temos 01 Então ninguém descreve um algoritmo que sempre será executado no mesmo tempo ou espaço, independentemente do tamanho dos dados de importação. Portanto, isso é extremamente eficiente. É incrível, Andi, há muito, muito poucos quartos antigos que podem realmente funcionar em um. Então temos Oh, e então O N descreve um ritmo antigo cujo desempenho crescerá linearmente em proporção direta ao tamanho do conjunto de dados de entrada. O que quero dizer com isso é, se tivermos uma matriz de 20 itens, certo? Se adicionarmos outro gelo, o processamento necessário para o Isil crescerá linearmente. Enquanto que, como veremos mais tarde, com Owen ao quadrado, cresce exponencialmente. Então isso é representado neste ofício que ouvimos no amarelo é que à medida que mais dados são adicionados a mais itens neste caso, em uma taxa, a complexidade computacional dele aumenta linearmente. Eu vou chegar a logaritmos como N log end, Andi Log e Nana. Mas primeiro, vamos passar por 20 e lulas. Então Owen quadrado representa um algoritmo cujo desempenho é diretamente proporcional ao quadrado fora do tamanho do conjunto de dados de entrada. Então isso é comum com algoritmos que envolviam inspirações aninhadas sobre o conjunto de dados. Mensagens mais profundas. Rações resultarão em O. M. para o poder de três ou o fim para o poderoso etcetera, etc, etc. Então isso é muito ineficiente. Reação realmente quer ficar longe disso. Então aqui podemos ver oh, e quadrado nestes neste vídeo, Siri é onde é a pior complexidade computacional que vamos ver. Nós não vamos ver 02 para o poder do fim em tudo, porque para ser totalmente honesto, se classificar sobre eles é tão ineficiente, nós simplesmente não usamos isso. Nem sequer estudamos. Vamos falar sobre o fim. Ele denota um ritmo antigo cujo crescimento duplica com cada adição às entradas. Conjunto de dados. A curva de crescimento de 02 para o poder e função é exponencial, começando com um Lee meteórico muito raso e crescente. Vamos dar uma olhada nos logaritmos, então os logaritmos são um pouco mais difíceis de explicar. Então velho log n refere-se a uma função ou mais velhos eles ou pisando em todos eles, trabalhando em uma quantidade de tempo proporcional ao amante de geralmente uma base para na maioria dos casos e todos os exemplos que vamos ver no futuro. Assim, os atributos mais comuns de uma das funções de tempo de execução logarítmica são que a escolha do próximo elemento no qual realizar algumas ações é uma das várias possibilidades. Andi novamente será apenas e apenas um precisará ser escolhido ou os elementos em que a ação é executada são dígitos desligados. Então 00 log inimigo aqui é ridiculamente eficiente, não tão eficiente quanto 01, mas certamente mais eficiente do que o n linear. E então oh, e olha, e é realmente muito grande alcance aqui. Mas ainda é uma complexidade computacional melhor do que dizer, Oh, e quadrado. Vamos aprofundar muito mais este conceito nos próximos vídeos. Fique por perto para isso. 3. Tipo de bolha: Olá, senhoras e senhores, e bem-vindos a esta lição sobre o tipo bolha. Então vamos entrar ali. Qual é o tipo de bolha? Bem, a bolha é uma das fontes mais básicas de fontes de um logaritmo ondas, o mais simples de entender, é por isso que vamos começar aqui. São ideias básicas para bolhar os maiores ou os menores elementos, dependendo se você está classificando ou revertendo o fornecimento no segundo maior do terceiro e assim por diante. É o único até o fim da lista. Cada Elements faz uma varredura completa através da lista para encontrar-se em seu lugar correto, Então o sourcing de bola é um algoritmo terrivelmente ineficiente. Andi Pessoas perguntando por que, por que você aprende a classificação bolha quando já programação linguagens como python já comida. Excelente classificação mais antiga, como Tim classificar em. Isto está feito. Maura é um exercício acadêmico para não esquecer os princípios básicos da triagem. Então as fontes de bala, eu disse terrivelmente, terrivelmente ineficientes, com uma complexidade de caso pior e média fora oh, e quadrado, o que significa os elementos Mawr que são adicionados ao array. A violação do tempo de processamento aumentou exponencialmente. Curiosamente, no entanto, é o melhor caso e são onde todos os elementos na matriz são escritos. Ordenado é O. N, o que significa que ele só precisa correr através do array. O que é que é muito legal para testar se as matrizes já tipo de, mas não tão grande em realmente sourcing o array. Então aqui eu tenho um site que fornece o 80. Eu recomendo que você confira. É um recurso muito, muito interessante quando você está aprendendo seus diferentes algoritmos de classificação que ele tem uma série inteira deles. Vou usar isto durante todas as minhas lições. Então temos um completamente inordenado muito 09328614 cinco em sete. Então, essencialmente, como a bola para que ele funciona é vai comparar com parceiros adjacentes. No primeiro caso vai ser zero e nove. Ele vai ver se eles estão em suas posições corretas. Se não estiverem, vai virá-los ao redor. Neste caso, nada acontecerá. Mas quando nove é comparado a 39 e três, vamos virar e no próximo você é comparado agora nove, porque é o maior neste array vai continuar borbulhando até o final da lista. Então, medida que passamos por “Gets”, H e H continuarão borbulhando, sempre ao lado de nove , depois seis , etcetera, etc, etc. trabalho deles. Vamos dar uma olhada em como isso funciona. Ok, então nove viradas e apenas continua, borbulhando, borbulhando todo o caminho até o final da lista e de volta ao início. Três. E trocar os agentes seis. O que diz. Você pode ver que são apenas essas comparações entre estes pares dedos do pé. Coloque-os na posição certa, e isso geralmente é ineficiente, mas está fazendo isso, e então vamos lá. Temos nossa lista ou taxa classificada, então vou nos trazer de volta a essa visualização. Agora vamos primeiro entrar em algum código para ver o que realmente está acontecendo atrás das cortinas. Eu tenho este arquivo python ou um set up ordenando DupUy em vez de meu sourcing pasta mais velho deles em apenas isso. Podemos usar este mesmo arquivo para todas as diferentes salas antigas que fazemos. Nesta lição, vou para o mais velho desta maneira. Eu vou dizer, importação aleatória, uh, em. E vamos criar a matriz que vamos ser sourcing é itens aleatórios. Vamos povoar isso já com grandiosos aleatórios Oh, digamos menos 52 100. Então vamos criar inteiros aleatórios entre menos 50 em 100 quatro em um raio de um comprimento 20. Certo, então só podemos testar os algoritmos de distância na parte inferior dos documentos aqui . Eu vou dizer, Príncipe, Príncipe, antes de itens aleatórios. Então isso vai para o Prince, o arranjo não originado. Iam chamar o fornecedor comum deles de escolha. Neste caso, vamos chamar a fonte formal, que irá implementar agora e mais itens aleatórios através dele e príncipe depois, e isso é apenas lá para ter certeza sobre o mais velho do que funciona. Então vamos começar a implementar uma bolha classificar morte, classificações locais, passando por esses itens. Então a primeira coisa que vamos fazer aqui é realmente correr através de toda a taxa de zero para o comprimento fora itens vender um cofre para eu na faixa. Obrigado. Oh, itens. Em seguida, vamos percorrer todo este intervalo novamente, mas não vamos chegar ao fim porque sabemos que o maior elemento nesta matriz já está no final. Então, para J intervalo off fazer itens menos um menos I, qual é esta variável? Então vamos dizer, se os itens de J é maior que os itens O j mais um. Então, essencialmente, essa é a comparação entre os dois elementos para verificar qual deles é o maior dos dois , e então nós vamos trocá-los. Agora há duas maneiras de trocá-los. Linguagens de programação tradicionais. Você criaria uma variável temporária e médica item temporário é igual a itens O.J . E então definimos vitaminas O.J pessoas dois itens fora J mais um e, em seguida, diz itens O J +12 temporização. Então isso é muito detalhado. E eu não gosto muito disso em Python tem uma maneira muito legal de obter isso, senhor. Vamos dar uma olhada no que é isso. Bem, digamos que itens de J vírgula R J mais um são pessoas dois itens fora do J mais um dos meus pecados. Ó Shea. Isso vai fazer exatamente a mesma coisa. E é muito mais elegante até a patente e ler. Então vamos dar uma olhada se o nosso pequeno algoritmo de sourcing de bolha aqui funciona conforme necessário. Eu já estou eu abri meu terminal aqui, e eu já estou dentro deste sourcing sobre Holder dentro daquela pasta está classificando ponto alto. Então vamos executar isso e atualmente executando Python três, mas hífen dois deve funcionar perfeitamente bem. Ok, semana acima. Então, antes de termos negativo seis 35 indo todo o caminho através de inteiros completamente aleatórios entre menos 50 e 100 depois que parece que tudo está em ordem, indo de menos 50 todo o caminho até 90. Então sabemos que o nosso pequeno algoritmo fez o seu trabalho. Vamos dar outra olhada nessa visualização agora que sabemos o que está acontecendo aqui. Então é isso que eu deveria passar por isso. Ok. Então compara. Nove e três e nove continua borbulhando até o final da lista. E então três bolhas deste h continua borbulhando todo o caminho até o fim, e seis bolhas até a direita ao lado das sete. E agora só precisamos colocar o teste que você quer em sua posição correta. Andi! Lá temos ele. Senhoras e senhores, a fonte da bolha. Muito obrigado. Vejo-te na próxima lição. 4. Tipo de inserção: Bom dia, senhoras e senhores. E bem-vindo a esta lição sobre a classificação de inserção nos algoritmos básicos de sourcing e pipe no Khost. Então vamos saltar diretamente para os insurgentes fora de obras, pegando elementos da lista não ordenada e inserindo-os no lugar certo em um novo tipo de lista. A lista classificada está vazia. O começo. Este é o número total de elementos na lista nova e antiga permanecem os mesmos. Podemos usar o sem costura para representar sortidas nas seções não classificadas. Então, essencialmente, o que isso significa é que nós vamos, se avaliar junto, comparar os diferentes parceiros ser elementos completamente adjacentes até encontrarmos um que não está no lugar correto e movê-lo para baixo para o seu correto posição. Essencialmente, fazendo interruptores como vimos na classificação bolha é como uma bolha para baixo sempre que encontramos certas posições elemento. Então vamos dar uma olhada rápida na eficiência e depois fazer uma visualização. Thea Eficiência fora da fonte de inserção também é suficiente. Quebra. Este é outro desses tipos acadêmicos é que o pior desempenho caso é O. N suor, tanto em comparações e swaps. O caso médio apresenta Owens Square também. No melhor caso executa semelhante à classificação bolha é OM, que significa que tudo está na posição correta que só tem que operar através da lista uma vez. Então vamos dar uma olhada em como isso funciona. Primeiro, vamos comparar um com nove. Veremos que eles estão em que médicos corretos. Então eu ia ser comparado a oito. Eles vão mudar ao redor, então nove vai se tornar ela completa agora para não era nada. Essa é a posição correta. Então ele vai ser movido para o lugar, vai ser comparado com oito e trocado em torno e então nós mover todo o caminho de volta para nove e dois e dois não está em sua posição correta. Então vamos descer a lista e de novo. Lá vamos nós para que você possa ver que você pode ver a tendência daqui. Zero terá que se mover até o final da lista. Diz que não está em sua posição correta, e eu só vou acelerar isso agora que você tem a essência do que está acontecendo aqui . Temos seis movendo-se para baixo três movendo-se para baixo todo o caminho até o início e, em seguida, disparar quando colocamos ao lado de seis em sete será material em sua posição correta. E então temos a fonte da lista. Então vamos dar uma olhada no código. Aqui temos o também da última vez. Vamos definir uma nova inserção de função. Então, apenas leva na lista de itens. Não diga isso só para ter certeza de que não esquecemos isso, eu adicionei molho de inserção aqui. Então, os insurgentes serão chamados quando o arquivo estiver sendo executado. Primeiro precisamos do dedo do pé é correr através de toda a taxa de um para o comprimento Este próximo nós vamos definir J pessoas para I A razão pela qual nós estamos colocando J Able olhos apenas para nós termos a posição enquanto nós subimos. Então, enquanto J é maior que zero, você simplesmente não é o primeiro elemento. E Bison está fora do Jay ou menos do que Isis está fora. Licença de J menos um. Ok, então esta comparação aqui está verificando para ver se, uh se os elementos vizinhos estão em suas posições corretas e se eles estão em posições incorretas, nós vamos trocá-los em torno de como nós não jogamos pára. Nós vamos dizer itens de J sair então J menos um e você vai ver que estamos usando J menos um em vez de J mais um, como nós não fizemos a fonte da bolha A razão para isso é que nós estamos realmente fazendo a comparação ao contrário para que possamos continuar a mudar estes para que médicos corretos. Tyson Off J menos um item fora, J. diz. Está se contorcendo, e então a última e provavelmente a parte mais importante é esta. Jay é menos igual a um. Então o que isso vai fazer é que vai mover o índice para baixo enquanto esses elementos não estão na posição correta. Então, verificando para ter certeza de que não estamos certos no início, estamos verificando se essas coisas estão em ordem. Se não estiverem em ordem. O que fazemos é trocá-los e descer, trocá-los , subir. Ok, então vamos dar uma olhada em como esses quartos Ok, então vamos correr, uh, classificar. E mais uma vez estes amigos do tubo em dois e três lá vamos nós Em breve temos uma lista sem sal 97 85 3 42 21 Onda. Nós temos a lista depois, que tudo parece ter sido classificado sobre ele e está em sua posição correta. No caso de você não estar por perto na última lição, nós jatos. Geramos aleatoriamente uma lista de 2028 polegadas entre menos 50 em 100 que é a matriz que está classificada. Vamos dar uma olhada rápida na classificação que 18 para ver uma representação visual disso agora que você nos entende melhor. Tudo bem, então nove movimentos em estado de movimento completo posição correta para mover todo o caminho até a posição correta , bem como, e zero move todo o caminho através. Isso é que selvagem em surdos, emitindo fora do J em três anos todo o caminho até o início também. Cinco. Para esta posição correta em finalmente sete em sua posição correta. Bem, espero que isso lhe dê uma compreensão muito melhor sobre como a classificação de inserção funciona e também lhe dê uma melhor compreensão de como os algoritmos de classificação no trabalho geral têm que vê-lo na próxima lição. Tenha um ótimo 5. Tipo de mesclagem: Bom dia, senhoras e senhores, e bem-vindos a este vídeo sobre a classificação de mesclagem nos algoritmos básicos em vídeo Python, Siri Vamos saltar direto no tipo de mesclagem. Ele funciona subdividindo a lista em duas sub-listas, ordenando-os usando mesclagem, ordenar para repetir Siple e, em seguida, mesclando-os novamente. Como a Pesquisa Recursiva é feita para subdividir cada lista em uma sub-lista, eles acabarão por atingir o tamanho de um, que é tecnicamente uma lista classificada. Então nós vamos ter uma boa lista longa de inteiros em. Vamos subdividir isso em duas listas menores para listas menores para listas menores até termos inteiros individuais. Então vamos usar a chamada recursiva para fundi-los juntos em colá-los no lugar correto enquanto eles vão. Vamos dar uma olhada na complexidade computacional, modo que a complexidade computacional fora da fonte emergir nos piores casos em média são todos o n log, e você deve lembrar de nossa complexidade computacional e de vídeo que isso é terrível, como e ao quadrado. Mas não é rico. É justo. É uma rápida olhada em como a fusão funciona assim como temos na imagem aqui, temos uma matriz sem classificação de 38 27 43 39 82 e 10. Nós dividimos esse array em dois, separados para levantar ou sublistas, usando um cool recursivo que é 30 idade 27 43 3 de um lado e 1982 e 10 do outro lado , e nós subdividimos cada uma dessas listas também. Continuamos subdividindo até termos elementos individuais por todo o caminho. Agora, o pedido de Cool irá mesclá-los novamente ao fazer comparações para ver qual elemento vai para onde. Assim, 30 18 27 são mesclados e comparados entre si. Então nós temos 27 38 43 3 são comparados uns com os outros, e ele acaba como uma sub-lista fora três e 43 o mesmo é feito aqui com 1982 e finalmente 10 aqui. Honestamente solitário. Então temos essas sub-listas mesclar juntos para criar essas sub-listas maiores em Finalmente, essas duas sub-listas mesclam uns com os outros e eles são todos classificados na ordem correta 39 10 27 38 43 no dia 82. Vamos dar uma olhada rápida na classificação Feito 80. Classificar que 80 como eu mencionei meus vídeos anteriores é um recurso fantástico para visualizar algoritmos de classificação e um altamente recomendado que você confira. Dieta de triagem. Ele pode não ser a melhor maneira de visualizar a alma da fusão, mas recomendo que dê uma olhada. Vamos analisá-lo mais tarde, logo depois de entrarmos no código. Então nós temos nossa classificação pública e classificação de inserção da última vez. Vamos definir uma nova função dela aqui. Fonte de mesclagem a frio leva uma matriz de itens em Vamos. Vamos dizer se o comprimento dos itens é maior do que um, então selecionamos o meio, que é o comprimento dos itens dividido por dois. Ver qualquer coisa um pouco igual sobre eles e nós temos a esquerda mais. O Sumário esquerdo e Python tem uma boa maneira de definir os resumos à esquerda itens de zero para o ponto médio, e temos o resumo direito, que é ITV. Notícias. Off to the end é um pequeno encantador expressões em python e eu recomendo que você faça uma introdução ao curso Python apenas para que você esteja muito familiarizado com todos esses truques fantasiosos . Ok, então aqui é onde o Rickerson começa a acontecer dentro de dentro desta função, nós estamos realmente indo para cool merge source novamente com o resumo esquerdo, e nós vamos chamar merge, classificar com o resumo direito . Então, essencialmente, o que está acontecendo aqui vai continuar acontecendo e continuar acontecendo enquanto o comprimento fora da licença é se o comprimento dos itens é maior do que um. Certo, então agora vamos fundir a esquerda na lista da direita. Então nós temos esquerda, certo? É igual a zero é o seu. É uma boa maneira de definir isso. Esses índices vão dizer, ou eu em comprimento de alcance fora itens estavam correndo através de todo o raio. Vamos dizer valor à esquerda, encontrar isto definido. Esta variável é igual à esquerda no índice esquerdo. Se o índice esquerdo é menor do que o comprimento desligado à esquerda, se esse não for o caso mais, Não, vamos fazer o mesmo para os direitos. Dizemos que o valor certo é igual à matriz de direitos no índice. Se o índice certo for menor do que o comprimento, certo, certo, porque não queremos que o Teoh vá uma e outra vez, vamos dizer que não. você dissesse se o valor à esquerda existe e o valor à direita existe e o valor à esquerda é menor do que à direita. Então é aqui que a comparação começa a ser feita ou se o valor certo é nenhum. Certo, então a razão pela qual estamos fazendo isso é porque há chances de que haverá uma única instância em ambos os lados da lista. Você vai dizer, se isso é, então é itens. Oh, eu já que ainda estamos pisando por aqui é igual ao valor esquerdo. Tudo bem, então está enfiando naquele anel melhor. Vamos dizer que a esquerda abençoa as pessoas para querer apenas implementado por um para que possamos continuar pisando pela esquerda ou pela direita. Então agora vamos fazer o mesmo para o outro lado. Vamos dizer que vamos dizer se o valor esquerdo e o valor direito, certifique-se de que eles existem e valor esquerdo desta vez é maior ou igual ao valor certo . Você vai dizer que isso ou o valor esquerdo não é nenhum dos quais está configurado aqui, então vamos fazer o mesmo filme aqui. Itens tudo que eu é pessoas muito brilhante valor. E então nós incrementamos nosso índice ambos, e isso é apenas um pouco de um cheque. Podemos ficar. Aumente a exceção. Hood bate se funde, e está a torná-lo mais descritivo. Os tamanhos de sub-matrizes não correspondem à matriz principal. Ótima. Então esse é o código. Vamos dar uma olhada rápida através dele novamente que este é um pedido de legal. Vamos nos ver passando pela matriz novamente em incrementos menores e menores . Se o comprimento dos itens for maior que um e refinar os pontos intermediários, estamos criando uma matriz esquerda e direita, e então estamos chamando a classificação de fusão no aumento do metrô. Além disso, estamos definindo um índice para esquerda e direita em 00, então vamos correr através para eu sou reinos, não raiva para o comprimento que aqueles itens estavam indo para ter. O valor à esquerda é igual ao valor desligado à esquerda em todos os índices. Se o índice for menor que o comprimento da esquerda, apenas certifique-se de que ele está dentro. Está dentro desse resumo. O valor esquerdo é igual a nenhum, o que vamos verificar aqui. O mesmo com o valor certo. Ele vai estar no resumo direito no índice nosso Se o nosso é menor do que o comprimento fora da direita separar-nos, nosso valor é igual a não. E nós vamos fazer a verificação. Digamos, se o valor à esquerda no valor à direita existe no valor à esquerda é menor do que o valor à direita. Esta é a comparação. Ou se o valor certo é nenhum, então nós vamos ligar. Em seguida, vamos definir itens de I igual ao valor esquerdo um incremento de valor à esquerda. O mesmo acontece aqui, do lado direito. E se alguma coisa falhar, vamos levantar uma exceção dizendo que não pode se fundir. Os tamanhos separados não correspondem à taxa principal. Ok, vamos correr no terminal por aqui. Hífens triagem pontuar e correr. Ok, então nós temos a lista não ordenada do topo, que é uma matriz aleatória de comprimento de 20 que cada inteiro é aleatoriamente entre menos 50 e 100 depois temos uma lista perfeitamente ordenada. Fantástico. Espero que isso tenha lhe dado algumas informações valiosas sobre cargas assassinas. Algoritmos em geral sobre como Rikers funciona. Vejo você no próximo vídeo. 6. Tipo rápido: Bom dia, senhoras e senhores, e bem-vindos a este vídeo sobre o tipo rápido. Vamos direto ao assunto. O rápido vendido funciona primeiro selecionando um elemento central da lista. Os elementos de pivô é bastante fundamental na classificação rápida, a seleção do elemento profeta pode aumentar ou diminuir a complexidade computacional do mesmo. Então, o elemento pivô que vamos usar vai ser o centro direto da lista ou matriz, em seguida, cria duas listas, uma contendo elementos menos do que o público e os outros elementos contendo me contrataram. Em seguida, ataca as duas listas e junta-se a elas com o perfeito no meio, assim como o tipo de fusão. Quando as listas são subdivididas em listas de Tamanho um, elas são consideradas já classificadas. Além disso, assim como o tipo de mesclagem. Nós vamos estar usando Rikers em sim, a eficiência fora da fonte rápida no pior dos casos é O n ao quadrado, semelhante aos sais de bolha e não muito eficiente. O melhor caso e desempenho médio caso R O N log e semelhante à classificação emerge, que não é ruim. Também não é bom . É gorda. Vamos chamar isso de justo. Vamos fazer uma visualização do tipo rápido. Agora, como com o tipo de fusão por causa de tudo o que está acontecendo atrás da cortina de Rikers pode não fazer muito sentido. Então, primeiro, o que acontece é que selecionamos um ponto de pivô. Este é o primeiro é arejamento através dele, e nós vamos cavar o código, então você vai entender melhor o que está acontecendo com ele. Ele encontra tese entrar de marionete, e então é Ele muda aqueles dois, mas ele realmente não os muda. O que está acontecendo nos bastidores é que ele está colocando o seis no menor que o array de lucro e está colocando o nove no maior que o raio principal. Assumindo que a prova aqui é cinco. Próximo. À medida que atravessamos, ele muda sete e um e novamente, quando digo interruptores, significa que coloca um no menos de um ancinho e coloca sete no Ranger do que o Rick. Então temos cheio colocar no menos século e seis colocar no maior do que o terreno em. Finalmente, temos 25 alternar sobre cada um deles, selecionar seu próprio ponto de pivô todo o caminho para baixo, e então aqueles para mudar e Como você pode ver, ele lentamente começa a criar um socialista, e finalmente sete e cada um ficar virado sobre. Ali. Temos a lista ordenada novamente. Esta não é a melhor utilização disso. Vamos dar uma olhada no código, e eu acho que você vai entender melhor. Aqui está o arquivo DupUy que criamos para as aulas anteriores. Ele tem um item aleatório pronto, que é uma matriz de 20 elementos de comprimento, cada um deles gerado aleatoriamente. Entre menos 50 e 100 é encontrar uma nova função dele aqui, chamada Classificações de Wick. Protege na lista de itens e tomar na lista de itens é muito importante porque vamos chamá-los dentro da função porque é regressiva. Eu também chamado de classificação rápida aqui para se certificar de que é a função que é chamada quando executamos a classificação do arquivo alto. Tudo bem, ótimo. Então, as primeiras coisas primeiro, como com o tipo de mesclagem iam dizer se o comprimento dos itens é maior que um, porque como foram subdivididos, queremos estocar. Em seguida, selecionamos o índice privado novamente. Isso a seleção do índice Pivot pode ser uma função complicada para tentar encontrar o lugar correto para ele. Mas no nosso caso, e para fins de demonstração, vamos tê-lo como o comprimento da taxa dividida por dois tão mortos no centro. Em seguida, criamos itens menores e maiores levantam. Eles começaram como vazios e estarão preenchendo a natureza deles. iTunes maior é pessoas para gravar varietais. Fantástico. Então é aqui que a magia começa a acontecer. É um quatro I. Eu ia ser o índice que vai manter o nosso lugar e tu que era o valor da coisa que nós vamos estar enumerando grupo a coisa numerador através do brilho dos itens. Então, novamente, eu segurando o índice val contendo valor. Você diz que eu não sou pessoas, também não tenho índice porque nós não queremos que as cobiças reais sejam trocadas. Então, se arco é menor do que gelo fora dentro do próximo, dois estavam fazendo a comparação para ver se é ótimo para eles ou menos do que oito índice sobre, porque o valor é menor no próximo, levá-lo e colocá-lo em itens menores e, em seguida, se ele é não menos do que, mas é de fato maior do que ou não igual a, porque estamos fazendo aquela verificação lá e seguro mais. Iceman maior faz um valor pingente fantástico, então este não seria um array recursivo sem um cool recursivo. Só passaria por ele uma vez, e você tem um pouco mais de nós. Na verdade, seria apenas um único elemento que fica preso nos subúrbios, tipos nazistas, itens menores. Então, essencialmente, o que está acontecendo lá é que nós vamos ser rápido sourcing cada resposta individual cada um separado todo o caminho para baixo. Então, cada um separa elege seu próprio índice de cobiça. Ele cria uma pequena licença e um raio de gelo maior e cada um destes, em seguida, obter algum tipo desse tipo de França. É meio grande, surgir Sra. Well, e então, finalmente, o que vamos fazer é dizer itens iguais a itens menores, mais o de que investe mais itens maiores. Então, isso só junta tudo no final. Então temos itens menores, e então no meio temos elementos de índice, e então temos os itens maiores. Então vamos dar uma olhada no início. Vamos nos certificar de que o comprimento de cada um deles é Não. Um. Vamos selecionar um índice pivô, declarar menor e maior Ice Marie e então vamos correr. Nós vamos enumerar através dos itens em. Vamos colocá-los em um aumento menor ou maior, dependendo de onde devem estar. E, finalmente, vamos para o núcleo rápido, classificar em cada um desses resumos. Vamos dar uma olhada rápida, ver se isso funciona. Eles têm o meu P. WiFi ligado. Eu vou executá-lo, eu pensei, classificando alto. E como podem ver, temos um desordenado que não temos mais desordenado. 28 26 93 menos dois depois que temos um tipo completamente de taxa de menos 50 para 98. Fantástico. Sabíamos que a nossa gama de comprimidos funciona. Vamos dar uma segunda olhada na visualização novamente. A visualização não é toda essa revelação por causa de todo o Rickerson que está acontecendo, mas é interessante assistir e vamos. Então nós estamos assumindo que o primitivo aqui é cinco, e aqueles são trocados em seus maiores ou menores resumos maiores ou menores também o tipo rápido de às vezes chamado de troca de petições vendido, o que eu acredito é muito nome mais apt para como realmente particionamento e, em seguida, classificar cada uma dessas diferentes partições. Oh, você entende o tipo rápido de minúsculo, mas melhor em velhos ritmos na luta em geral. Muito obrigado por se juntar a mim. Tenha um encontro fantástico.