Sorting-in-rust-jadyn-nicholas created by GitHub Classroom


Sorting in Rust

Sorting tests


This lab uses various sorting algorithms as examples several features of the Rust programming language:

Here we've provided you with a sample Rust implementation of insertion sort, and you'll implement two other common sorting algorithms:

  • Quicksort
  • Merge sort

Insertion sort and quicksort can be done "in place", so they take a mutable array of values and destructively sort the given array.

Merge sort can't be done "in place" (it requires allocation of additional storage), so it is structured here to return a new Vec as its result.

There are lots of comments in the code on the various algorithms, but you might want to look them up in your favorite source if you're rusty (ho, ho) on those sorting algorithms.

Since you've dealt (at least a little) with arrays, slices, borrowing, and ownership in the Disemvowel in Rust lab we won't discuss them here, but we will say a little about traits.


Rust uses the concept of traits in a manner that is somewhat similar to interfaces in Java. A trait in Rust indicates a set of properties that a given type must have. A simplified signature for insertion_sort, for example, is:

    fn insertion_sort
   mut [T])

Here insertion_sort takes a single parameter v that is an array of items of type T. Now because we want to sort the items in the array, we need to be able to ask "less-than" questions about items of type T. That ability is provided by the trait PartialOrd. The annotation says that T can't just be any type – it must implement the PartialOrd trait, which ensures support for useful things like < and <=, which we'll clearly need to sort.

You can require a type to have several traits, joining them together with the + operator like this:

    fn insertion_sort
   PartialOrd + std::fmt::Debug>(v: 
   mut [T])

This is the actual signature for insertion_sort in the sample code, and says that T has to support two traits: PartialOrd and Debug. (The ability to support multiple traits in Rust is similar to the ability to implement multiple interfaces in Java.) The Debug trait allows you to print data using the {:?} format, which generates output in a programmer-friendly manner that is hopefully useful for debugging. We don't need this here (the code you're given doesn't actually use it), but it might be helpful if you want/need to add some printing to debug things as you're working on your implementation.

Lastly, one consequence of merge sort returning a new vector (instead of sorting the array in place) is that it requires the ability to copy elements from the input array into the output vector. Insertion sort and quicksort don't need that because they can use the .swap() method on arrays (which essentially swaps pointers on non-primitives instead of copying them).

This requires the addition of yet another trait (Copy) to T in the signature of merge_sort:

    fn merge_sort
   PartialOrd + std::marker::
   Copy + std::fmt::Debug>(v: 
   &[T]) -> 

Adding this trait allows us to perform actions that require copying such as:


Luckily integers (which is all we use here) already implement both the PartialOrd and the Copy traits, so we're good to go. If we needed to sort something more complex (like an array of student records), then we'd have to decide

  • How to implement the PartialOrd trait, perhaps by sorting by ID numbers, or we could be brave and attempt some sort of sorting by name.
  • If and how we are willing to implement the Copy trait. As a rule we probably don't want to copy entire student records, so we'd have to figure out what makes sense in our particular situation.

Running the code and the tests

This is set up so that running the program (with cargo run) will run and time all three sorting algorithms on a randomly generated array of integers. Since insertion sort is O(N^2) and the other two are O(N log N), we would expect them to be faster. We might also expect quicksort to be faster (by a constant factor) than merge sort since quicksort doesn't need to copy elements around. Feel free to increase the value of the size constant at the top of the code to see how that affects the timing.

Use cargo test to run the tests "by hand". The insertion sort tests should pass without you having to do anything. Some of the quicksort and merge sort tests may pass initially "for free" even though you know you haven't actually implemented anything. This is just because the default "silly" things that we do for those happen to be correct for things like empty lists of values.

When running either the program or the tests, you'll initially get a warning like:

warning: unused variable: `ys`
   --> src/
171 | fn merge
    (xs: Vec
     , ys: Vec
      ) -> Vec
    |                                                                           ^^ help: if this is intentional, prefix it with an underscore: `_ys`
    = note: `#[warn(unused_variables)]` on by default


This is just telling you that the stub code that we provided doesn't use the parameter ys. As you properly implement merge() you'll presumably use both arguments and this warning will go away.

To Do

The canvas rubric provides detailed information on how you will be graded. The provided tests (which you can run with cargo test) should provide some reasonable feedback on the correctness of your solution, but passing the tests never guarantees complete correctness. The badge at the top of this README should also indicate whether your tests are passing in GitHub Actions.

  • Implement quicksort
  • Implement merge sort
  • Ensure that the tests pass
  • Code and commits should be understandable and useful
You might also like...
Rust programs written entirely in Rust

mustang Programs written entirely in Rust Mustang is a system for building programs built entirely in Rust, meaning they do not depend on any part of

Rust 核心库和标准库的源码级中文翻译,可作为 IDE 工具的智能提示 (Rust core library and standard library translation. can be used as IntelliSense for IDE tools)

Rust 标准库中文版 这是翻译 Rust 库 的地方, 相关源代码来自于。 如果您不会说英语,那么拥有使用中文的文档至关重要,即使您会说英语,使用母语也仍然能让您感到愉快。Rust 标准库是高质量的,不管是新手还是老手,都可以从中

A library for extracting #[no_mangle] pub extern "C" functions (

