Sorting Algorithms

With this definition, we can identify five important characteristics of algorithms"

• Algorithms are well-ordered.
• Algorithms have unambiguous operations.
• Algorithms have effectively computable operations.
• Algorithms produce a result.
• Algorithms halt in a finite amount of time.

The sorting algorithms you will learn in the next few lessons share two basic operations in common. These operations are the comparison operation and the swap operation. We will look at each one in more detail before we examine our sorting algorithms.

The Comparison Operation : The comparison operation is simply a way of determining which item in a list should come first. If we are sorting a list of numbers from smallest to largest, the comparison operation tells us to place the number with the least value first. If we are sorting a list of letters alphabetically, the comparison operation tells us to place 'a' before 'b', 'b' before 'c', and so on. We will see that a sorting algorithm must usually perform many comparisons in order to correctly sort a list.

The Swap Operation: The swap operation is one way we move items as we are sorting. By swapping small items with large ones, we can place all the items in the correct order. When we use computers for sorting, the swap operation can be a little tricky because of the way computers copy data from one memory location to another. Using the animation below, see if you can correctly determine the algorithm for the swap operation.

Simple Sort:

Of course, we all know that the Simple Card Sort algorithm is not very useful to a computer. However, we can use the same idea as in our Simple Card Sort to write a Simple Sort that can be used by a computer. Let's see what this algorithm looks like and how it can be used to sort numbers in a computer.

Simple Sort Algorithm Get a list of unsorted numbers Repeat steps 3 through 6 until the unsorted list is empty    Compare the unsorted numbers    Select the smallest unsorted number    Move this number to the sorted list    Store a maximum value in the place of the smallest number Stop

Notice that most of the steps in our new algorithm are the same as the steps in the Simple Card Sort. The exception is step 6. We need this extra step because we are no longer moving cards from hand to hand but copying numbers in computer memory. For our algorithm to work, we must replace our original number with a special marker so it will not be considered again. The steps below illustrate how the Simple Sort algorithm works on a computer.

1. First, we give the computer a list of unsorted numbers. These numbers are stored in a group of contiguous memory cells called an array. Each memory cell of the array holds a single number.
   
   
2. As the computer sorts these numbers, it will repeatedly compare them to find the smallest number. This is similar to the comparisons we made when sorting our hand of cards. Each time we compared two cards and kept the smaller of the two. Then we compared this card to the remaining cards until we found a smaller one or checked all the cards. The computer uses the same process only with numbers rather than cards.
   
   Once the smallest number is found, the computer will copy this number to a new array of memory cells and replace the old number with a special number called MAX. MAX is the largest number a single memory cell can hold. None of the remaining numbers can be larger than MAX, so this number is a good choice for marking memory cells that have already been sorted.
   
   

   Unsorted Array Sorted Array

3. Next, the computer begins searching for the smallest number in the unsorted list. Although it is easy for us to scan the numbers and select the 2 as smallest, the computer must compare all the memory cells in the unsorted array to be certain which number is smallest. This means the computer must perform six comparisons: (7 < 8), (7 > 5), (5 > 2), (2 < 4), (2 < 6), and finally (2 < 3). Once the comparisons are done, the computer copies 2 to the sorted array and replaces the original 2 with MAX.
   
   

   Unsorted Array Sorted Array

4. Now the computer begins searching for the smallest number again. Six more comparisons are required to determine that 3 is smallest: (7 < 8), (7 > 5), (5 < MAX), (5 > 4), (4 < 6), and finally (4 > 3). Now we can see the importance of replacing 2 with MAX in our previous step. If we had not made this change, then 2 would have been selected as the smallest number again. After copying 3 to the sorted array, the computer also replaces the original with MAX.
   
   

   Unsorted Array Sorted Array

5. With six more comparisons, the computer selects 4 as the smallest number, copies it to the sorted array, and replaces the original with MAX.
   
   

   Unsorted Array Sorted Array

6. The numbers 5, 6, 7, and 8 are also selected in turn by six comparisons, a copy, and a replacement of the original. Once all the memory cells in the unsorted array have been considered, the sorted array contains our original numbers in sorted order.
   
   

   Unsorted Array Sorted Array

