Help us understand the problem. What is going on with this article?

Rustで書くソートアルゴリズム

Emma Bostianの“De-Coding The Technical Interview Process”では、Javascriptで書かれたソートアルゴリズムがわかりやすく紹介されている。読みながら、Rustのいい紹介ないかなと探したら、ちょうどいい投稿が見つからなかったので、自分で修正しながらまとめた。

エピステミックステータス:学習中
(詳しい説明は今度追加する予定)

以下がクイックソート、マージソートとバブルソートの例:

バブルソート

これは一番簡単なやつ。

fn sort(array: &mut Vec<i32>) {
  for i in 0..array.len() {
    for j in 0..array.len() - i - 1 {
      if array[j + 1] < array[j] {
        // let tmp = array[j];
        // array[j] = array[j + 1];
        // array[j + 1] = tmp;
        array.swap(j, j + 1);
      }
    }
  }
}

マージソート

マージソートは2つの関数, sortmergeで実現するのがベストっぽい。

fn sort(array: &mut [i32]) {
  let middle = array.len() / 2;
  if array.len() < 2 {
    return; // No need to sort vectors with one element
  }

  let mut sorted = array.to_vec();

  sort(&mut array[..middle]);
  sort(&mut array[middle..]);

  merge(&array[..middle], &array[middle..], &mut sorted);

  array.copy_from_slice(&sorted); // Copy the sorted result into original vector
}

fn merge(l_arr: &[i32], r_arr: &[i32], sorted: &mut [i32]) {
  // Current loop position in left half, right half, and sorted vector
  let (mut left, mut right, mut i) = (0, 0, 0);

  while left < l_arr.len() && right < r_arr.len() {
    if l_arr[left] <= r_arr[right] {
      sorted[i] = l_arr[left];
      i += 1;
      left += 1;
    } else {
      sorted[i] = r_arr[right];
      i += 1;
      right += 1;
    }
  }

  if left < l_arr.len() {
    // If there is anything left in the left half append it after sorted members
    sorted[i..].copy_from_slice(&l_arr[left..]);
  }

  if right < r_arr.len() {
    // If there is anything left in the right half append it after sorted members
    sorted[i..].copy_from_slice(&r_arr[right..]);
  }
}

クイックソート

これは一番ややこしいアルゴリズム。スペースを重視すると、分割(partitioning)はin-placeでしないといけないので。さらに、Rustでは関数のパラメタにデフォルトの値を設定できないので、わざわざ0から最後のインデックスまで全配列をソートしたいと明示しなくてもいいように、エントリーポイント的な関数が必要になる。

fn sort(array: &mut [i32]) {
  let start = 0;
  let end = array.len() - 1;
  quick_sort_partition(array, start, end as isize);
}

fn quick_sort_partition(array: &mut [i32], start: isize, end: isize) {
  if start < end && end - start >= 1 {
    let pivot = partition(array, start as isize, end as isize);
    quick_sort_partition(array, start, pivot - 1);
    quick_sort_partition(array, pivot + 1, end);
  }
}

fn partition(array: &mut [i32], l: isize, h: isize) -> isize {
  let pivot = array[h as usize];
  let mut i = l - 1; // Index of the smaller element

  for j in l..h {
    if array[j as usize] <= pivot {
      i = i + 1;
      array.swap(i as usize, j as usize);
    }
  }

  array.swap((i + 1) as usize, h as usize);

  i + 1
}

以上のアルゴリズムをGithubにもあげている:https://github.com/jlkiri/rust-sorting-algorithms

jlkiri
Webでのユーザーインターフェースを作っています @ Yumemi Co., Ltd.
https://www.kirillvasiltsov.com/
yumemi
みんなが知ってるあのサービス、実はゆめみが作ってます。スマホアプリ/Webサービスの企画・UX/UI設計、開発運用。Swift, Kotlin, PHP, Vue.js, React.js, Node.js, AWS等エンジニア・クリエイターの会社です。東京(三軒茶屋)/京都(四条烏丸)/札幌/大阪/福岡に展開中!Twitterで情報配信中https://twitter.com/yumemiinc
http://www.yumemi.co.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした