신입 개발자 기술면접 질문 정리 - 알고리즘

목차

1. 버블 정렬(Bubble sort)에 대해 설명해주세요.
2. 선택 정렬(Selection Sort)에 대해 설명해주세요.

1. 버블 정렬(Bubble sort)에 대해 설명해주세요.

• 버블 정렬은 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘
• 0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬.
• 시간 복잡도는 O(n^2)

CS50 2-4강 버블 정렬

1) 최선의 경우

• 자료가 이미 정렬되어 있는 경우
• 비교횟수 : i번째 원소를 (n-1)번 비교하므로 n(n-1)/2번
• 자리 교환 횟수 : 자리교환이 발생하지 않음

2) 최악의 경우

• 자료가 역순으로 정렬되어 있는 경우
• 비교 횟수 : i번째 원소를 (n-1)번 비교하므로 n(n-1)/2번
• 자리 교환 횟수 : i번째 원소를 (n-1)번 비교하므로 n(n-1)/2번

2. 선택 정렬(Selection Sort)에 대해 설명해주세요.

• 선택 정렬은 첫 번째 값을 두번째 부터 마지막 값까지 차례대로 비교하여 최솟값을 찾아 첫 번째에 놓고
  두 번째 값을 세번째 부터 마지막 값까지 비교하여 최솟값을 찾아 두번째 위치에 놓는 과정을 반복하며 정렬하는 알고리즘

• 시간복잡도는 O(n^2)

CS50 2-5강 선택 정렬

출처

신입 개발자 기술면접 질문 정리 - 알고리즘