Insertion Sort

Now let's look at how the Insertion Sort algorithm would work inside a computer. Below is our modified algorithm for sorting a list of numbers.

Insertion Sort Algorithm Get a list of unsorted numbers Set a marker for the sorted section after the first number in the list Repeat steps 4 through 6 until the unsorted section is empty    Select the first unsorted number    Swap this number to the left until it arrives at the correct sorted position    Advance the marker to the right one position Stop

This time the steps of our modified algorithm are almost identical to the steps in our card sorting algorithm. We have simply substituted numbers for playing cards and a list of numbers for a hand of cards. The steps below illustrate how the Insertion Sort algorithm works on a computer.

1. First, we give the computer a list of unsorted numbers and store them in an array of memory cells.
   
   
2. To begin the sort, the computer divides the sorted and unsorted sections of the list by placing a marker after the first number. To sort the numbers, it will repeatedly compare the first unsorted number with the numbers in the sorted section. If the unsorted number is smaller than its sorted neighbor, the computer will swap them.
   
   
3. The first number in the unsorted section is 8, so the computer compares it with the number to the left. Since 8 is greater than 7, these numbers do not need to swapped and the computer simply advances the marker one position. Notice that only one comparison was needed to sort the 8.
   
   
4. Now the first number in the unsorted section is 5. 5 is less than 8, so the computer swaps these numbers.
   
   
   5 is also less than 7, so the computer swaps these numbers as well.
   
   
   Now 5 is in the correct order, so the computer advances the marker one position. This time two comparisons and two swaps were needed to sort the number.
   
   
5. Now the first number in the unsorted section is 2. 2 is less than 8, 7, and 5, so after three comparisons and three swaps, 2 arrives at the correct sorted position, and the computer advances the sort marker.
   
   
6. Now the first number in the unsorted section is 4. 4 is less than 8, 7, and 5 but it is not less than 2. This time the computer performs four comparisons and three swaps to put the 4 in the correct order. Only three swaps were needed since the 2 and the 4 did not need to be switched. After these comparisons and swaps, the computer advances the sort marker.
   
   
7. Now 6 is the first number in the unsorted section. After three comparisons and two swaps, the computer places the 6 in the correct position between 5 and 7. Notice that the computer did not need to compare the 6 with the 2 or the 4 since it already knows these numbers are less than 5. Once the computer finds a number in the sorted section less than 6, it knows it has found the correct position for 6 and it can advance the sort marker.
   
   
8. The final unsorted number is 3. To find the correct position for 3, the computer must compare it with every number in the unsorted section. However, only five swaps are required since the first number (2) is less than 3. After moving 3 to the correct position and advancing the sort marker, the Insertion Sort is complete since the unsorted section is empty.
   
   

Selection Sort

Now that you have a general idea of how the Selection Sort works, let's see how the computer would perform this sort with numbers. Below is our modified algorithm for sorting a list of numbers.

Selection Sort Algorithm Get a list of unsorted numbers Set a marker for the unsorted section at the front of the list Repeat steps 4 - 6 until one number remains in the unsorted section    Compare all unsorted numbers in order to select the smallest one    Swap this number with the first number in the unsorted section    Advance the marker to the right one position Stop

Again our modified algorithm is almost identical to our card sorting algorithm. We only needed to substitute numbers for playing cards and a list of numbers for a hand of cards. One other slight change is that steps 4 and 5 of the Selection Card Sort have been combined. This is typical since a computer will usually keep track of the smallest number while it compares all the numbers. The steps below illustrate how the Selection Sort algorithm works on a computer.

