정신차료~

https://www.youtube.com/watch?v=H4s55GgAg0I 

C++ Linking

liking: source(C++) file to~ actual executable binary

compilation = compile + link

find where each symbol is & link them together
files are actually seperated, so we need to link them together in one program -> purpose of linker
분리되어있지 않은 한 파일의 코드일지라도 main() 을 찾아서 시작해야 하므로 사실상 main 과 다른 function들을 링크해야 함

LNK error = linking error

static function() >> this function is only declared for this unit

if cannot find the exact one >> linking error!

#include <iostream>
using namespace std;

int main()
{
    int arr[8] = { 83, 72, 65, 54, 47, 33, 29, 1 };

    int i = 1;
    int j, k;

    do {
        int front = arr[i];
        j = i - 1;

        do {
            int back = arr[j];
            k = j + 1;

            if (front < back)
            {
                int tmp = arr[k];
                arr[k] = arr[j];
                arr[j] = tmp;
            }
            else if (front >= back)
            {
                j = -1;
            }

            j--;

        } while (j >= 0);
        i++;
        for (int l = 0; l < 8; l++) { cout << arr[l] << ' '; }
        cout << endl;
    } while (i < 8);
}

Lisp에서의  Insertion Sort

(setq lista(list 83 72 65 54 47 33 29 1))
(setq listb(list 11 33 23 45 13 25 8 135))


(defun insSort (list)
    (print list)		;정렬하려는 리스트 원본 보여줌
    (print '정렬시작----------------)
	(setq a (length list))		;a=length(list)

	(setq i 1)		;i=1... 

	(loop while (< i a)
	do(
		progn
			(setf front (nth i list))		;front= list의 i 번째 요소
			(setq j (- i 1))		;j= i-1

			(loop while (>= j 0)
				do(progn
					(setq k (+ j 1))
					(setq back (nth j list))		;back= list의 j 번째 요소
					(cond
						((>= front back)	
							(setq j -1)		;while문 탈출
						)	
							
						((< front back)
							(progn
								(setf tmp (nth k list))		;tmp= list[k]
								(setf (nth k list) (nth j list))	;list[k]= list[j]
								(setf (nth j list) tmp)		;list[j]= tmp
							)
						)
					)
					(setq j (- j 1))	;j--
					
				)
			)
			(setq i (+ i 1))		;i++
			(print list)	;한 단계 정렬 결과 출력
		)
	)
)

(insSort lista)
(print '=======================)
(insSort listb)

Iterative Quicksort

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

int partition(int a[], int start, int end)
{
    int pivot = a[end]; //오른쪽 끝을 피벗으로

    int pIndex = start; //작은 수는 pindex 왼쪽, 큰 수는 오른쪽, 같은 건 어느쪽이든 상관없음

    // 원소가 피벗과 같거나 작으면 pindex 증가 후 피벗 앞에(왼쪽) 놓임
    for (int i = start; i < end; i++)
    {
        if (a[i] <= pivot)
        {
            swap(a[i], a[pIndex]); //왼쪽으로 보냄 (정확히는 a[0+i]으로
            pIndex++;
        }
    }

    swap(a[pIndex], a[end]); //pindex와 pivot을 스왑

    return pIndex;
}

// Iterative Quicksort routine
void iterativeQuicksort(int a[], int n)
{
    stack<pair<int, int>> s; //pair(int, int)가 들어가는 스택 s

    int start = 0;
    int end = n - 1;

    s.push(make_pair(start, end)); //(0, n-1)

    while (!s.empty()) //스택이 빌 때까지 루프
    {
        start = s.top().first, end = s.top().second;
        s.pop();

        // rearrange elements across pivot
        int pivot = partition(a, start, end);

        // push subarray indices containing elements that are
        // less than the current pivot to stack
        if (pivot - 1 > start) {
            s.push(make_pair(start, pivot - 1));
        }

        // push subarray indices containing elements that are
        // more than the current pivot to stack
        if (pivot + 1 < end) {
            s.push(make_pair(pivot + 1, end));
        }
    }
}

// Iterative Implementation of Quicksort
int main()
{
    int a[] = { 2, 5, 10, 8, 13, 6, 3 };
    int n = sizeof(a) / sizeof(a[0]);

    iterativeQuicksort(a, n);

    // print the sorted array
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }

    return 0;
}