Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Data File StructureRSS Feeds

Defines and provides example of selection sort, bubble sort, merge sort, two way merge sort, quick sort (partition exchange sort) and insertion sort

Posted By: Toby Evans     Category: C++ Programming     Views: 10133

This article defines and provides an example of selection sort, bubble sort, merge sort, two way merge sort, quick sort (partition exchange sort) and insertion sort.

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

  
Share: 



Toby Evans
Toby Evans author of Defines and provides example of selection sort, bubble sort, merge sort, two way merge sort, quick sort (partition exchange sort) and insertion sort is from London, United Kingdom.
 
View All Articles

 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
No Comment Found, Be the First to post comment!