1. First, we give the computer a list of unsorted numbers and store them in an array of memory cells.
   
   
2. To begin the sort, the computer divides the sorted and unsorted sections of the list by placing a marker before the first number. To sort the numbers, the computer will repeatedly search the unsorted section for the smallest number, swap this number with the first number in the unsorted section, and update the sort marker.
   
   
3. To find the smallest number in the unsorted section, the computer must make six comparisons: (7 < 8), (7 > 5), (5 > 2), (2 < 4), (2 < 6), and (2 > 3). After these comparisons, the computer knows that 2 is the smallest number, so it swaps this number with 7, the first number in the unsorted section, and advances the sort marker.
   
   
4. Now five more comparisons are needed to find the smallest number in the unsorted section: (8 > 5), (5 < 7), (5 > 4), (4 < 6), and (4 > 3). After these comparisons, the computer swaps 3, the smallest number in the unsorted section, with 8, the first number in the unsorted section, and advances the sort marker.
   
   
5. This time four comparisons are needed to determine that 4 is the smallest number in the unsorted section: (5 < 7), (5 > 4), (4 < 6), and (4 < 8). After these comparisons, the computer swaps 4 with 5 and then advances the sort marker.
   
   
6. After three more comparisons, the computer identifies 5 as the smallest unsorted number: (7 > 5), (5 < 6), and (5 < 8). Then the computer swaps 5 with 7 and advances the sort marker.
   
   
7. This time only two comparisons are needed to determine that 6 is the smallest number: (7 > 6) and (6 < 8). After these two comparisons, the computer swaps 6 with 7 and then advances the sort marker.
   
   
8. Now we only need a single comparison to find the right position for 7: (7 < 8). Since 7 is the smallest number and it is also the first number in the unsorted section, the computer does not need to swap this number. It only needs to advance the sort marker. Now there is only one number in the unsorted section, so the list of numbers is sorted and the Selection Sort algorithm is complete.
   
   

Algorithm Analysis:

Types of Efficiency  Measures

Space                     Amount of Computer Memory

Time                       # no of items copied, # no of item swapped, # no of item compared.

Comparision of Sort

Now that you have completed your calculations, let's summarize the results. We already know that the Insertion Sort and the Selection Sort were the most space-efficient, but we have yet to determine which sort is the most time-efficient. We will see that this answer is a little more difficult to determine.

Space Efficiency

Algorithm	# of memory cells
Simple Sort Insertion Sort Selection Sort	14 8 8

Time Efficiency

Algorithm	# of copies	# of comparisons
Simple Sort Insertion Sort Selection Sort	7 45 15	42 19 21

Notice that the Simple Sort required the least amount of copies. We would expect this to be true since it does not swap numbers while sorting. Instead the numbers are copied to a new list in the computer. This is a common tradeoff between time and space. Although the Simple Sort loses space efficiency by using two lists, it gains time efficiency because less copies are required. Of course this does not mean that it is always best to use the Simple Sort to gain more speed. If we are trying to sort a list of 5 million names the Simple Sort would use too much space in the computer's memory. It would be much better to swap items within the list rather than create two lists.
For number of comparisons, the Selection Sort and Insertion Sort were nearly the same. The Simple Sort, however, required twice as many comparisons. We can see the reason for this difference by thinking about how the algorithms work. Each algorithm repeatedly searches for the smallest number and then places this number in the correct position. For the Insertion Sort and the Selection Sort, each iteration of this process reduces the unsorted section by one number. During the next search, the computer does not need to make as many comparisons to find the smallest number. The Simple Sort, however, replaces sorted numbers with a marker called MAX. Each time the computer searches for the smallest number, it must compare all seven memory cells. This approach is much less efficient.
Given the particular set of seven numbers we sorted, the Selection Sort was the most time-efficient. However, it is important to understand that this may not be true for every set of seven numbers. Consider the following example.

If we use the Insertion Sort on these numbers only 8 comparisons and 1 swap would be needed to sort them. However, if we use the Selection Sort, 21 comparisons and 1 swap would be needed. In this case, the Insertion sort is more efficient.

Worst Case Comparison

 Now that we have formulas to describe the worst case time efficiency of our sorting algorithms, we can see how the algorithms will perform as we increase the number of items to be sorted. First, let's review our formulas. Notice that the formulas for swaps have been converted to copies by multiplying by 3. This allows us to correctly compare Simple Sort with the other two sorts.

Algorithm

Comparisons

Copies

Simple Sort	n * (n-1)	n
Insertion Sort	(n-1) + (n-2) + ... + 1	3 * [(n-1) + (n-2) + ... + 1]
Selection Sort	(n-1) + (n-2) + ... + 1	3 * (n-1)

