sorting algorithm의 이해(java)

소개글

sorting algorithm의 이해(java)에 대한 보고서 자료입니다.

목차

1.Soriting Algorithm의 이해
(1) Quick sort Algorithm
(2) Merge sort Algorithm
(3)Insertion sort Algorithm
Insertion sort의 경우에는 리스

2. java를 이용한 Soriting Algorithm의 구현
(1)코드
(2)sorting Program이 잘 작동되는지 시현
(3)Sorting Time 비교

3. 느낀점

본문내용

1.Soriting Algorithm의 이해

(1) Quick sort Algorithm
Quick sort의 경우 코딩한 바와 같이 pivot을 오른쪽 서브파일과 왼쪽 서브파일이 같도록 구현한 경우 이 때, pivot의 위치를 결정하는데 O(n)의 시간이 소요된다. 따라서 크기가 n인 파일을 정렬하는데 걸리는 시간을 T(n)이라고 하고, 이것의 크기가 비슷한 2개의 종속 파일로 분할되도록 제어키가 선택된다고 가정하면, 결국 Quick sort는 O(nlogn)의 시간이 걸릴 것이다. 그러나 비균등적으로 분할되는(pivot의 위치가 중앙이 아닌 경우) 경우에는 O(n^2)만큼이 걸릴 것이다.

(2) Merge sort Algorithm
Merge sort는 이미 정렬되어 있는 2개의 서브파일을 병합하여 하나의 새로운 파일을 생성하는 과정을 순환적으로 적용시켜 최종적으로 1개의 파일로 병합될 때까지 반복시키는 방법이다. Merge sort는 최악의 경우나 평균의 경우 모두 O(nlogn)의 시간이 걸린다.

(3)Insertion sort Algorithm
Insertion sort의 경우에는 리스트가 완전히 역순으로 되어 있는 최악의 경우에는 O(n^2)만큼의 시간이 걸린다. 따라서 삽입 정렬은 정렬하고자 하는 리스트의 데이터들이 이미 거의 정렬된 상태일 때 적용하는 것이 바람직하다.



2. java를 이용한 Soriting Algorithm의 구현

(1)코드

┌─────────────────────────────────────────────────
│　MainTestCode
└─────────────────────────────────────────────────
class MainTestCode{

public static void main(String[] args) throws Exception {
int n = 10;
System.out.println("n="+n);
double [] element = new double[n];

System.out.println();
System.out.println();
System.out.println("Sorting 시간을 비교");
System.out.println("1.Quick sort");


System.out.println();

for(int i=0; i element[i] = ((int)(Math.random()*(n-1)) +1);
/*Math.random()는 0.0~1.0사이의 double형
*따라서 ((int)(Math.random()*[RANGE]))+[BEGIN]*/
}

키워드

merge sort,   Quick sort,   insertion sort,   데이터 구조,   algorithm,   java