APCS Ch 6: Sorting and Searching Methods

Sorting methods as it pertains to arrays isn’t the simplest thing to wrap your head around but the concept and the way they should work should be pretty intuitive. You would need to know about two main sorting methods in APCS; the selection sort and the insertion sort. Like the different types of loops, both of these sorting methods have pros and cons attached to them.

Selection Sort

A selection sort is a tedious affair. Basically, what it does is takes each value in each index position and compares that value to all the other values to the right of it (after it) in the array. When it finds the smallest/largest value that exists to the right of its index position, it swaps places with it. In this way, this method sorts all of its value in either ascending or descending order of value.

Let’s take a look at what a selection sort in ascending order looks like in code:

//nums is an array of int values

//the variables min and minIndex both hold int values

for (int i = 0; i < nums.length – 1; i++)

{

min = nums[i];

minIndex = i;

for (int j = i; j < nums.length; j++)

{

if (nums[j] < min)

{

min = nums[j];

minIndex = j;

}

}

int temp = nums[i];

nums[i] = nums[minIndex];

nums[minIndex] = temp;

}

This is a daunting bit of code at first. However, if we understand mechanically how this sorting method works, it might help you understand better. For example, if I had an array of int values, this is what the array would look like after every pass of the outer loop:

(1) The outer loop started at index position 0, took the number 16 at index 0 and started to loop through the values after it to find the smallest number, which happened to be the number 1 at index position 5. Then, the numbers 1 and 16 swapped places due to the inner loop. That was the first pass of the outer loop.

(2) Then, the outer loop looked at index position 1 and picked up the number 3 at index 1 and looped through the values to the right to find the smallest number. Since there were no values to the right that was smaller than 3, the inner loop swapped the 3 at index 1 with 3 at index 1, which meant the 3 swapped with itself and stayed where it is.

This process would repeat until it got to the second to last number by which time, the last number in the array would already be in its final sorted position so the number of passes the outer loop needs to fully sort an array is always the length of the array minus 1. By this rule, if we were on the fourth pass of the outer loop, the first four values of the array would have been in their final sorted places.

Let’s break down the code and see what the first pass of the outer loop looks like:

for (int i = 0; i < nums.length – 1; i++)

The outer loop just goes through the whole length of the array. In the first pass, i would be set to 0.

min = nums[i];

minIndex = i;

This sets min to the number currently at the index position of whatever element the outer loop is currently looking at. So, min would be set to the number at index 0 on the first pass, which would be the number 16. The index of the smallest number would be default set to the index of the number that we’re currently looking at, which would be index 0.

for (int j = i; j < nums.length; j++)

This inner loop would loop through all the index positions to the right of the number at the index position we’re currently looking at, which would be all the values stored in the index positions after index 0.

if (nums[j] < min){

min = nums[j];

minIndex = j; }

This if statement compares the current min value (16) to all the values right of its index position (0). If it finds a number that is smaller, it will set the smaller value to min and set its index position to minIndex. The inner loop would cause this if statement to compare whatever smallest number it has found so far to the numbers in the index positions to the right. When it came to the number 1 at index 5, it set min to 1 and minIndex to 5. After going through the rest of the array, it didn’t find any smaller value so those variables stayed the same and we exit out of the inner loop.

int temp = nums[i];

nums[i] = nums[minIndex];

nums[minIndex] = temp;

This piece of code should look familiar; after all, it should be a simple puzzle that confronts many beginner programmers. Basically, what this does is it swaps the two numbers at the two index positions. In this case, temp would be set to 16, then the index position 1 would be overridden with the value at minIndex(5) which is 1. Then, temp (16) would override what was at index 5, effectively swapping the 16 and 1. This repeats until it has touched all but the last index position in the array, at which point the array is fully sorted and the outer loop terminates.

See next page for Insertion Sort

APCS Ch 6: Arrays Basics

Arrays are basically lists of things. This list can contain both objects and primitive data. The basic array can be declared and instantiated as such:

(data type)[ ] (arrayname) = new (data type) [(number of elements)];

Since arrays are considered as objects, the declaration and instantiation follow the pattern of other objects. So, if I wanted the array to store a total of ten names, I would make the array like so:

String[ ] names = new String[10];

Arrays have index values for every element they contain. If I had an array called nums that contained the numbers 1, 2, and 3, the number 1 would have the index position of 0, the number 2 would have index position 1 and the number 3 would have the index position 2 and so on.

Like Strings, arrays have a method that returns the length of the object. In the case of arrays, you would call the method .length. The  .length method for arrays does not need the double parentheses.

So, if you wanted to know the length (or number of elements) of the array names, you would do this:

names.length;

We now go on to loops. This is quite simple. Looping through an array is pretty easy and intuitive. If I were to use a for loop to go through every element of the array names which contains 10 String objects, it would look something like this:

for (int i = 0; i < names.length; i++)

{

//body of the loop

}

The Real Reason Why The Da Vinci Code is a Universal Bestseller

Hey all! Since I haven’t been able to post anything these past couple of weeks, I just thought that I should at least give y’all a bit of content seeing as I’m on break so I don’t have the excuse of not having enough time to write. Well, this isn’t content written specifically for Outlet but it is an essay we had to do for an English Literature class. However, since it fits the theme of Outlet and it’s recently written, I thought I should post it here albeit in a slightly altered form. If you guys have read some of my other articles, you can see some recurring ideas and points that I will make again in this essay so yes, I am aware that I reuse examples sometimes, especially when it comes to Dan Brown (if you can’t tell by the title) and the Spanish-American War. Lemme know what you think and if you agree or disagree and let’s jump right into it.

When it comes to controversial pieces of literature, the authors behind those pieces are often accused of ulterior motives. In the case of Dan Brown’s The Da Vinci Code, he was blasted for discrediting the biggest religion in the world while pushing his “feminist” agenda, all using information taken from a questionable source that had been debunked to high heaven. Yet, despite the expert opinions of specialists in both literature and history against him, The Da Vinci Code remains a book eagerly received by the American public. Some critics say Dan Brown took advantage of the social and political turmoil after 9/11 and sold his books when the American public needed for everything to make sense. As one critic puts it, “When bad things happen, Brown reassures us, it is probably because of the machinations of a 1,000-year-old secret society which is quietly running the world, though often in conflict with another hidden organisation.”[1] However, what I want to argue against isn’t about Brown’s lack of literary common sense but how he has managed to seduce the American public into pushing the book to become the second-most popular in modern literature by taking advantage of human nature.