Coursera Algorithms: Design and Analysis, Part 1 (Stanford)

Programming_Question_1.cpp

/***
Algorithms: Design and Analysis, Part 1
Week 1
Jan 2015
***/

#include <bits/stdc++.h>
using namespace std;

// [s,e) consider boundary!! make range uniform
long long countMergeInv(int A[], int s, int e){		
	long long cnt = 0;								//result: return value
	int mid = ( e - s ) / 2 + s;
	int size = ( e - s ) + 1;
	
	vector<int> res(size,-1);
	int i = s;
	int j = mid;

	for(int k = 0; k < size; k++){
		if ( i < mid && ( j >= e ||  A[i] < A[j] ) ){
			res[ k ] = A[i++];
		}
		else{
			cnt += mid - i;
			res[ k ] = A[j++];
		}
	}

	//copy to A[]
	for(int k = 0; k < size; k++){
		A[ k + s ] = res[ k ];
	}

	return cnt;
}

long long count(int A[], int s, int e){
	if ( e - s < 2 ){
		return 0;
	}
	else {
		int mid = ( e - s ) / 2 + s;
		long long x, y, z;
		x = count(A, s, mid );			//split first part
		y = count(A, mid , e);			//split second part
		z = countMergeInv(A, s, e);		//Merge and count Inversion
		return x + y + z;
	}
}

int main(){
	int A[200000];
	int i = 0;
	while ( scanf("%d", &A[i]) != EOF ) {
		i++;
	}
	int cnt = i;
	long long res;
	res = count(A, 0, cnt);
	printf("%lld\n", res);

	int test1[] = {1,3,5,2,4,6}; 		//test #1: 3
	int test2[] = {8,7,6,5,4,3,2,1};	//test #2: 28
	return 0;
}

Programming_Question_2.cpp

/***
Algorithms: Design and Analysis, Part 1
Week 2
Feb 2015
***/ 

#include <bits/stdc++.h>
using namespace std;

void Swap(int i, int j, int A[]){
    int t;
    t = A[i];
    A[i] = A[j];
    A[j] = t;
}

int quickSortFirst(int s, int e, int A[]){
    if ( s >= e ){
        return 0;
    } else {
        int p = A[s];
        int size = ( e - s ) + 1;

        int storeIndex = s + 1;
        for (int k = s + 1; k <= e ; k++){
            if ( A[k] < p ) {
                Swap(storeIndex, k, A);
                storeIndex++;
            }
        }

        storeIndex--;
        Swap(s, storeIndex, A);
        return size - 1
         + quickSortFirst(s, storeIndex - 1, A)
         + quickSortFirst(storeIndex + 1, e, A);
    }
}

int quickSortLast(int s, int e, int A[]){
    if ( s >= e ){
        return 0;
    } else {
        int p = A[e];
        Swap(s, e, A);
        int size = ( e - s ) + 1;

        int storeIndex = s + 1;
        for (int k = s + 1; k <= e ; k++){
            if ( A[k] < p ) {
                Swap(storeIndex, k, A);
                storeIndex++;
            }
        }

        storeIndex--;
        Swap(s, storeIndex, A);
        return size - 1
         + quickSortLast(s, storeIndex - 1, A)
         + quickSortLast(storeIndex + 1, e, A);
    }
}

bool isMedian(int A[], int i, int j, int k){
    return (A[i] < A[j] && A[i] > A[k]) ||
        (A[i] > A[j] && A[i] < A[k]);
}

int quickSortMedian(int s, int e, int A[]){
    if ( s >= e ){
        return 0;
    } else {
        int m = ( e - s ) / 2 + s;
        //wrong
        //int m = (e - s) >> 1 + s; '+' is higher than '>>'
        //should be (( e - s) >> 1 ) + s; 
        int p;
        if (isMedian(A, s, m, e) ){
            p = A[s];
        } else {
            if (isMedian(A, m, s, e)){
                p = A[m];
                Swap(s, m, A);
            } else {
                p = A[e];
                Swap(s, e, A);
            }
        }

        int size = ( e - s ) + 1;

        int storeIndex = s + 1;
        for (int k = s + 1; k <= e ; k++){
            if ( A[k] < p ) {
                Swap(storeIndex, k, A);
                storeIndex++;
            }
        }

        storeIndex--;
        Swap(s, storeIndex, A);
        return size - 1
         + quickSortMedian(s, storeIndex - 1, A)
         + quickSortMedian(storeIndex + 1, e, A);
    }
}


int main(){
    int A[200000];
    int B[200000];
    int C[200000];
    int i = 0;
    while( scanf("%d", &A[i]) != EOF ){
        B[i] = A[i];
        C[i] = A[i];
        i++;
    }
    
    printf("%d\n", quickSortFirst(0, i-1, A));
    printf("%d\n", quickSortLast(0, i-1, B));
    printf("%d\n", quickSortMedian(0, i-1, C));

    //  int test1[] = {10,9,1,3,5,2,4,6,8,7};   //cnt = 30
    //  printf("\ncnt: %d\n", quick1(0,9,test1)); 
    //  for(int i = 0; i < 10; i++){
    //      printf("%d ", test1[i]);
    //  }
    

    // int test2[] = {1,3,5,2,4,6,7,8}; //cnt = 21
    // printf("\ncnt: %d\n",    quick1(0,7,test2));
    // for(int i = 0; i < 8; i++){
    //  printf("%d ", test2[i]);
    // }
    return 0;
}