Compile-and-Link and Sorting

Good to Know: Compile and Link

When you become a mature programmer working on a huge project:

Consider the following scenario:

Suppose that your team works on a huge project with more than 1000 source code files.
You modified a file.
The project needs to be newly compiled. Since there are more than 1000 files, it will take at least 30 minutes to compile the entire project.
Oops, there is a syntax error in your revised code. You need to go back to step 2.

Compile and Link framework

Obviously, the code modification cycle in this scenario takes TOO LONG! Here's a better way.

You modified a file.
You only need to compile only the file you modified.
Oops, there is a syntax error in your revised code. You need to go back to step 2.
After a successful revision, you link all the compiled files into one executable program.

Example: `vector` program

Consider vector program contains two cpp files and some h files.


// point.h: prototypes and struct definitions
#pragma once
#include <iostream>
using namespace std;

struct point
{
  double x, y;
};
istream& operator >> (istream& is, point& p);
ostream& operator << (ostream& os, point p);
point operator + (point a, point b);
point operator / (point p, double z);


// point.cpp: function definitions
#include <iostream>
using namespace std;
#include "point.h"   // NOTE 2

istream& operator >> (istream& is, point& p)
{
  char c;
  return is >> c >> p.x >> c >> p.y >> c;
}

ostream& operator << (ostream& os, point p)
{
  return os << '(' << p.x << ',' << p.y << ')';
}

point operator + (point a, point b)
{
  point S = {a.x + b.x, a.y + b.y};
  return S;
}

point operator / (point P, double z)
{
  point Q = {P.x / z, P.y / z};
  return Q;
}


// main.cpp
#include <iostream>
using namespace std;
#include "point.h"  

struct Vector
{
  char label;
  point s, t;
};

int main()
{
  // Create a vector V
  Vector V;

  // Read label and vertices
  cout << "Enter label and 2 vertices: ";
  cin >> V.label >> V.s >> V.t; 

  // Write label and vertices
  cout << "Your vector is " << V.label << " "
       << V.s << " " << V.t << endl;

  return 0;
}

Compile all cpp files first.
1. ```
g++ -c point.cpp
```
  The above command will create an object file point.o .
2. ```
g++ -c main.cpp
```
  The above command will create an object file main.o .
Linking two object files as follows:
```
g++ point.o main.o -o vector
```
Then, when the program is linked, these two compiled pieces (i.e., object files) are brought together (along with any standard library code we need) to form a complete program.

Sorting: Practice Problem

In this lecture, we consider sorting numbers in an array.

Write a program that reads in the numbers and output them in increasing order.

$ ./a.out
N = 4: 7 4 1 3
1 3 4 7
$ ./a.out
N = 7: 100 -7 3 9 12 -6 45
-7 -6 3 9 12 45 100

You are given the easy part on the right. Write the function sort()


#include <iostream>
using namespace std;

void sort(int* A, int N);

int main()
{
  char c;
  int N;
  cin >> c >> c >> N >> c;

  int* A = new int[N];
  for(int i=0; i < N; i++)
    cin >> A[i];

  sort(A, N);

  for(int i=0; i < N; i++)
    cout << A[i] << " ";
  cout << endl;

  delete[] A;
  return 0;
}

Tip: selection sort

One natural way of sorting numbers is as follows:

The first iteration (with i==0) puts the smallest number at index 0 in the array
The second iteration (with i==1) puts the next-smallest number at index 1 in the array
The third iteration (with i==2) puts the next-smallest number at index 2 in the array
… and on until the entire thing is sorted!

This sorting algorithm is known as Selection Sort, because it selects the first of the remaining elements and puts it in its proper spot in the sorted array.

I hope the following picture clarifies the idea behind Selection Sort algorithm.

data = 7, 4, 1, 3
iteration 0

sorted up to index 0
iteration 1

sorted up to index 1
iteration 2

sorted up to index 2
(actually, all sorted)

 #        
 #
 #        put 
 # #      the smallest
 # #   #  at index 0
 # #   #   
 # # # #  (swap 2 -> 0)
---------
 0 1 2 3

     #    
     #
     #    put 
   # #    the next smallest
   # # #  at index 1  
   # # #
 # # # # (swap 3 -> 1)
---------
 0 1 2 3

     #    
     #   
     #    put 
     # #  the next smallest
   # # #  at index 2
   # # #
 # # # # (swap 3 -> 2)
---------
 0 1 2 3

       #
       #
       #
     # #
   # # #
   # # #
 # # # #
---------
 0 1 2 3

Solution

ex.cpp