2022_07_11_자료구조

알고리즘 선택의 기준이 되는 시간 복잡도 유형

• 빅 오메가 : 최선일 때 연산 횟수를 나타내는 표기법
• 빅 세타 : 보통일 때 연산 횟수를 나타낸 표기법
• 빅 오 : 최악일 때 연산 횟수를 나타낸 표기법

빅 오 표기법

버블 정렬

선택 정렬 : 버블 정렬의 자리 바꿈 횟수를 줄임으로써 성능을 개선한 알고리즘

1. 남은 정렬 부분에서 최소값을 찾느다
2. 남은 정렬 부분에서 가장 아펭 있는 데이터와 최소값을 swap 한다
3. 가장 앞에 있는 데이터를 다음 위치로 이동하여 범위를 축소한다
4. 남은 정렬 부분이 없을 때까지 반복한다

삽입 정렬 :기본 정렬 중 가장 큰 효율성을 갖음( 버블,선택 보다 더 빠름) , 정렬이 조금 되어있는 배열에서 고 효율

1. 현재 index에 있는 데이터를 선택한다
2. 현재 선택한 데이터가 정렬 범위 내에 삽입될 위치를 탐색한다
3. 삽입 위치부터 index위치까지 shift연산을 수행한다
4. 삽입 위치 현재 데이터를 삽입하고 index를 증가시킨다
5. 선택할 데이터가 없을 때까지 반복한다.