1. 알고리즘의 선택

1) 합병 정렬(merge sort)

- 분할, 정복, 결합 이라는 3가지 단계를 통해 정렬이 이루어 진다.

- 분할: 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

- 정복: 부분 배열을 정렬한다. 만약 충분히 작지 않으면 순환호출을 통해서 분할 -> 정복의 과정을 수행한다.

- 결합: 정렬된 부분 배열들을 하나의 배열로 합병한다. 합병하는 과정에서 실제로 정렬이 일어나게 된다.

- 아래의 이미지를 통해 실제로 동작하는 방식을 머리속에 그려 볼 수 있다.

출처: https://gmlwjd9405.github.io/images/algorithm-merge-sort/merge-sort-concepts.png

- 컴바인 과정 살펴보기

- 위와 같은 Divide 과정을 거쳐 우리는 2개의 정렬된 리스트를 얻게 되었다.

- 하나의 리스트로 이를 정렬하는 과정에서 각 리스트의 요소들을 하나씩 비교하면 더 작은 수를 앞쪽에 배치하는 과정을 통해 정렬을 진행한다.

출처: https://gmlwjd9405.github.io/images/algorithm-merge-sort/merge-sort.png

2) 합병 정렬의 장단점

(1) 장점

- 원본 배열을 절반으로 나누어 정렬을 한다는 점에서 퀵소트와 유사하나 pivot 설정 없이 항상 두개로 분할하기 때문에 O(N x logN)이라는 시간 복잡도가 보장된다.

(2) 단점

- 공간 복잡도가 증가한다. 즉, 임시배열에 원본맵을 계속해서 옮겨주며 정렬을 하는 방식이기 때문에 추가적인 메모리가 필요하다.

- 추가적인 메모리를 할당할 수 없다면 퀵소트를 사용한다.

2. 자료 구조 선택

1) 이중 연결 리스트

(1) 장점

- 조회하는 데이터의 인덱스에 따라 앞 || 뒤에서 검색이 가능함으로 검색의 효율을 높일 수 있다.

- 즉, 이중연결리스트의 element 수의 중앙값을 기준으로 요구하는 인덱스의 값이 크거나 작을 때 next 또는 previous를 이용해 효율적으로 찾을 수 있다.

(2) 단점

- previous라는 필드를 유지해야 하기 때문에 메모리를 더 많이 사용한다.

- 조금 더 복잡(?) -_-;;

참고자료

- 분할 정복 알고리즘의 하나(https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html)

- 샐활코딩 이중 연결 리스트 (https://opentutorials.org/module/1335/8940)

1. 알아야 하는 개념

1) What is Big-O

- 알고리즘의 성능을 수학적으로 표기해주는 표기법.

- 시간 복잡도(처리 속도)와 공간 복잡도(메모리)가 있음.

- 알고리즘의 작동 시간을 표기하는 것이 아니라, 데이터나 사용자의 수가 증가함에 따라 알고리즘의 성능을 예측하는 것이 목적!

- 따라서 모든 상수들은 1로서 생각한다.(왜냐하면 무한히 사용자의 수와 데이터가 커진다면 2x = y에서의 2라는 상수는 의미가 없음.)

2) Big-O 표기법으로 알아보는 몇 가지 알고리즘

(1) O(1)

- 아래와 같은 함수의 경우 주어지는 num이라는 배열의 크기가 변화함에 따라 성능의 변화가 없다.

- 이때 우리는 "해당 함수는 Big O one의 시간 복잡도를 가진다"라고 말한다.

int is_positive(int *num)
{
	return (num[0] > 0 ? 1 : 0);
}

(2) O(n)

- 선형 시간 복잡도(linear time complex)

- 생각을 해본다면 이는, 입력되는 데이터의 크기만큼 비례해서 성능 증가한다.

- 이때 우리는 "해당 함수는 "Big O n의 시간 복잡도를 가진다"라고 말한다.

void printf_all(char *str)
{
	while (*str) 
    	write(1, *str++, 1);
}

(3) O(n^2)

- Quadratic time

