fixed small bug in quick select algorithm

[BenjiAndre]

Pull Request Template

Description

This pull request fixes issue #714.

1. Fix partition Function

• Issue: The list.swap(right, store_index) statement was placed inside the loop, causing incorrect behavior during the partitioning step.
• Solution: Moved the list.swap(right, store_index) statement outside the loop to correctly move the pivot to its final place after partitioning.

2. Adjust Pivot Selection in quick_select Function

• Issue: The pivot index calculation was incorrect, potentially leading to out-of-range errors or incorrect partitioning.
• Solution: Adjusted the pivot index calculation to left + (right - left) / 2 to ensure a valid pivot index within the given range.

3. Correct Test Case

• Issue: The second test case had an incorrect expected value. The correct answer for the given inputs should be 9, not 12.
• Solution: Updated the expected value in the second test case from 12 to 9.

Detailed Changes

1. Partition Function:

   fn partition(list: &mut [i32], left: usize, right: usize, pivot_index: usize) -> usize {
      let pivot_value = list[pivot_index];
      list.swap(pivot_index, right); // Move pivot to end
      let mut store_index = left;
      for i in left..right {
          if list[i] < pivot_value {
              list.swap(store_index, i);
              store_index += 1;
          }
      }
      list.swap(right, store_index); // Move pivot to its final place
      store_index
   }

2. Quick Select Function:

   pub fn quick_select(list: &mut [i32], left: usize, right: usize, index: usize) -> i32 {
      if left == right {
          return list[left];
      }
      let mut pivot_index = left + (right - left) / 2; // select a pivotIndex between left and right
      pivot_index = partition(list, left, right, pivot_index);
      match index {
          x if x == pivot_index => list[index],
          x if x < pivot_index => quick_select(list, left, pivot_index - 1, index),
          _ => quick_select(list, pivot_index + 1, right, index),
      }
   }

3. Test Case Correction:

   #[cfg(test)]
   mod tests {
      use super::*;
      #[test]
      fn it_works() {
          let mut arr1 = [2, 3, 4, 5];
          assert_eq!(quick_select(&mut arr1, 0, 3, 1), 3);
          let mut arr2 = [2, 5, 9, 12, 16];
          assert_eq!(quick_select(&mut arr2, 1, 3, 2), 9); // Corrected to 9
          let mut arr3 = [0, 3, 8];
          assert_eq!(quick_select(&mut arr3, 0, 0, 0), 0);
      }
   }

These changes ensure the Quickselect algorithm functions correctly and the test cases produce the expected results.

Type of change

Please delete options that are not relevant.

• [x] Bug fix (non-breaking change which fixes an issue)

Checklist:

• [x] I ran bellow commands using the latest version of rust nightly.
• [x] I ran cargo clippy --all -- -D warnings just before my last commit and fixed any issue that was found.
• [x] I ran cargo fmt just before my last commit.
• [x] I ran cargo test just before my last commit and all tests passed.
• [x] I checked COUNTRIBUTING.md and my code follows its guidelines.

[codecov-commenter]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 95.00%. Comparing base (0cc792c) to head (5ec1c09).

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #727 +/- ## ========================================== - Coverage 95.01% 95.00% -0.01% ========================================== Files 303 303 Lines 22522 22522 ========================================== - Hits 21399 21398 -1 - Misses 1123 1124 +1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.