Logout

Home Topic 4 Last


Sorting Algorithms


With sorting algorithms we are able to sort arrays in a certain order, for example an array of ints from least to greatest, or vice versa, or an array of Strings alphabetically, or reverse-alphabetically. Oftentimes, we will want to look at or work with an array orgainzed in such a way.

But arguably, the signle most significant reason that sorting is so important to programming is that only with a sorted data structure can the binary search work. And the binary search is by far the most efficient searching algorithm we have at our disposal.

Since computers work with such vast quantities of data, that data is only useful if it can be quickly found. So searching is very, very important, meaning that sorting so that we can use the binary search is also very, very important.


"Algorithm
s"

An algorithm is a step-by-step solution to a problem. So Java algorithms are sequences of Java statements which solve a certain problem, or get some certain job done. (Though you can also think of an algorithm as being something non-programming language specific.)

So the binary search algorithm, for example, is an algorithm in which we look at the middle element of a sorted list, and if the element you are looking for is not there, then ask if it is greater or lesser than the element you are looking for, and then ignore looking through the half which it therefore cannot be. And following on this page are several various sorting algorithms; sequences of step-by-step instructions which will lead to sorted structures.

The following algorithms are variations from the sorts found at www.ensta.fr/~diam. and has a "very permissive" copyright via MIT.


Four Increasingly Efficient BubbleSorts

1. "Dumbest" BubbleSort: - it sorts properly, but not efficiently

public void dumbBubbleSort(int[] intArray) {
     for (int pass = 0; pass < intArray.length - 1; pass++) {  
	   //The outer loop will achieve the bubbling up of the highest number each pass
       //It's length - 1, since the # of comparisons is one less than the length
           for (int i = 0; i < intArray.length -1; i++) {
               if (intArray[i] > intArray[i+1]) {  //The "neighbor comparison"
                    //Swap
                    int temp = intArray[i];        //To understand the need for temp, imagine    
intArray[i] = intArray[i+1]; //trying to swap two glasses of
intArray[i+1] = temp; //juice...you will need a third glass.
} } } }

Detailed Explanation of the (Dubmest) Bubblesort

The bubble sort is a loop within a loop.

The outer loop will achieve the “bubbling up” of the largest value in the array, one largest remaining value at a time. So each “pass”, the next largest value needing to be bubbled up ends up in the right place.

Each outer pass is itself a loop. That internal loop achieves the bubbling up by repetitively making comparisons of neighboring elements, one pair at a time. Each time the one of the pair on the left is greater than the one to its right, they get swapped. (The swapping is achieved via use of a “temp” variable, but one way or the other, the elements get swapped, so that the larger is on the right.)

So for integers or other number types, the order that ends up being achieved is numeric, from smallest to largest. But other types which are “comparable” can also be sorted this way. For example, Strings will end up from “least” to “greatest”, which is really just alphabetic, A to Z.

Note that we can compare Strings using the compareTo( ) method, with a line such as:

if(arr[i].compareTo(arr[i + 1] > 0))     //which means if arr[i] is greater than arr[i - 1]

You are not responsible for this on the test (2021), but it's good to recognize that it works, and how it works.


2. Smarter BubbleSort, smarter because there's one less comparison each pass

This bubble sort compares one less pair ever pass, which makes sense, since each time one more largest bubbles up to the end. But it continues to do passes even if it becomes sorted before the last pass.

public void smarterBubbleSort1(int[] intArray) {
     for (int pass = 0; pass < intArray.length - 1; pass++) {
     //The outer loop will achieve the bubbling up of the highest number each pass
          for (int i = 0; i < intArray.length - 1 - pass; i++) {
          //The inner loop of "neighbor comparisons" get shorter by one each time 
          //(because of intArray.length - 1 - pass)
               if (intArray[i] > intArray[i+1]) { //The "neighbor comparison"
                    //Swap
                    int temp = intArray[i];  
intArray[i] = intArray[i+1];
intArray[i+1] = temp;
} } } }

 

3. Even Smarter BubbleSort, smarter because it ends as soon as it's sorted

This bubble sort is more efficient because if it goes through comparing all pairs and no swapping is necessary, that means that it all must be correctly sorted, and it will stop.

public void smarterBubbleSort2(int[] intArray) {
boolean sorted = false;
while (!sorted) {
sorted = true;
//this is just an assumption, which every time except the last, will //actually not be the case so the last time through the while loop, //when we don't get into the swap at least once, the while will no longer run
for (int i = 0; i< intArray.length-1; i++) { //(So this bubble sort inefficiently checks all neighbors each pass)
if (intArray[i] > intArray[i+1]) {
//Swap
int temp = intArray[i]; intArray[i] = intArray[i+1]; intArray[i+1] = temp;
sorted = false;
//sorted goes back to false so we still have to continue sorting
}
}
}
}

 

4. Smartest BubbleSort, because both one comparison less each pass, and ends when sorted

The following bubble sort combines both of the good features of the other two. It will only continue to go through the outer loop when there is still more sorting to do (accomplished by the while !sorted) And it compares one less pair each pass, in this case accomplished by the n variable that goes one down each pass.

public void smartestBubbleSort(int[] intArray) {
     int n = intArray.length;
     boolean sorted = false;
     while (!sorted) {
          n--; //It is the n which will result in one less comparison happening each outer pass;
               //whereas, with the first bubble sort we could use the 'pass' variable used for the for loop.
          sorted = true;  
          for (int i=0; i < n; i++) {
               if (intArray[i] > intArray[i+1]) {
                    int temp = intArray[i];  
                    intArray[i] = intArray[i+1];  
                    intArray[i+1] = temp;
                    sorted = false; //as in the second bubble sort, if swapping happens we'll want to continue, and so
                                    //with sorted re-set to false again, the while loop continues
               }
          }
     }
  }