Using our formulas, we will compute the number of comparisons and copies needed to sort several lists of items. The number of items in each list increases by a power of ten.

Comparisons Required

# of Items	Simple Sort	Insertion Sort	Selection Sort
10	90	45	45
100	9,900	4,950	4,950
1,000	999,000	499,500	499,500
10,000	99,990,000	49,995,000	49,995,000

From our table of comparisons, we can see two important facts. First, the Simple Sort always requires twice as many comparisons as the Insertion and Selection Sorts. This means we can rewrite the formula for these sorts as follows: (n * (n-1)) / 2. This expression is much easier to use than the summation (n-1) + (n-2) + ... + 1, especially when n is large.
Second, all three sorts require a tremendous number of comparisons as the number of items increases. In fact, we can see with the Simple Sort that the number of comparisons is very close to n². Take another look at the formula you derived for the number of comparison the Simple Sort requires in the worst case. If we multiply the n into the parentheses, the formula becomes n² - n. Now you see why our total comparisons is very near n². You can also see why the number of comparisons needed is growing so quickly.

Copies Required

# of Items	Simple Sort	Insertion Sort	Selection Sort
10	10	135	27
100	100	14,850	297
1,000	1,000	1,498,500	2,997
10,000	10,000	149,985,000	29,997

Now let's compare the number of copies each algorithm requires. Notice how quickly the number of copies required by the Insertion Sort is growing. This makes us suspect that the formula for the Insertion Sort contains an n² term. In fact, the formula does contain such a term, but we must rewrite the formula to see it. Using the relationship we discovered earlier, we can replace the summation (n-1) + (n-2) + ... + 1 with (n * (n-1)) / 2 and simplify.

# of copies  =  3 * [(n-1) + (n-2) + ... + 1] # of copies  =  3 * [(n * (n-1)) / 2]  # of copies  =  (3 / 2) * [n * (n-1)]  # of copies  =  (3 / 2) * [n2 - n]

The simplified formula shows the n² term that we suspected. Notice that the other two formulas only have an n term rather than a n² term. This is the reason that they grow slowly as the number of items increases.

Order Notation

 In the last lesson, we discovered that we can represent the efficiency of our sorting algorithms with formulas. We derived these formulas by identifying the most important operations in the algorithm (e.g. comparisons, copies, or swaps) and then counting how many of these operations were required to sort a specific number of items. Next, we found a general pattern in the number of operations required at each step and used this pattern to write our formula. One such formula that we derived was the formula to describe the number of comparisons the Simple Sort requires in the worst case. The formula is given below.

# of comparisons  =  n * (n-1) # of comparisons  =  n2 - n

Since the largest term in this formula is n², we discovered that the number of comparisons needed grows very quickly. We also saw a couple other formulas whose largest term was n, and we found these formulas only showed moderate growth. From these examples, we can see that the size of the largest term in an algorithm's efficiency formula has a very great effect on the performance of an algorithm. In fact, algorithms are classified based on the size of this term. This classification is called "order notation" and it is used to compare the amount of work that different algorithms must perform to do the same job. An algorithm which has n² as its highest term would be called an O(n²) algorithm (pronounced "order-n-squared algorithm"). An algorithm with n as its highest term would be called an O(n) algorithm (pronounced "order-n algorithm"). Two other common classes of algorithms are O(2ⁿ) and O(log n). The graph below shows you how the performance of these four classes of algorithms compares.

Although we used sorting algorithms to introduce the idea of efficiency and order notation, these ideas apply to all algorithms. For example, suppose we wrote a search algorithm to find a telephone number in a large list of phone numbers. We could also describe the efficiency of this algorithm using order notation. In this case, n would represent the size of phone directory (i.e. the number of phone numbers). The most important operation in this algorithm would be comparing numbers, so we would be interested in knowing how many comparisons our algorithm would need to find a particular phone number. If our algorithm is efficient, then the largest term in the efficiency formula will be n or log n. If our algorithm is inefficient, then our formula will have a larger term like n² and 2ⁿ.

