MergeSort

[CS50X] Week3 번외편(Sort 구현 - Selection, Bubble, Merge, 비트연산자 )

번외편을 따로 만든 이유는 3주차 Algorithms 에서 Selection, Bubble, Merge Sort가 나오는데 바로 구현하기 내용이 어려운 것과 정렬한 결과를 Array 로 return 하는 것이 자연스러운데 C에서 return Array 이런식으로 동작하지 않기 때문에 포인터 개념을 알고 있어야 했다. 그래서 4주차 Memory 에서 포인터에 대해 배운 덕분에 구현 할 수 있게 되었다. 추가적으로 비트 연산자 관련 내용도 같이 다루려 한다. Selection Sort - O(n^2), Ω(n^2) #include int SelectionSort(int numbers[], int length); int Swap(int *a, int *b); int main(void) { int numbers..

[CS50X] 2024 Week3 Algorithms

알고리즘을 배울 때면 항상 중학생 때 들었던 가우스 일화가 생각난다. 1 + 2 + 3 + ... + 99 + 100 = ??? 이 계산을 해보라는 것이였는데 자연스럽게 1 + 2, 3 + 3 을 하면서 계산했던 기억이 난다. 선생님은 10초 만에 시간이 끝났다며 계산을 한 사람이 있는지 물었는데 아무도 없었다. 아마 계산기를 써도 그렇게 빠르게 하긴 어려울 것이다. 근데 가우스는 10살 무렵에 이 계산을 10초 안에 했다고 한다. 그의 비법은 거꾸로 뒤집어 2번 더하는 것이였다. 1 + 2 + 3 + ... + 99 + 100 100 + 99 + 97 + ... + 2 + 1 = 101 + 101 + ... + 101 --> 101 * 100 10100 이라는 수가 나오는데 2번 더했으니 2로 나누면 ..