Page 219 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Step 5:
1 3 4 5 6 10 8 9 7 2 – Step 5, the new element is 1, which is again smaller than 10, then like in the
previous steps, it is compared to the next numbers 6,5,4,3 and is smaller than an of these, so it
ends at the left of the array that has been sorted out so far, with the order being 1 3 4 5 6
Step 6:
1 3 4 5 6 8 10 9 7 2 – At step 6, the element 8 was compared to 10 and moved to the left, but
compared to 6 it is greater, so now the list would look like 1 3 4 5 6 8
Step 7:
1 3 4 5 6 8 9 10 7 2 – Step 7, the element 9 was compared to 10 and moved to the left having it being
smaller, but it is greater than 8 so the list is: 1 3 4 5 6 8 9
Step 8:
1 3 4 5 6 7 8 9 10 2 – Step 8, the element of 7 was compared to 10, so it had to move to the left of
10, also 7 is smaller than 8 which it moves another position to the left, but it is greater than 6, so
it found its position, with the array looking like: 1 3 4 5 6 7 8 9

Step 9:
1 2 3 4 5 6 7 8 9 10 – At the final step 9, the element 2 was compared to 10, being smaller it moves
to the left, then again it is compared to 9, then 8, 7, 6, 5, 4, 3 and is smaller than any of these
numbers, so the right position is to the left, but being greater than 1, it’s at one position to the
right of the element 1, now the final order is the right one : 1 2 3 4 5 6 7 8 9 10

Having no more elements to compare 10 to, the algorithm now knows that the list is sorted.
The following is an implementation in C.
#include < iostream >
using namespace std;
int main(void)
{
int i;
long int A[100];
long int n=100;
cout << “Please insert the number of elements to be sorted:”;
cin >> n; // The total number of elements
for(int i=0;i < n;i++)
{
cout << “Input” << i << “element:”;
cin >> A[i]; // Adding the elements to the array
}
cout << “Unsorted list:” << endl; // Displaying the
unsorted array
for(int i=0;i < n;i++)
{
cout << A[i] << “ ”;
}
for (int k=1;k < n;k++)
{

212 LOVELY PROFESSIONAL UNIVERSITY