정렬 - 자료구조, 알고리즘

소개글

소트 - 인설션, 퀵, 머지 발표자료

목차

삽입 정렬
병합 정렬
퀵 정렬

본문내용

정렬(sort)
순서 없이 배열된 자료들을 어떤 기준에 따라 오름차순(ascending order)으로 또는 내림차순(descending order)으로 재배열하는 것
자료를 정렬하는 데 기준이 되는 특정 값을 키(key)라고 함
정렬의 예
컴퓨터 아이콘들을 이름 순으로 정렬
학생들의 정보를 성적 순으로 내림차순 정렬
학생들의 정보를 학년-이름을 기준으로 오름차순 정렬

삽입 정렬(insert sort)
이미 정렬되어있는 부분에 새로운 원소의 위치를 찾아 삽입하는 방식으로 정렬한다.

가정사항
S : 정렬된 배열의 왼쪽 부분
U : 정렬되지 않은 배열의 오른쪽 부분

정렬 방법
U 의 왼쪽에서 삽입할 원소 k를 선택
k를 가져와 S 에 있는 원소와 k를 비교 (k 있던 자리는 빈자리)
S 에서 k보다 큰 원소들을 오른쪽으로 이동
k를 S 에 만들어진 빈자리에 삽입
U 의 모든 원소들이 S 에 삽입될 때까지 반복

참고 자료

없음