Sorting Algorithms

Sort a generated array of numbers by specifing the size of the array. The program will generate the array and sort it, then calculate how long each algorithm takes to sort. Type in 0 to automatically sort arrays starting from 2 to 524288 by doubling after each iteration.

Installation

Note: make sure you have Java installed before proceeding in the installation.

git clone https://www.github.com/Electr0d/SortingAlgorithms
javac -d bin src/*.java
cd bin
java main

Algorithms

Selection Sort

Explanation

Selection sort is made of searching and sorting. In each pass, the unsorted value with the smallest/largest value is moved to its proper position in the array.

Example

Code

public int[] selection (int [] numbers) {
  int first, temp;
  for (int i = 0; i < numbers.length; i++) {
    first = 0;   //initialize to subscript of first element
    // locate smallest element between positions 1 and i.
    for(int j = 1; j <= i; j ++) {
      // switch to "<" for descending order   
      if(numbers[j] > numbers[first]) first = j;
    }
    temp = numbers[first]; //swap smallest found with element in position i.
    numbers[first] = numbers[i];
    numbers[i] = temp;
  }
  return numbers;
}

Insertion Sort

Explanation

Unlike other sorting algorithms, insertion Sort passes through the array once. Insertion sort splits up the array into 2.The 1st sub-array is sorted and the other sub-array contains the unsorted numbers. The 1st sub-array is gradually filled up as the algorithm goes through the 2nd sub-array.

Code

public void insertion(int [] numbers) {
  int j, i;
  int key;
  // Start with 1 (not 0)
  for (j = 1; j < numbers.length; j++) {
      key = numbers[j];
      for(i = j - 1; (i >= 0) && (numbers[i] < key); i--) {
      // Smaller values are moving up
        numbers[i + 1] = numbers[i];
    }
    numbers[i + 1] = key;    // Put the key in its proper location
  }
}

Bubble Sort

Explanation

Bubble sort swaps two integers that are out of order, so if a big number is in the first number, it gradually moves up the array in each loop. Hence why it’s called “Bubble Sort”.

Example

Code

public void bubble(int[] numbers) {
  int i, temp;
  boolean flag = true;   // set flag to true to begin first pass
  while (flag) {
    flag = false;    //set flag to false awaiting a possible swap
    for(i = 0; i < numbers.length -1; i++)
    {
      // change to > for ascending sort
      if(numbers[i] > numbers[i + 1]) {
        temp = numbers[i];                //swap elements
        numbers[i] = numbers[i + 1];
        numbers[i + 1] = temp;
        flag = true;              //shows a swap occurred 
      }
    }
  }
}

Exchange Sort

Explanation

The exchange sort is similar to Bubble sort. The difference is in the way they compare the elements.
Exchange sort compares the first element with all the following elements, making any necessary swaps.

Example

Code

public void exchange (int[] numbers) {
  int temp;  //be sure that the temp variable is the same "type" as the array
  for (int i = 0; i < numbers.length - 1; i++)  {
    for (int j = i + 1; j < numbers.length; j++) {
      if(numbers[i] > numbers[j])         //sorting into descending order
      {
        temp = numbers[i];   //swapping
        numbers[i] = numbers[j];
        numbers[j] = temp; 
      }           
    }
  }
}

Observations

Specs

All the algorithms are tested on a PC with the following specifications:

• Processor: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz, 2901 Mhz, 2 Core(s), 4 Logical Processor(s)
• RAM: 16 GB
• OS: Windows 10 Pro
  • Version: 20H2
  • Build: 19042.685
• IDE: Eclipse

Sorting Integers with Minimal Background Processes

" class="reference-link">

Sorting Doubles with Minimal Background Processes

" class="reference-link">

Sorting Integers while CPU Under Load

Sorting Doubles while CPU Under Load

Integer Sorting Time w/ CPU Load – Integer Sorting Time

Double Sorting Time w/ CPU Load – Double Sorting Time

Double - Integer Sorting Time Difference

Double - Integer w/ CPU Load Sorting Time Difference

Sorting Arrays in 5 Minutes

FAQ

1. Which sort seems to be the best “overall” for most purposes? Explain.

The overall best sorting algorithm is “Insertion Sort”. The reason why, is because unlike other sorting algorithms. Insertion Sort passes through the array once.
Insertion sort splits up the array into 2.The 1st sub-array is sorted and the other sub-array contains the unsorted numbers. The 1st sub-array is gradually filled up as the algorithm goes through the 2nd sub-array.

1. Which sort appears to be the least efficient? Explain. Why do you think this sort is taught?

Bubble Sort seems to be the least efficient sorting algorithm. This algorithm is taught because of its simple nature, unlike more complex sorting algorithms such as, insertion sort. Bubble sort swaps two integers that are out of order, so if a big number is in the first number, it gradually moves up the array in each loop. Unlike Insertion sort where it is put in its definitive position. The diagram below explains how Insertion sort works in comparison to Bubble sort.

As shown above. High numbers move to the end of the array just like how bubbles move up, hence why it is called “Bubble Sort”.

1. Under some circumstances, insertion sort can be the most efficient (in time). What would be one of the circumstances? Explain.

When sorting large amounts of doubles. The reason why is because insertion sort puts the number in its definitive position unlike bubble sort where it gradually goes in the proper order.

The table below shows how Insertion sort performs against other sorting algorithms when sorting Doubles with minimal background processes.

1. List all the factors you can think of that might affect the time required to sort a file.

The factors that might affect the time required to sort a file/array are:

• CPU Power
  • Cores
  • Threads
  • Cache size
  • Clock Speed
• RAM speed
• File/array size
• Background and foreground processes
• Programming language
• Algorithm efficiency
• Data type (integer or double)
• PC cooling (throttling while sorting can increase sorting times).
• Power saving settings on laptops might lock the CPU under a certain clock speed, effecting sorting times

1. Suppose you have two data files with the same kind of data but one file is exactly twice as large as the second (twice as much data). Initially, how do you think the sort times should compare between these files?

Sorting times differ between each algorithm. Although, generally speaking sorting times grow exponentially as the file size doubles.

1. Test #5 above: Double the size of the array and repeat the test. How did the sort times change? Explain. Can you explain this “discrepancy”?

Sorting times grew exponentially as predicted. The reason why the sorting times double as the file size double is because sorting algorithms have to do more operations to move a number to its proper position, then more numbers around it to their proper position. Doubling the array size means more numbers around it need to gradually move into their position which takes a toll on sorting time and does not necessarily mean doubling the sorting time or passes.

1. Run many YouTube (or other) videos in the background. Load a few other apps. Play some music (with the volume off or with headphones), run some other programs or do some video / picture editing. Try to make the CPU work to slow down your computer. Run your sorting algorithms again and see what effect the background applications had on the sort time. Record the time difference (the increase in amount of times the sorts took).

1. Change the data type of the numbers from integer to double. How much did this affect the sort times?

Sorting times increased when sorting doubles. The trend can be visualized below:





As shown above double sorting time is sometimes shorter and sometimes longer than double sorting time. Generally speaking, sorting times are longer, though. The likely cause is that Integers are easier to compare due to the lack of decimal points.