<title>challenges/bubble_sort.markdown at master · turingschool/challenges · GitHub</title>
<link rel="search" type="application/opensearchdescription+xml" href="/opensearch.xml" title="GitHub">
<link rel="fluid-icon" href="https://github.com/fluidicon.png" title="GitHub">
<link rel="apple-touch-icon" sizes="57x57" href="/apple-touch-icon-114.png">
<link rel="apple-touch-icon" sizes="114x114" href="/apple-touch-icon-114.png">
<link rel="apple-touch-icon" sizes="72x72" href="/apple-touch-icon-144.png">
<link rel="apple-touch-icon" sizes="144x144" href="/apple-touch-icon-144.png">
<meta property="fb:app_id" content="1401488693436528">
<meta content="@github" name="twitter:site" /><meta content="summary" name="twitter:card" /><meta content="turingschool/challenges" name="twitter:title" /><meta content="Contribute to challenges development by creating an account on GitHub." name="twitter:description" /><meta content="https://avatars3.githubusercontent.com/u/7934292?v=3&s=400" name="twitter:image:src" />
<meta content="GitHub" property="og:site_name" /><meta content="object" property="og:type" /><meta content="https://avatars3.githubusercontent.com/u/7934292?v=3&s=400" property="og:image" /><meta content="turingschool/challenges" property="og:title" /><meta content="https://github.com/turingschool/challenges" property="og:url" /><meta content="Contribute to challenges development by creating an account on GitHub." property="og:description" />
<meta name="browser-stats-url" content="https://api.github.com/_private/browser/stats">
<meta name="browser-errors-url" content="https://api.github.com/_private/browser/errors">
<link rel="assets" href="https://assets-cdn.github.com/">
<meta name="pjax-timeout" content="1000">
<meta name="msapplication-TileImage" content="/windows-tile.png">
<meta name="msapplication-TileColor" content="#ffffff">
<meta name="selected-link" value="repo_source" data-pjax-transient>
<meta name="google-analytics" content="UA-3769691-2">
<meta content="collector.githubapp.com" name="octolytics-host" /><meta content="collector-cdn.github.com" name="octolytics-script-host" /><meta content="github" name="octolytics-app-id" /><meta content="4999852B:68F1:1460FFE:55679954" name="octolytics-dimension-request_id" />
<meta content="Rails, view, blob#show" name="analytics-event" />
<meta class="js-ga-set" name="dimension1" content="Logged Out">
<meta class="js-ga-set" name="dimension2" content="Header v3">
<meta name="is-dotcom" content="true">
<meta name="hostname" content="github.com">
<meta name="user-login" content="">
<link rel="icon" type="image/x-icon" href="https://assets-cdn.github.com/favicon.ico">
<meta content="authenticity_token" name="csrf-param" />
<link href="https://assets-cdn.github.com/assets/github/index-a377bfb367623b04e93275d8c48c849ba6a4f2043cd8bb31bc4c800d067d19bf.css" media="all" rel="stylesheet" />
<link href="https://assets-cdn.github.com/assets/github2/index-61b03ff5216fa723fa0e7b7373816fdf3bd691c57a3414598d77e456b0c4c108.css" media="all" rel="stylesheet" />
<meta http-equiv="x-pjax-version" content="79af601d77a8e3686a92bae99387fe7b">
<div class="header header-logged-out" role="banner">
<a class="header-logo-wordmark" href="https://github.com/" data-ga-click="(Logged out) Header, go to homepage, icon:logo-wordmark">
<span class="mega-octicon octicon-logo-github"></span>
</a>
<div class="header-actions" role="navigation">
<a class="btn btn-primary" href="/join" data-ga-click="(Logged out) Header, clicked Sign up, text:sign-up">Sign up</a>
<a class="btn" href="/login?return_to=%2Fturingschool%2Fchallenges%2Fblob%2Fmaster%2Fbubble_sort.markdown" data-ga-click="(Logged out) Header, clicked Sign in, text:sign-in">Sign in</a>
</div>
<div class="site-search repo-scope js-site-search" role="search">
<form accept-charset="UTF-8" action="/turingschool/challenges/search" class="js-site-search-form" data-global-search-url="/search" data-repo-search-url="/turingschool/challenges/search" method="get"><div style="margin:0;padding:0;display:inline"><input name="utf8" type="hidden" value="✓" /></div>
This repository
<ul class="header-nav left" role="navigation">
<li class="header-nav-item">
<a class="header-nav-link" href="/explore" data-ga-click="(Logged out) Header, go to explore, text:explore">Explore</a>
</li>
<li class="header-nav-item">
<a class="header-nav-link" href="/features" data-ga-click="(Logged out) Header, go to features, text:features">Features</a>
</li>
<li class="header-nav-item">
<a class="header-nav-link" href="https://enterprise.github.com/" data-ga-click="(Logged out) Header, go to enterprise, text:enterprise">Enterprise</a>
</li>
<li class="header-nav-item">
<a class="header-nav-link" href="/blog" data-ga-click="(Logged out) Header, go to blog, text:blog">Blog</a>
</li>
</ul>
<div id="start-of-content" class="accessibility-aid"></div>
<div class="site" itemscope itemtype="http://schema.org/WebPage">
<div id="js-flash-container">
</div>
<div class="pagehead repohead instapaper_ignore readability-menu">
<div class="container">
- Watch 10
-
Star
<a class="social-count js-social-count" href="/turingschool/challenges/stargazers"> 9 </a>
<li>
<a href="/login?return_to=%2Fturingschool%2Fchallenges"
class="btn btn-sm btn-with-count tooltipped tooltipped-n"
aria-label="You must be signed in to fork a repository" rel="nofollow">
<span class="octicon octicon-repo-forked"></span>
Fork
</a>
<a href="/turingschool/challenges/network" class="social-count">
26
</a>
</li>
<h1 itemscope itemtype="http://data-vocabulary.org/Breadcrumb" class="entry-title public">
<span class="mega-octicon octicon-repo"></span>
<span class="author"><a href="/turingschool" class="url fn" itemprop="url" rel="author"><span itemprop="title">turingschool</span></a></span><!--
--><span class="path-divider">/</span><!--
--><strong><a href="/turingschool/challenges" class="js-current-repository" data-pjax="#js-repo-pjax-container">challenges</a></strong>
<span class="page-context-loader">
<img alt="" height="16" src="https://assets-cdn.github.com/assets/spinners/octocat-spinner-32-e513294efa576953719e4e2de888dd9cf929b7d62ed8d05f25e731d02452ab6c.gif" width="16" />
</span>
</h1>
</div><!-- /.container -->
</div><!-- /.repohead -->
<div class="container">
<div class="repository-with-sidebar repo-container new-discussion-timeline ">
<div class="repository-sidebar clearfix">
-
Code
<li class="tooltipped tooltipped-w" aria-label="Issues">
<a href="/turingschool/challenges/issues" aria-label="Issues" class="js-selected-navigation-item sunken-menu-item" data-hotkey="g i" data-selected-links="repo_issues repo_labels repo_milestones /turingschool/challenges/issues">
<span class="octicon octicon-issue-opened"></span> <span class="full-word">Issues</span>
<span class="js-issue-replace-counter"></span>
<img alt="" class="mini-loader" height="16" src="https://assets-cdn.github.com/assets/spinners/octocat-spinner-32-e513294efa576953719e4e2de888dd9cf929b7d62ed8d05f25e731d02452ab6c.gif" width="16" />
<li class="tooltipped tooltipped-w" aria-label="Pull requests">
<a href="/turingschool/challenges/pulls" aria-label="Pull requests" class="js-selected-navigation-item sunken-menu-item" data-hotkey="g p" data-selected-links="repo_pulls /turingschool/challenges/pulls">
<span class="octicon octicon-git-pull-request"></span> <span class="full-word">Pull requests</span>
<span class="js-pull-replace-counter"></span>
<img alt="" class="mini-loader" height="16" src="https://assets-cdn.github.com/assets/spinners/octocat-spinner-32-e513294efa576953719e4e2de888dd9cf929b7d62ed8d05f25e731d02452ab6c.gif" width="16" />
<li class="tooltipped tooltipped-w" aria-label="Pulse">
<a href="/turingschool/challenges/pulse" aria-label="Pulse" class="js-selected-navigation-item sunken-menu-item" data-selected-links="pulse /turingschool/challenges/pulse">
<span class="octicon octicon-pulse"></span> <span class="full-word">Pulse</span>
<img alt="" class="mini-loader" height="16" src="https://assets-cdn.github.com/assets/spinners/octocat-spinner-32-e513294efa576953719e4e2de888dd9cf929b7d62ed8d05f25e731d02452ab6c.gif" width="16" />
<li class="tooltipped tooltipped-w" aria-label="Graphs">
<a href="/turingschool/challenges/graphs" aria-label="Graphs" class="js-selected-navigation-item sunken-menu-item" data-selected-links="repo_graphs repo_contributors /turingschool/challenges/graphs">
<span class="octicon octicon-graph"></span> <span class="full-word">Graphs</span>
<img alt="" class="mini-loader" height="16" src="https://assets-cdn.github.com/assets/spinners/octocat-spinner-32-e513294efa576953719e4e2de888dd9cf929b7d62ed8d05f25e731d02452ab6c.gif" width="16" />
<div class="only-with-full-nav">
<a href="/turingschool/challenges/archive/master.zip"
class="btn btn-sm sidebar-button"
aria-label="Download the contents of turingschool/challenges as a zip file"
title="Download the contents of turingschool/challenges as a zip file"
rel="nofollow">
<span class="octicon octicon-cloud-download"></span>
Download ZIP
</a>
</div>
</div><!-- /.repository-sidebar -->
<div id="js-repo-pjax-container" class="repository-content context-loader-container" data-pjax-container>
branch:
master
<div class="select-menu-modal">
<div class="select-menu-header">
<span class="select-menu-title">Switch branches/tags</span>
<span class="octicon octicon-x js-menu-close" role="button" aria-label="Close"></span>
</div>
<div class="select-menu-filters">
<div class="select-menu-text-filter">
<input type="text" aria-label="Filter branches/tags" id="context-commitish-filter-field" class="js-filterable-field js-navigation-enable" placeholder="Filter branches/tags">
</div>
<div class="select-menu-tabs">
<ul>
<li class="select-menu-tab">
<a href="#" data-tab-filter="branches" data-filter-placeholder="Filter branches/tags" class="js-select-menu-tab">Branches</a>
</li>
<li class="select-menu-tab">
<a href="#" data-tab-filter="tags" data-filter-placeholder="Find a tag…" class="js-select-menu-tab">Tags</a>
</li>
</ul>
</div>
</div>
<div class="select-menu-list select-menu-tab-bucket js-select-menu-tab-bucket" data-tab-filter="branches">
<div data-filterable-for="context-commitish-filter-field" data-filterable-type="substring">
<a class="select-menu-item js-navigation-item js-navigation-open "
href="/turingschool/challenges/blob/backgrounding-homework/bubble_sort.markdown"
data-name="backgrounding-homework"
data-skip-pjax="true"
rel="nofollow">
<span class="select-menu-item-icon octicon octicon-check"></span>
<span class="select-menu-item-text css-truncate-target" title="backgrounding-homework">
backgrounding-homework
</span>
</a>
<a class="select-menu-item js-navigation-item js-navigation-open "
href="/turingschool/challenges/blob/gringotts/bubble_sort.markdown"
data-name="gringotts"
data-skip-pjax="true"
rel="nofollow">
<span class="select-menu-item-icon octicon octicon-check"></span>
<span class="select-menu-item-text css-truncate-target" title="gringotts">
gringotts
</span>
</a>
<a class="select-menu-item js-navigation-item js-navigation-open selected"
href="/turingschool/challenges/blob/master/bubble_sort.markdown"
data-name="master"
data-skip-pjax="true"
rel="nofollow">
<span class="select-menu-item-icon octicon octicon-check"></span>
<span class="select-menu-item-text css-truncate-target" title="master">
master
</span>
</a>
</div>
<div class="select-menu-no-results">Nothing to show</div>
</div>
<div class="select-menu-list select-menu-tab-bucket js-select-menu-tab-bucket" data-tab-filter="tags">
<div data-filterable-for="context-commitish-filter-field" data-filterable-type="substring">
</div>
<div class="select-menu-no-results">Nothing to show</div>
</div>
</div>
challenges/bubble_sort.markdown
<div class="participation">
<p class="quickstat">
<a href="#blob_contributors_box" rel="facebox">
<strong>2</strong>
contributors
</a>
</p>
<a class="avatar-link tooltipped tooltipped-s" aria-label="jcasimir" href="/turingschool/challenges/commits/master/bubble_sort.markdown?author=jcasimir"><img alt="@jcasimir" class="avatar" data-user="43102" height="20" src="https://avatars1.githubusercontent.com/u/43102?v=3&s=40" width="20" /> </a>
<a class="avatar-link tooltipped tooltipped-s" aria-label="worace" href="/turingschool/challenges/commits/master/bubble_sort.markdown?author=worace"><img alt="@worace" class="avatar" data-user="1227440" height="20" src="https://avatars3.githubusercontent.com/u/1227440?v=3&s=40" width="20" /> </a>
</div>
<div id="blob_contributors_box" style="display:none">
<h2 class="facebox-header">Users who have contributed to this file</h2>
<ul class="facebox-user-list">
<li class="facebox-user-list-item">
<img alt="@jcasimir" data-user="43102" height="24" src="https://avatars3.githubusercontent.com/u/43102?v=3&s=48" width="24" />
<a href="/jcasimir">jcasimir</a>
</li>
<li class="facebox-user-list-item">
<img alt="@worace" data-user="1227440" height="24" src="https://avatars1.githubusercontent.com/u/1227440?v=3&s=48" width="24" />
<a href="/worace">worace</a>
</li>
</ul>
</div>
<div class="btn-group">
<a href="/turingschool/challenges/raw/master/bubble_sort.markdown" class="btn btn-sm " id="raw-url">Raw</a>
<a href="/turingschool/challenges/blame/master/bubble_sort.markdown" class="btn btn-sm js-update-url-with-hash">Blame</a>
<a href="/turingschool/challenges/commits/master/bubble_sort.markdown" class="btn btn-sm " rel="nofollow">History</a>
</div>
<button type="button" class="octicon-btn disabled tooltipped tooltipped-n" aria-label="You must be signed in to make or propose changes">
<span class="octicon octicon-pencil"></span>
</button>
<button type="button" class="octicon-btn octicon-btn-danger disabled tooltipped tooltipped-n" aria-label="You must be signed in to make or propose changes">
<span class="octicon octicon-trashcan"></span>
</button>
</div>
<div class="file-info">
98 lines (72 sloc)
<span class="file-info-divider"></span>
4.072 kb
</div>
Sorting algorithms are one of the common domains for studying Computer Science data structures and algorithms. The most straight forward is Bubble Sort.
Bubble sort works by comparing and possibly swapping two values in a set. Say we start with this set of numbers:
1 0 2 3 4 5
The algorithm would start with a variable previous pointing to the first element,
1 and current pointing to the second value 0. Then if current is
less than previous then the two values are swapped. The swap would take
place in this case. After that single swap the sequence would be:
0 1 2 3 4 5
The algorithm would restart with previous pointing at the first position and
current at the second position. 1 is not less than 0, so the focus shifts
one spot to the right. previous now holds 1 and current holds 2. They
do not need to be swapped. This repeats moving right one space at a time until
reaching the end of the set, meaning the set is sorted.
Let's look at the sequence for a more out-of-order sequence:
Pre-Sequence Previous Current Swap? Post-Sequence
4 3 5 0 1 4 3 Y 3 4 5 0 1
3 4 5 0 1 3 4 N 3 4 5 0 1
3 4 5 0 1 4 5 N 3 4 5 0 1
3 4 5 0 1 5 0 Y 3 4 0 5 1
3 4 0 5 1 3 4 N 3 4 0 5 1
3 4 0 5 1 4 0 Y 3 0 4 5 1
3 0 4 5 1 3 0 Y 0 3 4 5 1
0 3 4 5 1 0 3 N 0 3 4 5 1
0 3 4 5 1 3 4 N 0 3 4 5 1
0 3 4 5 1 4 5 N 0 3 4 5 1
0 3 4 5 1 5 1 Y 0 3 4 1 5
0 3 4 1 5 0 3 N 0 3 4 1 5
0 3 4 1 5 3 4 N 0 3 4 1 5
0 3 4 1 5 4 1 Y 0 3 1 4 5
0 3 1 4 5 0 3 N 0 3 1 4 5
0 3 1 4 5 3 1 Y 0 1 3 4 5
0 1 3 4 5 0 1 N 0 1 3 4 5
0 1 3 4 5 1 3 N 0 1 3 4 5
0 1 3 4 5 3 4 N 0 1 3 4 5
0 1 3 4 5 4 5 N 0 1 3 4 5
0 1 3 4 5 5 nil
Once that nil pops up in current then we're done! We'd say that this run
of the algorithm made 7 swaps.
Write an implementation of bubble sort that does not use any custom classes.
You'll likely want to use methods and will surely needs arrays and a while loop.
In addition to writing an implementation following the template below, answer the following questions:
- Given the numbers 0 through 5, what would be the worst case scenario for bubble sort (aka, what order would necessitate the most swaps)?
- How many swaps would that worst case take?
- The example above took 21 iterations to get to a result. Can you tweak the
algorithm so that it takes the same number of swaps (
7) but fewer total operations?
sequence = [4, 3, 5, 0, 1] swaps = 0# Your Code Here
puts "Final result: #{result}" puts "Swaps: #{swaps}"
Implement bubble sort using one or more classes and many tests. Remember to spiral up your design. What's the simplest possible case? What's the next smallest step from there?
The version of bubble sort described above is actually a slightly simplified version of the algorithm which uses a "short-circuiting" approach to making successive iterations. As soon as a number is swapped, go back to the beginning of the list and try again. According to the "real" algorithm, every pass should actually iterate completely through the list, and then decide whether another pass is needed.
See if you can write another, slightly modified, version of the algorithm which follows this pattern. You'll need to add some code to keep track during each pass of whether a swap has been made any time during that pass. The wikipedia entry on bubble sort has some useful visualizations of the process which you can refer to to aid your understanding.
Go
</div>
</div><!-- /.repo-container -->
<div class="modal-backdrop"></div>
</div><!-- /.container -->
</div><!-- /.wrapper -->
<div class="container">
<div class="fullscreen-overlay js-fullscreen-overlay" id="fullscreen_overlay">
<textarea name="fullscreen-contents" id="fullscreen-contents" class="fullscreen-contents js-fullscreen-contents" placeholder=""></textarea>
<div id="ajax-error-message" class="flash flash-error">
<span class="octicon octicon-alert"></span>
<a href="#" class="octicon octicon-x flash-close js-ajax-error-dismiss" aria-label="Dismiss error"></a>
Something went wrong with that request. Please try again.
</div>
<script crossorigin="anonymous" src="https://assets-cdn.github.com/assets/frameworks-447ce66a36506ebddc8e84b4e32a77f6062f3d3482e77dd21a77a01f0643ad98.js"></script>
<script async="async" crossorigin="anonymous" src="https://assets-cdn.github.com/assets/github/index-3f56bddce210ff05608078010cccdc986eae099e28cba689d52ed7f702a91123.js"></script>