**Sorting Algorithm Tutorials - Herong's Tutorial Examples** - Version 6.01, by Dr. Herong Yang

Selection Sort - Performance

This section provides a tutorial on how to measure the performance of the Selection Sort algorithm. My first Java implementation of Selection Sort is performing at the O(N*N) order level.

Now let's see how my Java implementation of the Selection Sort algorithm performs. I tried this implementation with my SortTest.java under JDK 1.3.1. Here are the results:

Array size: 1000 Average sorting time: 38 milliseconds Number of tests: 1000 Performance: 38.0 O(N) nanoseconds Performance: 3.813046611743762 O(N*Log2(N)) nanoseconds Performance: 0.038 O(N*N) nanoseconds Array size: 2000 Average sorting time: 153 milliseconds Number of tests: 1000 Performance: 76.5 O(N) nanoseconds Performance: 6.976245201813886 O(N*Log2(N)) nanoseconds Performance: 0.03825 O(N*N) nanoseconds Array size: 3000 Average sorting time: 347 milliseconds Number of tests: 1000 Performance: 115.66666666666667 O(N) nanoseconds Performance: 10.01378255586346 O(N*Log2(N)) nanoseconds Performance: 0.03855555555555556 O(N*N) nanoseconds

The results showed us that the performance of selection method is O(N*N), because the last performance line gave me a constant, when I increased the array size.

Comparing with the Insertion Sort implementation, the Selection Sort implementation is much slower, the execution time is doubled.

*Last update: 2011.*

Table of Contents

Introduction of Sorting Algorithms

Java API for Sorting Algorithms

Insertion Sort Algorithm and Implementation

►Selection Sort Algorithm and Implementation

Selection Sort - Algorithm Introduction

Selection Sort - Java Implementation

Selection Sort - Implementation Improvements

Bubble Sort Algorithm and Implementation

Quicksort Algorithm and Implementation

Merge Sort Algorithm and Implementation

Heap Sort Algorithm and Implementation

Shell Sort Algorithm and Implementation