[자료구조] 삽입(insertion)정렬과 빠른(quick)정렬

소개글

A+받았던 기말 과제입니다. 고등학생들을 대상했기때문에 쉽게 쓸려고 노력했고, 따라서 이해하는데 어려움이 없으리라고 생각됩니다. 그러나 수준은 전혀 뒤쳐지지 않습니다.
중간중간 삽입되어있는 그림과 예, 그리고 프로그램 코드는 여러분의 이해를 도울 것입니다. 아무쪼록 많은 도움이 되었으면 합니다.

목차

정렬이란?
1. 삽입 정렬(insertion sort)
STEP 1. 삽입 정렬이란?
STEP 2. 삽입 정렬의 원리는?
STEP 3. 삽입 정렬의 예
STEP 4. Let's go Programming!!
STEP 5. 삽입 정렬의 성능
2. 빠른 정렬 (Quick Sort)
STEP 1. 빠른 정렬이란?
STEP 2. 빠른 정렬의 원리는?
STEP 3. 빠른 정렬의 예
STEP 4. Let's go programming!!
STEP 5. 빠른 정렬의 성능
4. 삽입 정렬과 빠른 정렬의 비교

본문내용

정렬(sorting)이란 주어진 자료를 순서화 하려는 기준에 따라 재배열하는 연산입니다. 여러 가지 정렬 알고리즘들이 사용되고 있지만, 여기에서 우리는 삽입 정렬과 빠른 정렬에 대해 배워보기로 하겠습니다. 준비가 되었으면 이제 출발할까요?
1. 삽입 정렬(insertion sort)
STEP 1. 삽입 정렬이란?
공부를 시작하려니 벌써부터 온 몸이 간지럽죠. 그럼 우리 컴퓨터 시간에 선생님 몰래 카드 게임 하던 상황을 잠시 떠올려볼까요. 아니면 친구들끼리 했던 때를 떠올려도 좋습니다.
여러분이 다음의 순서대로 카드를 받았다고 생각해봅시다. 그리고는 받은 카드를 자기 손에서 카드를 재배열하겠죠? 오름차순으로 정렬시킬 경우,

삽입 정렬과 빠른 정렬은 내부정렬방법 중에서도 삽입법에 속하는 방법입니다. 빠른 정렬은 또한 교환법에 속하기도 하죠. 삽입 정렬은 평균 O(n²)의 성능으로 빠른 정렬보다 성능이 떨어지긴 하지만, 가장 단순한 정렬 방법 중 하나로 많이 사용되고 있습니다. 빠른 정렬은 평균 O(nlog²n)의 성능을 가지며 가장 효율적인 정렬 방법으로 알려져 있습니다.

참고 자료

없음