1 Quick sort

It takes time \(O(nlog_2n)\) and space \(log_2n\).

1.1 Key point

Select randomly a number x, say x=s[i]. In the first step, you may set x=s[0];
- Find a position for x, which satisfies that the numbers before x are not greater than x, and the numbers after x are not smaller than x.
- Then split the sequence into two parts from x
- Apply the same way in the two parts again
Iterate above steps until each segment only has one element

1.2 C codes

//run on VS 2010
#include <stdlib.h>
#define N 10
void QSort_int(int *s, int l, int r){
    int i, j, x;
    if (l < r){
        i = l; j = r; x = s[i];
        while (i < j){
            while(i < j && s[j] > x) 
              j--; 
                  if(i < j) 
                    s[i++] = s[j];
            while(i < j && s[i] < x) 
              i++; 
                  if(i < j) 
                    s[j--] = s[i];
                  
                  printf("step=%d, x=%d\n",++step, x); 
                  for (int ii = 0; ii < N; ii++) 
                    printf("%d ",s[ii]);
                  printf("\n");
        }
        s[i] = x;
        
        printf("i=%d, x=%d\n",i,x);
        for (int ii = 0; ii < N; ii++) 
          printf("%d ",s[ii]);
        printf("\n");
        
        QSort_int(s, l, i-1); 
        QSort_int(s, i+1, r);
    }
}

int main(){
    int i,j;
    int b[100], c[100];
    srand(1);
    for (i = 0; i < 100; i++) b[i] = rand() % 100;
    srand(1000);
    for (i = 0; i < 100; i++) c[i] = rand() % 100;
    
    printf("b[i]="); 
    for (i = 0; i < N; i++) 
      printf("%d\t",b[i]);printf("\n");
    
    QSort_int(b,0,N-1);
    
    printf("b[i]="); 
    for (i = 0; i < N; i++) 
      printf("%d\t",b[i]);printf("\n");
    
    fflush(stdin);
    getchar();
    return 0;
}

2 Find an element

It takes time \(log_2n\).

2.1 Key point

Let input value is “x”
Compare x with the middle element of the increasing sequence “a”
- Search by the same way in the first segment if x<=a[middle]
- Search by the same way in the second segment if x>a[middle]
Iterate above steps until
- you find x, output the position
- or the segment only has one element, output -1 which mean x does not locate in this sequence

2.2 C codes

//run on VS 2010
#include <stdlib.h>

int findp(double *a, int n, double val){
    int half, tmp, up, low;
    up = n-1; low = 0;
    while(up-low>1){
        tmp = up-low;
        half=low+tmp/2;
        if(val==a[half]) return half;
        else if(val<a[half]) up = half;
        else low = half;
    }
    if(val==a[low]) tmp=low;
    else if(val==a[up]) tmp=up;
    else tmp = -1;
    return tmp;
}

int main(){
  int i, j;
    double b[100], c[100];
    srand(1);
    for (i = 0; i < 100; i++)   b[i] = (rand() % 100) / 100.0;
    
  printf("b[i]="); 
    for (i = 0; i < 100; i++) 
      printf("%f\t",b[i]);printf("\n");
    int index = findp(b,100,0.24);
    printf("%d\n",index);


    fflush(stdin);
    getchar();
    return 0;
}

3 Recursion of pell’s equation

It’s very convenient to be coded by “while” or “for”
The purpose by using recursion is only for training recursiion
The previous version by using “while” can be found in matrixprodect

3.1 C codes

#include <stdlib.h>
void pf2(int *a1, int *b1, int *Lab, int N){
    int i,La,ta,tb,ta1,tb1;
    if(N<=1) {
        a1[0]=3;b1[0]=2;
        Lab[0]=Lab[1]=1;
    }
    else{
        pf2(a1, b1, Lab, N-1);
        ta=tb=0;La=Lab[0];
        for(i=0;i<La;i++){
            ta1=a1[i]*3+b1[i]*4+ta; 
            tb1=a1[i]*2+b1[i]*3+tb;
            a1[i]=ta1%10;   
            b1[i]=tb1%10;
            ta=ta1/10;  
            tb=tb1/10;  
        }
        Lab[0]=La;
        Lab[1]=La;
        if(ta){
          a1[i]=ta;
          Lab[0]++;
          }
        if(tb){
          b1[i++]=tb;
          Lab[1]++;
          }
    }       
}