- 버블 정렬, 삽입 정렬의 복잡도이기도 하다.

void swap(int *xp, int *yp) {
    int tmp = *xp;
    *xp = *yp;
    *yp = tmp;
}
 
void bubbleSort(int arr[], int n) {
    if (n == 1)return;
 
    for (int i = 0; i < n - 1; i++)
        if (arr[i] > arr[i + 1])
            swap(&arr[i], &arr[i + 1]);
 
    bubbleSort(arr, n - 1);
}

(4) O(2^n)

- 대표적인 피보나치 수열

int fibonacci(int n)
{
	if(n == 0)
		return (0);
	else if (n == 0)
		return (1);
	else
		return (fibonacci(n - 1) + fibonacci(n - 2));
}

(5) 나머지..

- 아래의 위키피디아의 표를 보면 더 많은 내용들을 확인할 수 있다.(위키피디아에서 자세히 보기)

(6) 몇 개의 영상들..

 - 15 Sorting Algorithms in 6 Minutes

- 그들만의 즐거움...ㅠㅜ

2. 과제 분석

1) Goals

- Sorting 알고리즘을 통해서 최적을 방법으로 sorting을 합니다.

- 그런데 무엇을 sorting 하는 것일까?

2) General Instrcutions

사람에 의해서 채점되기 때문에 구조와 네이밍에 있어서 자유롭습니다.
다만 아래의 규칙들은 존재합니다.

1. 실행 파일 이름은 **push_swap**으로 합니다.
2. Makefile을 생성하여 제출합니다. 일반적인 규칙들은 준수하며, 필요한 경우만 recompile 되도록 합니다.
3. 필요한 경우 Makefile을 포함한 libft 라이브러리를 사용하며, libft 라이브러리 컴파일 후 여러분의 프로젝트가 컴파일되도록 합니다.
4. 글로벌 변수 금지
5. C를 사용하고 norm을 준수하도록 합니다.
6. Segementation fault, bus error, double free 등과 같은 민감한 에러를 handling 해야 합니다.
7. 다음의 함수를 사용할 수 있습니다.
- write, read, malloc, free, exit

3) Mandatory part

1. 2개의 스택이 주어집니다.
2. a에는 중복되는 숫자 없이 양수 음수가 랜덤으로 주어집니다.
3. b는 비어있습니다.
4. a에 오름차순으로 정리합니다.
5. 필요에 의해 다음의 함수를 사용합니다.

- sa: swap a - a에서 처음 2개의 elements를 swap 합니다. 만약 하나 이하로 남게 되면 아무것도 하지 않습니다.

- sb: swap b - b에서 처음 2개의 elements를 swap 합니다. 만약 하나이하로 남게 되면 아무것도 하지 않습니다.

- ss: sa와 sb를 동시에 진행합니다.

- pa: b의 최상위에 있는 element를 a로 올립니다. b가 비어있으면 아무것도 하지 않습니다.

- pb: a의 최상위에 있는 element를 b로 올립니다. a가 비어있으면 아무것도 하지 않습니다.

- ra: a에 있는 모든 element를 한 칸씩 위로 올립니다. 즉, 처음 있던 element를 마지막에 오게 됩니다.

- rb: b에 있는 모든 element를 한칸씩 위로 올립니다. 즉, 처음 있던 element를 마지막에 오게 됩니다.

- rr: ra와 rb를 동시에 진행합니다.

- rra: a에 있는 모든 element를 한칸씩 아래로 내립니다. 즉, 마지막에 있던 element는 처음으로 오게 됩니다.

- rra: b에 있는 모든 element를 한칸씩 아래로 내립니다. 즉, 마지막에 있던 element는 처음으로 오게 됩니다.

- rrr: rra와 rrb를 동시에 합니다.

참고자료

-[자료구조 알고리즘] 빅오(Big-O) 표기법 완전정복(https://www.notion.so/push_swap-c15e62229b9541d78fadec4d6aae8b50)

- [자료구조] 2-3. Big-O 표기법의 예(https://makemethink.tistory.com/110)

Github Repository

- Github Repository(https://github.com/hitaeskim/ecole42)