Selection, Bubble, and Insertion Sort

Chapter 18

Introduction

• To compare the performance of commonly used sorting algorithms, one must provide some analysis of these algorithms.

• These sorting algorithms can be applied to either array-based lists or linked lists.

Selection Sort

• The Selection Sort Algorithm: repeatedly select the smallest element from an unsorted portion of a list and moves it to the front..

• Steps for a selection sort:

  • Find the smallest element in the unsorted portion of the list

  • Move it to the top of the unsorted portion by swapping it with the currently-first element.

  • Start again with the rest of the list.

• Can also be applied to linked lists.

1 / 1

Example Selection Sort

Analysis: Selection Sort

• swap:
  Does three assignments; executed times.

• minIndex:

  • For a list of length , key comparisons.

  • Executed times (by selectionSort)

  • The number of key comparisons:

Bubble Sort

• Suppose list[0]...list[n-1] is a list of elements, indexed to .

• In a series of iterations, compare successive elements, list[index] and list[index + 1].

• If list[index] is greater than list[index + 1], then swap them.

1 / 1

Example Bubble Sort

Performance Analysis

• The Bubble-Sort algorithm contains nested loops.

  • The outer loop executes times.

  • For each iteration of the outer loop, the inner loop executes one fewer times.

• The total number of comparisons is:

• The number of assignments (worst case):

  because there are 3 assignments per swap operator.

Insertion Sort

The Insertion Sort Algorithm sorts the list by moving each element to its proper place in the sorted portion of the list.

1 / 1

Example Insertion Sort:
(This diagram shows just the first few steps.)

Implementation for Arrays

Let’s implement the Insertion Sort.

Performance Analysis

• The for-loop executes times.

• Best case (list is already sorted):
  Key comparisons:

• Worst case: for each iteration, the if statement evaluates to true.
  Key comparisons:

• Average number of key comparisons and of item assignments:

Lower Bound

Sorting Algorithm Comparison

Average Case Behavior of the Bubble Sort, Selection Sort, and Insertion Sort Algorithms for a List of Length .

Algorithm	Comparisons	Swaps
Bubble Sort
Selection Sort
Insertion Sort (Array Based)
Insertion Sort (Linked-List Based)

Lower Bound on Comparison-Based Sort Algorithms

Can we do better than for sorting?

What is the best we can do?

(Find the answers to these questions in the next module.)

Lab 10: Selection Sort, Bubble Sort, and Binary Search

Let’s take a look at Lab 10.