int main(int argc,char* arg[]){
    int i;
    
    int a[100], b[100], Lab[2];
    for (i = 0; i < 100; i++) a[i]=b[i]=0;
    pf2(a,b,Lab,50);
    printf("p=");
    for(i=Lab[0]-1;i>=0;i--)
      printf("%d",a[i]);
    printf("   q=");
    for(i=Lab[1]-1;i>=0;i--)
      printf("%d",b[i]);printf("\n");

    getchar();
    return 0;
}

4 Drawbacks of recursion

4.1 It is easy to cause error “Stack overflow”

The reason is that the Stack is so limited. Usually, it is only 2M on your laptop. Ofcause, it depends on your laptop.
Therefore, do not use recursion if you can code subrutines by “while” or “for”. Unless, you can guarantee it is “OK”, which means there is not too much iterations or big storage.

5 Arguments of main

The first argument “argc” is an “int” type, which denotes how many arguments are there in main()
The second argument “arg[]” is an arry with type “char”. “arg[1]” denotes the first input of main(), “arg[2]” denotes the second input of main(), and similarly “arg[i]” denotes the \(i^{th}\) input of main().

5.1 An example, say “add.c” or “add.cpp”

#include <stdlib.h>
int main(int argc,char* arg[]){
    int a = atoi(arg[1]), b = atoi(arg[2]);
    printf("a+b=%d\n",a+b);
    
    return 0;
}

5.2 Build an executable file, say “add.exe”.

5.2.1 On Windows OS

Right click on your project, and choose “properties”
- Like follows
Input initial value, such as 10 and 20 on “Command Arguments” under button “Debugging”
- Lie follows
Debug current project
Going to the folder which is a sub-directory named “Debug” under your current project. You can find an executable file “add.exe”.
- Open “CMD”, and use “cd” enter sub-directory “Debug”
- Type “add 10 32”. You will get “a+b=42” on your command line.
```
add 10 32
```
If you already installed “mingw32” or “mingw64” and setuped suitable library path (A good way is to install “Rtools” which includes “mingw64” in the path "D:Files_64" or "c:rtools43_64-w64-mingw32.static.posix“. You can add this path in”Environment variables“), you can follow the similar way as next subsection”On Unix OS" to build an executable file.
- Open “CMD”, and use “cd” enter sub-directory “Debug”
  - Type “gcc add.c -o add”. If there is an error, try to type “g++ add.c -o add”
```
gcc add.c -o add
```
  - You can find an executable file “add.os” in the sub-directory “Debug”
  - Go back to terminal, type “./add 10 32”. You will get “a+b=42” on your command line.
```
add 10 32
```
- Or open mimic terminal, such as “msys”, and use “cd” enter sub-directory “Debug”
  - Type “gcc add.c -o add”. If there is an error, try to type “g++ add.c -o add”
```
gcc add.c -o add
```
  - You can find an executable file “add.os” in the sub-directory “Debug”
  - Go back to terminal, type “./add 10 32”. You will get “a+b=42” on your command line.
```
./add 10 32
```

5.2.2 On Unix type OS, such as Mac OS/Linux/Ubuntu…

It is much simpler than Windows OS
- Open terminal, and use “cd” enter sub-directory “Debug”
- Type “gcc add.c -o add”. If there is an error, try to type “g++ add.c -o add”
```
gcc add.c -o add
```
- You can find an executable file “add.os” in the sub-directory “Debug”
- Go back to terminal, type “./add 10 32”. You will get “a+b=42” on your command line.
```
./add 10 32
```

6 Learning “Debug” by yourself

6.1 There are three usual methods to “Debug”

Build first,
- See if there is any grammer error
- Click on “build”, choose “Build Solution”
- Or click on “build”, choose “Rebuild Solution” if your codes have no any revision
Set “break point”
- See if there is any unnormal value of any variable
- It may need to set multi-breaks
- Or set breaks in inner iteration
Make full use of “printf()”
- Printf out what you think it’s wrong in high probability
- See if there is any unnormal value by “printf()”

Recursion

Xu Liu

1 Quick sort

1.1 Key point

1.2 C codes

2 Find an element

2.1 Key point

2.2 C codes

3 Recursion of pell’s equation

3.1 C codes

4 Drawbacks of recursion

4.1 It is easy to cause error “Stack overflow”

5 Arguments of main

5.1 An example, say “add.c” or “add.cpp”

5.2 Build an executable file, say “add.exe”.

5.2.1 On Windows OS

5.2.2 On Unix type OS, such as Mac OS/Linux/Ubuntu…

6 Learning “Debug” by yourself

6.1 There are three usual methods to “Debug”