본문 바로가기

삽입정렬구현1

[알고리즘] Sorting_선택정렬과 삽입정렬 구현하기.java * 선택정렬 * : 가장 간단한 정렬 알고리즘, 배열 A[1~n]에서 가장 큰 원소를 찾아 배열의 끝자리에 있는 A[n]과 치환 : 시간복잡도 - (n-1)+(n-2)+...+2+1= O(n^2) - 각 루프마다 1. 최대원소찾기 2. 최대 원소와 맨 오른쪽 원소 교환 3. 맨 오른쪽 원소 제외시키기 - 하나의 원소만 남을 때 까지 위의 루프를 반복한다. * 삽입정렬 * : 이미 정렬된 i개의 배열에 원소를 하나 더 더해서 i+1개 짜리 배열을 만드는 과정을 반복 : 하나의 배열에서 시작해 점차 크기를 늘리는 방법 : 시간 복잡도 - worst case : (n-1)+(n-2)+...+2+1= O(n^2) -> 배열이 역으로 정렬되어있는 경우 - best case : 1+1+...+1+1=O(n) -> .. 2022. 1. 9.

이전 1 다음

티스토리툴바