Home | Gaming | Programming | Play Online | Contact | Keyword Query
Games++ Games & Game Programming

GAMES++
Games++ Home
Games++ Gaming
Games++ Programming
Beta Testing Games
Free Online Games
Hints & Cheats

BROWSER UTILITIES
E-mail This Page
Add to Favorites

SITE SEARCH

Web Games++

AFFILIATES
Cheat Codes
Trickster Wiki
Game Ratings
Gameboy Cheats
PlayStation Cheats
BlackBerry Games
Photoshop Tutorials
Illustrator Tutorials
ImageReady Tutorials

ADVERTISEMENT

Comparison of Sorting Algorithms

The following table summarizes the basic strategies used in various sorting algorithms, and lists the algorithms that use these strategies.

Comparison-Based Sorting Methods

  • Transposition (exchange adjacent values)
    • Bubble Sort
  • Priority Queue (select largest value)
    • Selection Sort
    • Heap Sort
  • Insert and Keep Sorted
    • Insertion Sort
    • Tree Sort
  • Diminishing Increment
    • Shell Sort
  • Divide & Conquer
    • Quicksort
    • Merge Sort

Address-Calculation Sorting Methods

  • Radix Sort

The diagrams below may help you develop an intuitive sense of how the algorithms work. The vertical axis is the position within the array and the horizontal axis is time. Values within the array are represented by small squares with differing brightness. The goal of the algorithm is to sort the values from darkest to lightest. In each diagram, the input array is represented by a vertical column on the left, with an random assortment of brightess values. (Click on an image to see a larger version.)

[bubble sort]     [selection sort]     [insertion sort]     [quicksort]
      bubble            selection            insertion         quicksort

Bubble Sort exchanges adjacent values so lighter ones "bubble up" towards the top, and darker ones "sink down" towards the bottom. Selection Sort minimizes exchanges by scanning the unsorted portion to find the largest remaining value on each iteration. Insertion Sort is familiar to anyone who plays cards. It works by taking the next value from the unsorted portion and inserting it into the already sorted portion of the array. Of these three, Insertion Sort is the most efficient, on average, but Selection Sort is preferred when the records are large. Bubble Sort is never preferred. (Quicksort will be discussed later in this course.)

The following table summarizes what we have learned about the relative efficiency of various sorting algorithms.

Bubble Sort (Version from Class)

best case: about N comparisons, 0 exchanges, (input already sorted)

worst case: about N^2 comparisons, N^2 exchanges, (input sorted in reverse order)

average case: quite close to worst case (difficult to analyze)

notes: Very inefficient and should never be used. Uses an excessive and unnecessary number of exchanges.

Bubble Sort (Version from Textbook)

best case: about N^2/2 comparisons, 0 exchanges, (input already sorted)

worst, average cases: about N^2/2 comparisons, N^2/2 exchanges

Selection Sort

all cases: about N^2/2 comparisons, N exchanges

notes: minimizes the number of exchanges; execution time quite insensitive to original ordering of input data.

Insertion Sort

best case: about N comparisons, 0 moves, (input already sorted)

worst case: about N^2/2 comparisons, N^2/2 moves, (input sorted in reverse order)

average case: about N^2/4 comparisons, N^2/4 moves

notes: very efficient when input is "almost sorted"; moving a record is about half the work of exchanging two records, so average case is equivalent to roughly N^2/8 exchanges.

Copyright © 1998-2007, Games++ All rights reserved. | Privacy Policy