Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
43
Help us understand the problem. What is going on with this article?
@jlkiri

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

More than 1 year has passed since last update.

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

43
Help us understand the problem. What is going on with this article?
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
jlkiri
ユーザーインターフェースと開発者ツール開発 (User interface & developer tools development) @ Yumemi Co., Ltd.
yumemi
みんなが知ってるあのサービス、実はゆめみが作ってます。スマホアプリ/Webサービスの企画・UX/UI設計、開発運用。Swift, Kotlin, PHP, Vue.js, React.js, Node.js, AWS等エンジニア・クリエイターの会社です。Twitterで情報配信中https://twitter.com/yumemiinc

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
43
Help us understand the problem. What is going on with this article?