문제6) 정렬 알고리즘은 데이터Set이 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 순서대로 나열하여 재배치하는 기법이다. 정렬 알고리즘과 관련하여 다음에 대하여 설명하시오.
가. 버블 정렬
나. 삽입 정렬
다. 퀵 정렬
답)
1. 버블 정렬의 설명
가. 버블정렬의 개념
- 정렬 대상리스트(배열)의 항목을 수평방향으로 나열했다고 가정했을 때, 왼쪽끝에서부터 시작해서 인접하는두 항목의 값을 비교하여 원하는 순서(오름차순 또는 내림차순)로 되어있지 않으면 서로 위치를 교환하는 정렬방법
- 시간복잡도는 O(N²)
나. 버블정렬의 예시
 |
|
2. 삽입 정렬의 설명
가. 삽입정렬의 개념
- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
- 시간복잡도 : O(N²)
나. 삽입정렬의 예시
 |
3. 퀵정렬의 설명
가. 퀵정렬의 개념
- 입력자료를 Pivot(기준데이터)을 중심으로 작은 값을 갖는 자료들과 큰 값을 갖는 자료들로 분할하여 정렬하며, 분할된 각 부분 리스트에 대해 반복적으로 퀵 정렬을 수행하는 정렬 알고리즘
- 시간복잡도 : 최악 : O(N²) / 평균 : O(Nlog₂N)
나. 퀵정렬의 예시
|
단계
|
Pivot
|
데이터
|
|
1
|
|
 |
|
2
|
30
|
 |
|
3
|
30
|
 |
|
4
|
17
|
 |
|
5
|
17
|
 |
|
6
|
16
|
 |
|
7
|
33
|
 |
|
8
|
33
|
 |
공감과 댓글은 아이티신비에게 큰 힘이 됩니다.
블로그 글이 유용하다면 블로그를 구독해주세요.♥