24.06.21 알고리즘, C

24.06.21 알고리즘, C

알고리즘

삽입 정렬(Insertion Sort)

• 손 안의 카드를 정렬하는 방법과 유사하다.
• Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다.
• 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
• 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.

과정

1. 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
3. ‘1’번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

시간복잡도

• 평균, 최악의 경우 O(n^2)
• 최선의 경우 O(n)

공간복잡도

• 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.

장점

• 알고리즘이 단순하다
• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.⇒ 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.
• Selection, Bubble 알고리즘에 비교하여 상대적으로 빠르다.

단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
• 배열의 길이가 길어질수록 비효율적이다.

C

컴파일 과정

1. 전처리 과정

• 헤더 파일 삽입
  • #include 구문을 만나면 헤더파일을 찾아 그 내용을 순차적으로 삽입한다.
  • 매크로 치환 및 적용한다.

2. 컴파일 과정(전단부 - 중단부 - 후반부)

• 전단부
  • 언어 종속적인 부분 처리 - 어휘, 구문, 의미 분석
• 중단부
  • SSA 기반으로 최적화 수행 - 프로그램 수행 속도 향상으로 성능 높이기 위함
• 후단부
  • RTS로 아키텍처 최적화 수행 - 더 효율적인 명령어로 대체해서 성능 높이기 위함

3. 어셈블 과정

• 컴파일이 끝나면 어셈블리 코드가 된다. 이 코드는 어셈블러에 의해 기계어가 된다.
• 어셈블러로 생성되는 파일은 명령어와 데이터가 들어있는 ELF 바이너리 포맷 구조를 가진다(링커가 여러 바이너리 파일을 하나의 실행 파일로 효과적으로 묶기 위해 명령어와 데이터 범위 를 일정한 규칙을 갖고 형식화 해놓는다.)

4. 링킹 과정

• 오브젝트 파일들과 프로그램에서 사용된 C 라이브러리를 링크한다.
• 해당 링킹 과정을 거치면 실행파일이 만들어진다.