Selection Sort
It is the easiest way to sort a table. The sort is being performed from the first element; a search is performed to locate the element that is smaller than the key element. When this element is found, it is interchanged with the first element in the table. A search for the second smallest key is then carried out. Then it is started from the second element onwards. The element, which has the second smallest key, is interchanged with the element located in second position of table. This process continues till the array is in ascending order.
Pass:
Initially the elements of the array are : 9 8 7 6 5 4 3 2 1 10
| 9 1 1 1 1 1 1 1 1 1 |
| 8 9 2 2 2 2 2 2 2 2 |
| 7 8 9 3 3 3 3 3 3 3 |
| 6 7 8 9 4 4 4 4 4 4 |
| 5 6 7 8 9 5 5 5 5 5 |
| 4 5 6 7 8 9 6 6 6 6 |
| 3 4 5 6 7 8 9 7 7 7 |
| 2 3 4 5 6 7 8 9 8 8 |
| 1 2 3 4 5 6 7 8 9 9 |
V 10 10 10 10 10 10 10 10 10 10 V
Bubble Sort
It is a well-known sorting method. It differs from the selection sort in that, instead of finding the smallest record and then performing an interchange, two records are interchanged immediately upon discovering that they are out of order. In this method, after the first pass, the record with the largest key will be in the nth position. On each successive pass, the records with the next largest key will be placed in position n-1, n-2,…respectively.
Pass:
Initially the elements of the array are : 9 8 7 6 5 4 3 10 2 1
| 9 8 7 6 5 4 3 3 2 1 |
| 8 7 6 5 4 3 4 2 1 2 |
| 7 6 5 4 3 5 2 1 3 3 |
| 6 5 4 3 6 2 1 4 4 4 |
| 5 4 3 7 2 1 5 5 5 5 |
| 4 3 8 2 1 6 6 6 6 6 |
| 3 9 2 1 7 7 7 7 7 7 |
| 10 2 1 8 8 8 8 9 8 8 |
| 2 1 9 9 9 9 9 8 9 9 |
V 1 10 10 10 10 10 10 10 10 10 V
Simple Merge Sort
The merge sort is a sort where the operation of sorting is closely related to the process of merging. Let assume that there are two arrays that can be combined to produce a single sorted array. This process can be accomplished easily by successively selecting the record with the smallest key occurring in either of the tables and placing this record in a new table, thereby creating an ordered list.
Pass:
Initially the elements of the array are :
Table 1:11 23 42
Table 2: 9 25
Table 1:11 23 42
Table 2:25
New Table: 9
Table 1:23 42
Table 2:25
New Table: 9 11
Table 1:42
Table 2:25
New Table: 9 11 23
Table 1:42
Table 2:
New Table: 9 11 23 25
Table 1:
Table 2:
New Table: 9 11 23 25 42
Two Way Merge Sort
The process to merge k sorted tables into a single sorted table is called multiple merging or k-way merging. Multiple merging can also be accomplished by performing a simple merge repeatedly.
Pass:
Initially the elements of the array are : 9 83 43 64 15 28 74 8
---------------------------------------------->
[9 83 43 64] [15 28 74 8]
[9 83] [43 64] [15 28 74 8]
[9] [83] [43 64] [15 28 74 8]
(9 83) [43] [64] [15 28 74 8]
(9 83) (43 64) [15 28 74 8]
(9 43 64 83) [15 28 74 8]
(9 43 64 83) [15 28] [74 8]
(9 43 64 83) [15] [28] [74 8]
(9 43 64 83) (15 28) [74 8]
(9 43 64 83) (15 28) [74] [8]
(9 43 64 83) (15 28) (8 74)
(9 43 64 83) (8 15 28 74)
(8 9 15 28 43 64 74 83)
---------------------------------------------->
Quick Sort (Partition Exchange Sort)
This sorting technique performs very well on larger tables. At each step in the method, the goal is to place a particular record in its final position within a table. This technique essentially partitions the table into two subtables. The same process can then be applied to each of these subtables and repeated until all records are placed in their final positions.
Pass:
Initially the elements of the array are : 42 23 74 11 65 58 94 36 99 87
---------------------------------------------->
42 23 74 11 65 58 94 36 99 87
42 23 74 11 65 58 94 36 99 87
42 23 74 11 65 58 94 36 99 87
42 23 74 11 65 58 94 36 99 87
42 23 74 11 65 58 94 36 99 87
42 23 36 11 65 58 94 74 99 87
42 23 36 11 65 58 94 74 99 87
42 23 36 11 65 58 94 74 99 87
42 23 36 11 65 58 94 74 99 87
42 23 36 11 65 58 94 74 99 87
42 23 36 11 65 58 94 74 99 87
11 23 36 42 65 58 94 74 99 87 i>=j
---------------------------------------------->
Insertion Sort
This sorting technique is very easy. In this, we sort the array taking into consideration the concept of insertion. If the first element is greater than the second, then we interchange them. Then we check the third element if it is smaller than the above elements then it is inserted at appropriate place.
Pass:
Initially the elements of the array are : 9 8 7 6 5 4 3 10 2 1
|9876543211 |
|8987654322 |
|7798765433 |
|6669876544 |
|5555987655 |
|4444498766 |
|3333339877 |
|2222222988 |
|101010101010101099 |
V111111111010 V