{"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\/2022\/07\/30\/quicksort\/","title":{"rendered":"Quicksort"},"content":{"rendered":"

Quicksort is a divide-and-conquer sorting algorithm. Recursively, we sort the array of numbers in parts, placing the numbers in smaller and larger order from the selected pivot element, and insert the pivot element itself into the gap between them. After several recursive iterations, we get a sorted list. Time complexity is O(n2<\/sup>).<\/p>\n

Scheme:<\/p>\n

    \n
  1. We start by getting the list of elements from the outside, the sorting boundaries. In the first step, the sorting boundaries will be from the beginning to the end.<\/li>\n
  2. We check that the boundaries of the beginning and end do not intersect, if this happens, then it’s time to finish<\/li>\n
  3. We select some element from the list, call it the reference<\/li>\n
  4. Move it to the right at the end to the last index so it doesn’t get in the way<\/li>\n
  5. Create a counter of *smaller numbers* that is still equal to zero<\/li>\n
  6. We go through the list in a loop from left to right, up to the last index where the reference element is located, not inclusive<\/li>\n
  7. Each element is compared with the reference<\/li>\n
  8. If it is less than the reference, then we swap them by the index of the counter of smaller numbers. We increment the counter of smaller numbers.<\/li>\n
  9. When the cycle reaches the reference element, we stop and swap the reference element with the element with the counter of smaller numbers.<\/li>\n
  10. We run the algorithm separately for the left smaller part of the list, and separately for the right larger part of the list.<\/li>\n
  11. Eventually all recursive iterations will start to stop due to the check in point 2<\/li>\n
  12. Get a sorted list<\/li>\n<\/ol>\n

    Quicksort was invented by scientist Charles Anthony Richard Hoare at Moscow State University, who, having learned Russian, studied computer translation and probability theory at the Kolmogorov School. In 1960, due to the political crisis, he left the Soviet Union.<\/p>\n

    Example implementation in 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
    If nothing is clear, I suggest watching a video by Rob Edwards from the University of San Diego https:\/\/www.youtube.com\/watch?v=ZHVk2blR45Q<\/a> it shows the essence and implementation of the algorithm in the simplest way, step by step.<\/p>\n
    Links<\/h3>\n
    https:\/\/gitlab.com\/demensdeum \/algorithms\/-\/tree\/master\/sortAlgorithms\/quickSort<\/a><\/p>\n
    Sources<\/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 is a divide-and-conquer sorting algorithm. Recursively, we sort the array of numbers in parts, placing the numbers in smaller and larger order from the selected pivot element, and insert the pivot element itself into the gap between them. After several recursive iterations, we get a sorted list. Time complexity is O(n2). Scheme: We startContinue reading “Quicksort”<\/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":"en","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\/wp-json\/wp\/v2\/posts\/3344","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/comments?post=3344"}],"version-history":[{"count":20,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3344\/revisions"}],"predecessor-version":[{"id":3880,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3344\/revisions\/3880"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/media?parent=3344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/categories?post=3344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/tags?post=3344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}