Summary

 Let's take a quick review of all that we have learned about algorithms.

1. We began by carefully defining what an algorithm is. In our definition, we saw five important characteristics that an algorithm must have:



1. Algorithms are well-ordered.
2. Algorithms have unambiguous operations.
3. Algorithms have effectively computable operations.
4. Algorithms produce a result.
5. Algorithms halt in a finite amount of time.
   
2. We discussed three different ways to represent algorithms: plain English, programming languages, and structured English. We found that plain English was too wordy and ambiguous for specifying algorithms. On the other hand, programming languages require knowledge of many details that are not relevant to algorithms. Our compromise was to use structured English to represent algorithms.
   
3. We learned three different sorting algorithms: the Simple Sort, the Insertion Sort, and the Selection Sort. We found that these algorithms actually provide a solution to a class of problems. They are useful not only for sorting cards, but also for names, numbers, dates, etc.
   
4. We compared the space efficiency and the time efficiency of the three sorting algorithms. Although the Selection Sort was the most efficient sort in our example, we found that these results can change depending on the number of items sorted and the order of the items. To perform a better comparison, we found formulas that describe the performance of our sorting algorithms in the worst case.
   
5. We compared the efficiency formulas of the sorts and introduced the idea of order notation. We discovered that the performance of an algorithm depends heavily upon the size of the largest term in the efficiency formula. In order notation, this term defines what class an algorithm belongs to. Four common classes of algorithms are O(log n), O(n), O(n²), and, O(2ⁿ).

History of the Decimal System

The Enneagram - History of the Decimal System
One of the problems in determining the origins of the enneagram is that the sequence of the pattern of the internal lines is based on the decimal division of 1 by 7 yielding the repeating decimal 0.142857.

Shang Dynasty 1766-1122 BCE: Decimal place system (14th century BCE) - 2300 years later in Western civilization

History of Chinese Invention - The Decimal System of Number Representation: Decimal number system, also called HINDU-ARABIC, or ARABIC, base 10 system, in mathematics, positional numeral system employing 10 as the base and requiring 10 different numerals, the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and a dot (decimal point).

A noteworthy characteristic of the Chinese system, and one that represented a substantial advantage over the Mediterranean systems, was its predilection for a decimal notation, as demonstrated by foot rulers dating back as far as the 6th century BC. An example of how the Chinese used the decimal system may be seen in an inscription from the thirteenth century BC, in which '547 days' is written 'Five hundred plus four decades plus seven of days'. The Chinese wrote with characters instead of an alphabet. When writing with a Western alphabet of more than nine letters, there is a temptation to go on with words like eleven. With Chinese characters, ten is ten-blank and eleven is ten-one (zero was left as a blank space: 405 is 'four blank five'), This was much easier than inventing a new character for each number (imagine having to memorize an enormous number of characters just to read the date!). Having a decimal system from the beginning was a big advantage in making mathematical advances. The first evidence of decimals in Europe is in a Spanish manuscript of 976 AD.

History of the Decimal System
The Arabic numeral system is considered one of the most significant developments in mathematics, and, ergo, several theories have been advanced about its origin. These theories include

• The idea that it originated in China.
• The idea that it was invented by Al-Khwarizmi.
• The idea that it originated in the ancient Middle East and that the Arabic numeral system was simply an westward transmission of the Indian numeral system.

Although these theories contain varying amounts of truth, each is exaggerated in its thesis. Nevertheless, very few historians debate the Arabic numeral system was influenced by Indian mathematics.

Somewhat speculatively, the origin of a base-10 positional number system used in India can be traced to China. Because the Chinese Hua Ma system (see Chinese numerals) is also a positional base-10 system, Hau Ma numerals—or some numeral system similar to it—may have been the inspiration for the base-10 positional numeral system that evolved in India. This hypothesis is made stronger by the fact that years from 400 to 700, during which a positional base-10 system emerged in India, were also the period during which the number of Buddhist pilgrims traveling between China and India peaked. What is certain is that by the time of Bhasakara I (i.e., the seventh century AD) a base 10 numeral system with 9 glyphs was being used in India. This numeral system had reached the Middle East by 670. Significantly, however, this numeral system lacked a zero digit. Muslim mathematicians working in what is now Iraq were familiar with the Babylonian numeral system, which used the zero digit between nonzero digits (although not after nonzero digits). Furthermore, by 874, the latest Muslim mathematicians were using a base 10 positional numeral system, with the zero digit used both between and after nonzero digits. Mathematicians in India took the same step at essentially the same time (by 876 at the latest). The two groups apparently derived analogous numeral systems independently. In the early twelfth century AD, Arab mathematicians in North Africa extended the Arabic numeral system to include decimals.