A library for extracting #[no_mangle] pub extern "C" functions In order to expose a function with C binary interface for interoperability with other p

clone of grep cli written in Rust. From Chapter 12 of the Rust Programming Language book

minigrep is a clone of the grep cli in rust Minigrep will find a query string in a file. To test it out, clone the project and run cargo run body poem

Rust-blog - Educational blog posts for Rust beginners

pretzelhammer's Rust blog 🦀 I write educational content for Rust beginners and Rust advanced beginners. My posts are listed below in reverse chronolo

The ray tracer challenge in rust - Repository to follow my development of
The ray tracer challenge in rust - Repository to follow my development of "The Raytracer Challenge" book by Jamis Buck in the language Rust

The Ray Tracer Challenge This repository contains all the code written, while step by implementing Ray Tracer, based on the book "The Ray Tracer Chall

Learn-rust-the-hard-way - "Learn C The Hard Way" by Zed Shaw Converted to Rust

Learn Rust The Hard Way This is an implementation of Zed Shaw's Learn X The Hard Way for the Rust Programming Language. Installing Rust TODO: Instruct

Learn to write Rust procedural macros [Rust Latam conference, Montevideo Uruguay, March 2019]
Learn to write Rust procedural macros [Rust Latam conference, Montevideo Uruguay, March 2019]

Rust Latam: procedural macros workshop This repo contains a selection of projects designed to learn to write Rust procedural macros — Rust code that g

The Rust Compiler Collection is a collection of compilers for various languages, written with The Rust Programming Language.

rcc The Rust Compiler Collection is a collection of compilers for various languages, written with The Rust Programming Language. Compilers Language Co

  • Feedback


    :wave:! GitHub Classroom created this pull request as a place for your teacher to leave feedback on your work. It will update automatically. Don’t close or merge this pull request, unless you’re instructed to do so by your teacher. In this pull request, your teacher can leave comments and feedback on your code. Click the Subscribe button to be notified if that happens. Click the Files changed or Commits tab to see all of the changes pushed to main since the assignment started. Your teacher can see this too.

    Notes for teachers Use this PR to leave feedback. Here are some tips: - Click the **Files changed** tab to see all of the changes pushed to `main` since the assignment started. To leave comments on specific lines of code, put your cursor over a line of code and click the blue **+** (plus sign). To learn more about comments, read “[Commenting on a pull request](”. - Click the **Commits** tab to see the commits pushed to `main`. Click a commit to see specific changes. - If you turned on autograding, then click the **Checks** tab to see the results. - This page is an overview. It shows commits, line comments, and general comments. You can leave a general comment below. For more information about this pull request, read “[Leaving assignment feedback in GitHub](”.

    Subscribed: @JadynSondrol @miiiiip

    opened by github-classroom[bot] 0
learn_rust_rustlings-qinyuhang created by GitHub Classroom

rustlings ?? ❤️ Greetings and welcome to rustlings. This project contains small exercises to get you used to reading and writing Rust code. This inclu

The Learning&Training Hub of OS Kernel 2 Oct 22, 2022
Simple RESTful API in rust created with actix-web. (Routing, models, JWT auth).

rust-simple-api Simple RESTful API created with rust, actix-web, Diesel, JWT. Running application Manual Firstly generate a secret.key which will be u

null 2 Jul 30, 2022
A simple programming language, created for AP Computer Science

A simple programming language, created for AP Computer Science

Michelle S. 3 Sep 2, 2022
kickable - a crate created to answer the age old question

kickable kickable is a crate created to answer the age old question... "Can I Kick It?" This package is for showcase purposes only. What is a kickable

@defstream 4 Jan 12, 2023
The second Rust implementation on GitHub of third-party REST API client for Bilibili.

Bilibili REST API The second Rust implementation on GitHub of third-party REST API client for Bilibili. Designed to be lightweight and efficient. It's

null 4 Aug 25, 2022
Tools for managing GitHub block lists

GitHub block list management Octocrabby is a small set of command-line tools and Octocrab extensions that are focused on managing block lists on GitHu

Travis Brown 97 Nov 3, 2022
Automatically deploy from GitHub to Replit, lightning fast ⚡️

repl.deploy Automatically deploy from GitHub to Replit, lightning fast ⚡️ repl.deploy is split into A GitHub app, which listens for code changes and s

Khushraj Rathod 78 Dec 22, 2022
example codes for CIS198

CIS198: RUST 编程语言 学习背景 rust 和 c/c++/Java/Python/golang 不太一样 rust 学习曲线比较陡峭 rust 有很多颠覆认知的特性: 所有权,生命周期,借用检测 cargo 工具 函数式+命令式支持 视频讲解见 B站 课程大纲 Timeline Lec

Jinghui Hu 3 Apr 9, 2024
Leetcode Solutions in Rust, Advent of Code Solutions in Rust and more

RUST GYM Rust Solutions Leetcode Solutions in Rust AdventOfCode Solutions in Rust This project demostrates how to create Data Structures and to implem

Larry Fantasy 635 Jan 3, 2023
Simple autoclicker written in Rust, to learn the Rust language.

RClicker is an autoclicker written in Rust, written to learn more about the Rust programming language. RClicker was was written by me to learn more ab

null 7 Nov 15, 2022