{"id":3344,"date":"2022-07-30T22:01:39","date_gmt":"2022-07-30T19:01:39","guid":{"rendered":"https:\/\/demensdeum.com\/blog\/?p=3344"},"modified":"2024-12-16T22:32:18","modified_gmt":"2024-12-16T19:32:18","slug":"quicksort","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/pt\/2022\/07\/30\/quicksort\/","title":{"rendered":"Classifica\u00e7\u00e3o r\u00e1pida"},"content":{"rendered":"

Quicksort \u00e9 um algoritmo de classifica\u00e7\u00e3o de divis\u00e3o e conquista. Recursivamente, pe\u00e7a por pe\u00e7a, analisamos a matriz de n\u00fameros, colocando os n\u00fameros em ordem menor e maior a partir do elemento de refer\u00eancia selecionado, e inserimos o pr\u00f3prio elemento de refer\u00eancia no corte entre eles. Ap\u00f3s v\u00e1rias itera\u00e7\u00f5es recursivas, voc\u00ea ter\u00e1 uma lista ordenada. Complexidade de tempo O(n2<\/sup>).<\/p>\n

Esquema:<\/p>\n

    \n
  1. Come\u00e7amos obtendo uma lista de elementos externos, os limites de classifica\u00e7\u00e3o. Na primeira etapa, os limites de classifica\u00e7\u00e3o ser\u00e3o do in\u00edcio ao fim.<\/li>\n
  2. Verifique se os limites inicial e final n\u00e3o se cruzam; se isso acontecer, \u00e9 hora de terminar.<\/li>\n
  3. Selecione algum elemento da lista e chame-o de piv\u00f4<\/li>\n
  4. Mova-o para a direita at\u00e9 o final do \u00faltimo \u00edndice para que n\u00e3o atrapalhe<\/li>\n
  5. Crie um contador de *n\u00fameros menores* ainda iguais a zero<\/li>\n
  6. Percorrer a lista da esquerda para a direita, at\u00e9 e incluindo o \u00faltimo \u00edndice onde o elemento de refer\u00eancia est\u00e1 localizado<\/li>\n
  7. Comparamos cada elemento com o de refer\u00eancia<\/li>\n
  8. Se for menor que o de refer\u00eancia, trocamos de acordo com o \u00edndice do contador de n\u00fameros menores. Aumente o contador de n\u00fameros menores.<\/li>\n
  9. Quando o loop atinge o elemento de suporte, paramos e trocamos o elemento de suporte pelo elemento de acordo com o contador de n\u00fameros menores.<\/li>\n
  10. Executamos o algoritmo separadamente para a parte menor \u00e0 esquerda da lista e separadamente para a parte maior \u00e0 direita da lista.<\/li>\n
  11. Como resultado, todas as itera\u00e7\u00f5es recursivas come\u00e7ar\u00e3o a parar devido \u00e0 verifica\u00e7\u00e3o no ponto 2<\/li>\n
  12. Obter uma lista ordenada<\/li>\n<\/ol>\n

    Quicksort foi inventado pelo cientista Charles Anthony Richard Hoare na Universidade Estadual de Moscou. Depois de aprender russo, ele estudou tradu\u00e7\u00e3o computacional, bem como teoria das probabilidades na escola Kolmogorov. Em 1960, devido \u00e0 crise pol\u00edtica, deixou a Uni\u00e3o Sovi\u00e9tica.<\/p>\n

    Exemplo de implementa\u00e7\u00e3o em Rust:<\/p>\n

    \n
    \n
    \nuse rand::Rng;\n\nfn swap(numbers: &mut [i64], from: usize, to: usize) {\n    let temp = numbers[from];\n    numbers[from] = numbers[to];\n    numbers[to] = temp;\n}\n\nfn quicksort(numbers: &mut [i64], left: usize, right: usize) {\n    if left >= right {\n        return\n    }\n    let length = right - left;\n    if length <= 1 {\n        return\n    }\n    let pivot_index = left + (length \/ 2);\n    let pivot = numbers[pivot_index];\n\n    let last_index = right - 1;\n    swap(numbers, pivot_index, last_index);\n\n    let mut less_insert_index = left;\n\n    for i in left..last_index {\n        if numbers[i] < pivot {\n            swap(numbers, i, less_insert_index);\n            less_insert_index += 1;\n        }\n    }\n    swap(numbers, last_index, less_insert_index);\n    quicksort(numbers, left, less_insert_index);\n    quicksort(numbers, less_insert_index + 1, right);\n}\n\nfn main() {\n    let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];\n    let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];\n\n    let mut rng = rand::thread_rng();\n    for i in 0..numbers.len() {\n        numbers[i] = rng.gen_range(-10..10);\n        reference_numbers[i] = numbers[i];\n    }\n\n    reference_numbers.sort();\n\n  println!(\"Numbers           {:?}\", numbers);\n  let length = numbers.len();\n  quicksort(&mut numbers, 0, length);\n  println!(\"Numbers           {:?}\", numbers);\n  println!(\"Reference numbers {:?}\", reference_numbers);\n\n  if numbers != reference_numbers {\n    println!(\"Validation failed\");\n    std::process::exit(1);\n  }\n  else {\n    println!(\"Validation success!\");\n    std::process::exit(0);\n  }\n}\n<\/code><\/pre>\n<\/div>\n<\/div>\n
    Se nada estiver claro, sugiro assistir ao v\u00eddeo de Rob Edwards, da Universidade de San Diego  https:\/\/www.youtube.com\/watch?v=ZHVk2blR45Q<\/a> mostra de maneira mais simples, passo a passo, a ess\u00eancia e a implementa\u00e7\u00e3o do algoritmo.<\/p>\n
    Links<\/h3>\n
    https:\/\/gitlab.com\/demensdeum \/algoritmos\/-\/tree\/master\/sortAlgorithms\/quickSort<\/a><\/p>\n
    Fontes<\/h3>\n
    https:\/\/www.youtube.com\/watch?v =4s-aG6yGGLU<\/a>
    https:\/\/www.youtube.com\/watch?v=ywWBy6J5gz8<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=Hoixgm4-P4M<\/a>
    \n    https:\/\/ru.wikipedia.org\/wiki\/\u0411\u044b\u0441\u0442\u0440\u0430\u044f_\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=Hoixgm4-P4M<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=XE4VP_8Y0BU<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=MZaf_9IZCrc<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=ZHVk2blR45Q<\/a>
    \n    http:\/\/rosettacode.org\/wiki\/Sorting_algorithms\/Quicksort<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=4s-aG6yGGLU<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=dQw4w9WgXcQ<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=maibrCbZWKw<\/a>
    \n    https:\/\/www.geeksforgeeks.org\/quick-sort\/<\/a>
    \n    https:\/\/www.youtube.com\/watch?v=uXBnyYuwPe8<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    Quicksort \u00e9 um algoritmo de classifica\u00e7\u00e3o de divis\u00e3o e conquista. Recursivamente, pe\u00e7a por pe\u00e7a, analisamos a matriz de n\u00fameros, colocando os n\u00fameros em ordem menor e maior a partir do elemento de refer\u00eancia selecionado, e inserimos o pr\u00f3prio elemento de refer\u00eancia no corte entre eles. Ap\u00f3s v\u00e1rias itera\u00e7\u00f5es recursivas, voc\u00ea ter\u00e1 uma lista ordenada. ComplexidadeContinue reading “Classifica\u00e7\u00e3o r\u00e1pida”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,199,190],"class_list":["post-3344","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-quicksort","tag-sorting","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"pt","enabled_languages":["en","ru","zh","de","fr","ja","pt"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/3344","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/comments?post=3344"}],"version-history":[{"count":20,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/3344\/revisions"}],"predecessor-version":[{"id":3880,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/posts\/3344\/revisions\/3880"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/media?parent=3344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/categories?post=3344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/pt\/wp-json\/wp\/v2\/tags?post=3344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}