Fibonacci, an Italian mathematician who had lived in North Africa, introduced the Arabic numeral system to Europe and promoted it with his book Liber Abaci, which was published in 1202. It should be noted that in the Muslim World—until modern times—the Arabic numeral system was used only by mathematicians. Muslim scientists used the Babylonian numeral system, and merchants used a numeral system similar to the Greek numeral system and the Hebrew numeral system. Therefore, it was not until Fibonacci that the Arabic numeral system was used by a large population.

Understanding Signing and Verification

The Java™ platform enables you to digitally sign JAR files. You digitally sign a file for the same reason you might sign a paper document with pen and ink -- to let readers know that you wrote the document, or at least that the document has your approval.
When you sign a letter, for example, everyone who recognizes your signature can confirm that you wrote the letter. Similarly when you digitally sign a file, anyone who "recognizes" your digital signature knows that the file came from you. The process of "recognizing" electronic signatures is called verification.
When the JAR file is signed, you also have the option of time stamping the signature. Similar to putting a date on a paper document, time stamping the signature identifies when the JAR file was signed. The time stamp can be used to verify that the certificate used to sign the JAR file was valid at the time of signing.
The ability to sign and verify files is an important part of the Java platform's security architecture. Security is controlled by the security policy that's in force at runtime. You can configure the policy to grant security privileges to applets and to applications. For example, you could grant permission to an applet to perform normally forbidden operations such as reading and writing local files or running local executable programs. If you have downloaded some code that's signed by a trusted entity, you can use that fact as a criterion in deciding which security permissions to assign to the code.
Once you (or your browser) have verified that an applet is from a trusted source, you can have the platform relax security restrictions to let the applet perform operations that would ordinarily be forbidden. A trusted applet can have freedoms as specified by the policy file in force.
The Java platform enables signing and verification by using special numbers called public and private keys. Public keys and private keys come in pairs, and they play complementary roles.
The private key is the electronic "pen" with which you can sign a file. As its name implies, your private key is known only to you so that no one else can "forge" your signature. A file signed with your private key can be verified only by the corresponding public key.
Public and private keys alone, however, aren't enough to truly verify a signature. Even if you've verified that a signed file contains a matching key pair, you still need some way to confirm that the public key actually comes from the signer that it purports to come from.
One more element, therefore, is required to make signing and verification work. That additional element is the certificate that the signer includes in a signed JAR file. A certificate is a digitally signed statement from a recognized certification authority that indicates who owns a particular public key. Certification authorities are entities (typically firms specializing in digital security) that are trusted throughout the industry to sign and issue certificates for keys and their owners. In the case of signed JAR files, the certificate indicates who owns the public key contained in the JAR file.
When you sign a JAR file your public key is placed inside the archive along with an associated certificate so that it's easily available for use by anyone wanting to verify your signature.
To summarize digital signing:

• The signer signs the JAR file using a private key.
• The corresponding public key is placed in the JAR file, together with its certificate, so that it is available for use by anyone who wants to verify the signature.

Digests and the Signature File

When you sign a JAR file, each file in the archive is given a digest entry in the archive's manifest. Here's an example of what such an entry might look like:

Name: test/classes/ClassOne.class
SHA1-Digest: TD1GZt8G11dXY2p4olSZPc5Rj64=

The digest values are hashes or encoded representations of the contents of the files as they were at the time of signing. A file's digest will change if and only if the file itself changes.
When a JAR file is signed, a signature file is automatically generated and placed in the JAR file's META-INF directory, the same directory that contains the archive's manifest. Signature files have filenames with an .SF extension. Here is an example of the contents of a signature file:

Signature-Version: 1.0
SHA1-Digest-Manifest: h1yS+K9T7DyHtZrtI+LxvgqaMYM=
Created-By: 1.7.0_06 (Oracle Corporation)

Name: test/classes/ClassOne.class
SHA1-Digest: fcav7ShIG6i86xPepmitOVo4vWY=

Name: test/classes/ClassTwo.class
SHA1-Digest: xrQem9snnPhLySDiZyclMlsFdtM=

Name: test/images/ImageOne.gif
SHA1-Digest: kdHbE7kL9ZHLgK7akHttYV4XIa0=

Name: test/images/ImageTwo.gif
SHA1-Digest: mF0D5zpk68R4oaxEqoS9Q7nhm60=

As you can see, the signature file contains digest entries for the archive's files that look similar to the digest-value entries in the manifest. However, while the digest values in the manifest are computed from the files themselves, the digest values in the signature file are computed from the corresponding entries in the manifest. Signature files also contain a digest value for the entire manifest (see the SHA1-Digest-Manifest header in the above example).
When a signed JAR file is being verified, the digests of each of its files are re-computed and compared with the digests recorded in the manifest to ensure that the contents of the JAR file haven't changed since it was signed. As an additional check, digest values for the manifest file itself are re-computed and compared against the values recorded in the signature file.
You can read additional information about signature files on the Manifest Format page of the JDK™ documentation.

The Signature Block File

In addition to the signature file, a signature block file is automatically placed in the META-INF directory when a JAR file is signed. Unlike the manifest file or the signature file, signature block files are not human-readable.
The signature block file contains two elements essential for verification:

• The digital signature for the JAR file that was generated with the signer's private key
• The certificate containing the signer's public key, to be used by anyone wanting to verify the signed JAR file

Signature block filenames typically will have a .DSA extension indicating that they were created by the default Digital Signature Algorithm. Other filename extensions are possible if keys associated with some other standard algorithm are used for signing.

---

Related Documentation

For additional information about keys, certificates, and certification authorities, see

• The JDK Security Tools
• X.509 Certificates

For more information about the Java platform's security architecture, see this related documentation:

• Security Features in Java SE
• Java SE Security
• Security Tools

Setting an Application's Entry Point

If you have an application bundled in a JAR file, you need some way to indicate which class within the JAR file is your application's entry point. You provide this information with the Main-Class header in the manifest, which has the general form:

Main-Class: classname

The value classname is the name of the class that is your application's entry point.
Recall that the entry point is a class having a method with signature public static void main(String[] args).
After you have set the Main-Class header in the manifest, you then run the JAR file using the following form of the java command:

java -jar JAR-name

The main method of the class specified in the Main-Class header is executed.

An Example

We want to execute the main method in the class MyClass in the package MyPackage when we run the JAR file.
We first create a text file named Manifest.txt with the following contents:

Main-Class: MyPackage.MyClass

---

Warning: The text file must end with a new line or carriage return. The last line will not be parsed properly if it does not end with a new line or carriage return.

---

We then create a JAR file named MyJar.jar by entering the following command:

jar cfm MyJar.jar Manifest.txt MyPackage/*.class

This creates the JAR file with a manifest with the following contents:

Manifest-Version: 1.0
Created-By: 1.7.0_06 (Oracle Corporation)
Main-Class: MyPackage.MyClass

When you run the JAR file with the following command, the main method of MyClass executes:

java -jar MyJar.jar

Setting an Entry Point with the JAR Tool

The 'e' flag (for 'entrypoint') creates or overrides the manifest's Main-Class attribute. It can be used while creating or updating a JAR file. Use it to specify the application entry point without editing or creating the manifest file.
For example, this command creates app.jar where the Main-Class attribute value in the manifest is set to MyApp:

jar cfe app.jar MyApp MyApp.class

You can directly invoke this application by running the following command:

java -jar app.jar

If the entrypoint class name is in a package it may use a '.' (dot) character as the delimiter. For example, if Main.class is in a package called foo the entry point can be specified in the following ways:

jar cfe Main.jar foo.Main foo/Main.class