Detailed, Explanation of the Smartest BubbleSort

The smartest bubblesort takes in an array, and sorts it. It uses progressive passes through the array in which comparisons of neighboring elements are done, and swaps made where necessary.

A while loop continues the passes of comparisons & swaps down through the array as long as a boolean called sorted remains false. With each pass down through the array, an inner loop repeats the comparison of neigbouring elements, and whenever the first of any pair is greater than the second of the pair, the two are swapped. Over the course of a pass through the array, this will result in the largest as yet un-placed element to be "bubbled up" to its proper position.

One less comparison is made each pass, since one by one the next largest elements get put into place; the one less comparison each time is accomplished by decrementing the loop control variable each pass (n--). Every time through the while loop, its loop control variable, a boolean called "sorted", is set to true, but changes to false when even one swap is made. The one time a pass through the array is completed and no swaps are made, that "sorted" variable remains true, thus making the condition for continuing the outer while loop to be false.

 


The Selection Sort

The first thing to notice with most selection sorts is that they typically work with finding the smallest value each outer pass, rather than the largest element, but this is not so significant a difference from the bubble sort.

This version of the selection sort has one particular efficiency gain over the bubblesort, because it only swaps values once every outer pass. Rather than putting each successive element into its proper place through a series of swaps each pass, it instead just keeps track of which is the smallest, and then swaps only once at the end of the full pass. (Keeping track of one variable's changing value is less processor intensive than use of a bunch of three-step swaps each outer pass.)

public void selectionSort2(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
int minIndex = i; // Assumed index of smallest remaining value.
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[minIndex] ) {
minIndex = j; // Remember index of new minimum
}
}
if (minIndex != i) {
//Exchange current element with smallest remaining. //But note that this only happens once each outer loop iteration, at the end of the inner loop's looping
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}

(Detailed, precise) Explanation of the Selection Sort

An outer for loop repeats passes down through the array. When each pass begins, it assumes the element where it starts contains the smallest element. One element at a time down through the array, we check to see whether that element is actually smaller than the one assumed to be. And every time that this is found to be the case, that newest smallest element is assigned to be the smallest - though, importantly, note that what we keep track of is the index of the element that is the smallest (with a variable "minIndex"), not the value.

Upon reaching the end of each pass, we see if the smallest is actually the one we started with, or if that changed. If it changed, that means that the element we started with is not in fact in the correct position, rather, what we found to be smallest of the remaining should be there, so we swap the initial element with that one (now pointed to by the variable minIndex). Each outer loop pass starts at one element beyond the last time, since the smallest of the remaining elements is put in the proper place each pass.

 

 

Comparing Strings

The comparison of ints and other number data types is straight-forward and can be done with simple greater than and less than operators (> <). But to compare Strings, you will need to use another of the String class' methods. We have already used equals. Now we will need to employ compareTo and compareToIgnorCase.

compareTo and compareToIgnore case are called by a String, and take in another String as a parameter. They return a number which will usually be the difference between the two Strings' ASCII values of their first characters. Though, if the first letters are the same, the calculation is done on the second letters and so on. In this way, if the first String is alphabetically smaller than the second String, a negative number is returned, and if the first String is alphabetically larger than the second String, a positive number is returned.

***If you are unsure of how characters are represented by numbers in the ASCII code set, see the "appendix" at the bottom of this page.

String s = "Chemistry";
String s1 = "Architect";
System.out.println(s.compareTo(s1));

Output: 2
(Since the ASCII value for 'C' is 67, and the ASCII value for 'A' is 65, and 67 - 65 = 2.)

String s = "Architect"; 
String s1 = "Chemistry";
System.out.println(s.compareTo(s1));

Output: -2
(Which is 65 - 67)

String s = "Chemistry";
String s1 = "Churchill";
System.out.println(s.compareTo(s1));

Output: -16
(Since the ASCII value for 'e' is 101, and the ASCII value for 'u' is 117, and 101 - 117 = -16. The 'C' and the 'h' are ignored since they are the same in both words.)

 

So in a sort or a search which is comparing Strings, we employ this fact. We know that if the returned value from compareTo is negative, the first String is "less than" the second. And vice versa, if the returned value is positive, the first string is "greater than" the second.

So if we wanted to achieve

if(StringA > StringB)

We would write:

if(StringA.compareTo(StringB) > 1)

 

And as you would expect, the difference between compareTo and compareToIgnoreCase is that upper and lower case don't matter in the comparison. So "aardvark".compareToIgnoreCase("Banana") yeilds -1 just like "Aardvark".compareToIgnoreCase("banana") does, regardless of the small a and capital B or capital A and small b.

 

***ASCII appendix

ASCII stands for the American Standard Code for Information Interchange. It is the basis for the code set that virtually all computers in the world use to represent basic English letters and symbols, along with the digits 0 - 9. The basic ASCII set represents 128 characters, and is uniform throughout the world. The extended ASCII set of 128 additional characters is non-standard, and there exist many versions for various languages. The idea is that each character in the ASCII set is represented by an agreed upon combinations of binary 0s and 1s. So capital A is 0100 0001, capital B is 0100 0010, and so on. These binary "bits" represent one of two states, most often, in a computers, an electrical switch on (1) or an electrical switch off (0). When the binary number is converted to decimal, you get the standard decimal equivalent of the characters. For example, capital A (binary 0100 0001) in decimal is 65, and capital B (binary 0100 0010) is 66, and so on.

Here is a link to an ASCII talbe showing the first, standard, 128 characters, along with their binary value and decimal equivalent.